7.26集训

Posted on 2020-07-26 Edited on 2020-11-14 In 暑假日常

#上午

考试 #下午

讲题讲课

以下有的东西是粘的

同余定理

若$a \% b == c \% b$, 我们称之为$a\equiv c (\mod b)$

在四则运算中，我们需要知道

在做题时，我们经常会遇到对一个数取模的运算

我们需要知道

$(a+b)\%c=((a\%c)+(b\%c))\%c$

$(a-b)\%c=(((a-b)\%c)+c)\%c$

$(a\times b)\%c=((a\%c)\times(b\%c))\%c$

对于除法的处理参见下面的逆元

回归正题

快速幂的作用就是以$O(\log{b})$的时间复杂度解决$a^b\%c$的问题

正常暴力的话我们只能$O(b)$

这里用到的是二分的思想

根据上面的同余定理，显然我们可以将问题二分

LL ksm(LL a, LL n, int c) {
   if (n == 0) return 1;
   if (n & 1) return (LL)ksm(a, n - 1, c) * a % c;
   int res = ksm(a, n >> 1, c);
   return (LL)res * res % c;
}

上面的是递归式的，我们也有非递归式的

不妨换个角度思考一下

我们把指数换成二进制

比如我们求$7^{10}$

在二进制的角度，也就是$7^{(1010)_2}$

所以呢，我们很自然的联想到把它拆分成$7^{(1000)2}$和$7^{(10)2}$

将上面的方法推广，所有的这样的问题我们都可以将指数拆开，分开计算

这样我们需要指数的二进制的每一位，因此，复杂度同上

下面的快速幂也是最常用的快速幂

LL ksm(LL a, LL b, int mod) {
   LL res = 1LL; 
   while(b) {
      if(b & 1) res = (LL)res * a % mod;
      a = a * a % mod;
      b >>= 1;
   }
   return res;
}

逆元

由费马小定理

$a^p\equiv a (\mod p)$

$a^{p-1}\equiv 1 (\mod p)$

$a\times a^{p-2}\equiv 1 (\mod p)$

$a^{p-2}\equiv \frac{1}{a} (\mod p)$

因此，a在模c意义下的乘法逆元为$ksm(a, c - 2, c)$

还有一种$O(n)$线性求逆元的方法

推荐记住推导过程，当然要是直接记住结论也没问题

对于$i$在mod p意义下的逆元,我们可以

令$a=\frac p i, b=p \% i$

显然p可以表示为$i\times a + b$

于是，$i\times a + b \equiv 0 (\mod p)$

$i\times a \equiv -b (\mod p)$

$i^{-1} \equiv -\frac a b (\mod p)$

于是，i的逆元就是$-a\times b^{-1}$

即$-\frac p i \times (p\%i)^{-1}$

可能你会问，那$p\%i$的逆元咋求，用ksm的结论吗？

不难发现，$p \% i$肯定比当前的i要小，因此我们再求i的逆元的时候$p\%i$的逆元是已知的！

void mutl(int mod) {
   inv[1] = 1;
   for(int i = 2; i <= M; i++) 
   inv[i] = (((mod-mod/i)*inv[mod % i])%mod+mod)%mod; 
}

#### 慢速乘（龟速乘）感觉比较简单直接贴代码吧

LL msc(LL a, LL b, LL c) {
   LL ans = 0;
   while(b) {
      if(b & 1) ans = (ans + a) % c;
      a = (a + a) % c;
      b >>= 1;
   }
   return ans;
}

矩阵加速

比如，以斐波那契数列为例

$f[n] = f[n - 1] + f[n - 2]$

不妨构造矩阵 $\left[\begin{matrix} f[n] & f[n + 1] & f[n + 2] \ 0 & 0 & 0 \ 0 & 0 & 0 \end{matrix}\right]$

如果我们称上面的矩阵为第n个矩阵

那么显然第一个矩阵就是 $\left[\begin{matrix} f[1] & f[2] & f[3] \ 0 & 0 & 0 \ 0 & 0 & 0 \end{matrix}\right]$

也即 $\left[\begin{matrix} 1 & 1 & 2 \ 0 & 0 & 0 \ 0 & 0 & 0 \end{matrix}\right]$

我们现在的任务便是构造一个矩阵B，使得 $& f[n + 1] & f[n + 2]
0 & 0 & 0
0 & 0 & 0 \end{matrix}]B = & f[n + 2] & f[n + 3]
0 & 0 & 0
0 & 0 & 0 \end{matrix}] $

根据矩阵乘法的方式，我们成功获得矩阵B $\left[\begin{matrix} 0 & 0 & 0 \ 1 & 0 & 1 \ 0 & 1 & 1 \end{matrix}\right]$

贴上代码

struct matrix { 
   LL a[3][3];
   matrix() {
      for(int i = 0; i <= 2; i++)
         for(int j = 0; j <= 2; j++)
           	a[i][j] = 0;
   }
   friend matrix operator * (const matrix &b, const matrix &c) {
      matrix d;
      for(int i = 0; i <= 2; i++)
         for(int j = 0; j <= 2; j++)
            for(int k = 0; k <= 2; k++)
               (d.a[i][j] += ((LL)b.a[i][k] * c.a[k][j])) %= mod;
      return d;
   }
   void rec() {
     	for(int i = 0; i <= 2; i++)
         for(int j = 0; j <= 2; j++)
            this->a[i][j] = (i == j);
   }
   matrix ksm(LL t) {
      matrix c;
      c.rec();
      while(t) {
         if(t & 1LL) c = c * (*this);
         (*this) = (*this) * (*this);
         t >>= 1LL;
      }
      return *this = c;
   }
}A, B;
int main() {
   A.a[1][0] = A.a[2][1] = A.a[2][2] = A.a[1][2] = 1LL;
   B.a[0][0] = B.a[0][1] = 1;
   B.a[0][2] = 2;
   printf("%lld\n", (B * A.ksm(in() - 1)).a[0][0]);
   return 0;
}

#### STL 一大堆东西 $queue,vector,map,set,priority_queue$ 都是基操，虽然可能大概有的我还不会.....

甩甩链接：

关于迭代器的使用：

1	for(STL::iterator it = STL.begin(); it != STL.end(); it++)

#### 卡特兰数公式：$C_{2n}^{n} - C_{2n}^{n-1}$

可以推出来：$\dfrac {C_{2n}^{n}} {n+1}$

这玩意应用多

通过一群数的进zhan出zhan顺序可以得到，设$h[i]$表示以$i$为结尾的数的总出栈方案

显然$h[i] = \sum {h[j-1]*h[i-(j+1)-1]}$ 其中 $1 \leq j \leq i$

#晚上

改题

药神

写个线段树维护一下标记，其中，如果一个数被干了五次以上，就为1了

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 5e5+66;

int n, m;
int a[N], b[N<<2], d[N<<2];

inline void build (int s, int t, int p) {
   if (s == t) {
      d[p] = a[s];
      b[p] = a[s];
      return;
   }
   int m = (s + t) >> 1;
   build (s, m, p<<1), build (m+1, t, (p<<1)|1);
   d[p] = d[p<<1] + d[(p<<1)|1];
   b[p] = max(b[p<<1], b[(p<<1)|1]);
}
inline void update (int l, int r, int s, int t, int p) {
   if (s == t) {
      d[p] = sqrt(d[p]);
      b[p] = sqrt(b[p]);
      return;
   }
   if (b[p] <= 1) return;
   int m = (s + t) >> 1;
   if (l <= m) update (l, r, s, m, p<<1);
   if (r > m) update (l, r, m+1, t, (p<<1)|1);
   d[p] = (d[p<<1] + d[(p<<1)|1]);
   b[p] = max(b[p<<1], b[(p<<1)|1]);
}
inline int getsum (int l, int r, int s, int t, int p) {
   if (l <= s && t <= r) return d[p];
   int m = (s + t) >> 1, sum = 0;
   if (l <= m) sum += getsum (l, r, s, m, p<<1);
   if (r > m) sum += getsum (l, r, m+1, t, (p<<1)|1);
   return sum;
}
signed main () {
   scanf ("%lld", &n);
   for (int i = 1; i <= n; ++ i) 
      scanf ("%lld", &a[i]);
      build (1, n, 1);
      cin >> m;
      for (int i = 1; i <= m; ++ i) {
	 int opt, x, y;
	 cin >> opt >> x >> y;
	 if (x > y) swap(x, y);
	 if (opt == 0) update (x, y, 1, n, 1);
	 else cout << getsum (x, y, 1, n, 1) << '\n';
      }
   return 0;
}

单调队列优化dp

别人一眼$dp$，我也一眼$dp$，但是别人写$dp$，我却在写搜索，全$T$了....

我们设$f[i][j]$为到达$i,j$这个点所能获得的最大价值

显然：$f[i][j] = max(f[i-1][k] + val[i][j]$其中$j-t \leq k \leq j+t$

显然：我们只需要在$i$的上一层，维护一个长度为$2*t$的滑动窗口就可以了

#include <bits/stdc++.h>
using namespace std;

const int N = 4e3+66;

int n, m, k, t;
int head = 1, tail = 0, res;
int f[N][N], q[N], a[N][N];

inline void calc(int x) {
   for (int i = 1; i <= t; ++ i) {
      while (f[x][i] > f[x][q[tail]] && tail >= head)
	 -- tail;
	 q[++tail] = i;
      }
}

inline void Insert(int x, int last) {
   if (x+t <= m) {
      while (f[last][x+t]>f[last][q[tail]] && tail >= head)
	 -- tail;
         q[++tail] = x+t;
      }
   while (q[head]+t < x) ++ head;
}

int main () {
   cin >> n >> m >> k >> t;
   for (int i = 1; i <= k; ++ i) {
      int x, y, v;
      cin >> x >> y >> v;
      a[x][y] = v;
   }
   for (int i = 1; i <= n; ++ i) f[1][i] = a[1][i];
   for (int i = 2; i <= n; ++ i) {
      calc(i-1);
      for (int j = 1; j <= m; ++ j){
	 Insert(j, i-1);
	 f[i][j] = f[i - 1][q[head]]+a[i][j];
      }
      head = 1, tail = 0;
   }	
   for (int i = 1; i <= m; ++ i) res = (res<f[n][i])?f[n][i]:res;
   cout << res;
   return 0;
}

一群操蛋的奶牛https://www.luogu.com.cn/problem/P2344

不会

埋个坑

日后补

$7.28update$

正解是维护前缀和与树状数组

我写了个搜索在某谷就过去了，但是HEZG给的数据过不去

某谷数据太水了！！！

给出能在某谷AC的代码

#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<int> >q;
const int N = 1e5+66, mod = 1e9+9;
	
int n, m, res;
int yhm[N], a[N];
bool v[N];

inline void xieruyijichushihua() {
   yhm[0] = 1;
   cin >> n;
   for (int i = 1; i <= n; ++ i) cin >> a[i];
}

inline void jiejuewenti() {
   q.push(0);
   while (q.size()) {
   int now = q.top(); q.pop();
   res = 0;
      for (int i = now+1; i <= n; ++ i) {
          res += a[i];
          if (res >= 0) {
	     yhm[i] += yhm[now];
             yhm[i] %= mod;
             if (!v[i]) q.push(i), v[i] = 1;
          }
      }
   }
}

int main () {
   xieruyijichushihua();
   jiejuewenti();
   cout << yhm[n];
   return 0;
}

写入以及初始化：$xieruyijichushihua$

解决问题:$jiejuewenti$