2021十月暂记（2）

2021十月暂记（2）

文章目录

• • 10.13
  • 10.14
  • • AT2039 [ARC060C] 高橋君とホテル / Tak and Hotels （贪心，二分，倍增）
  • 10.18
  • • AT2021 [ARC059C] キャンディーとN人の子供 / Children and Candies (递推，数学，DP，前缀和优化)
    • AT2688 [ARC080C] Young Maids （性质，分治，数据结构优化）
  • 10.19
  • • AT2272 [ARC066B] Xor Sum （性质，递推）
    • T2 数位 DP ，矩阵优化
  • 10.20
  • • P3758 [TJOI2017]可乐 （DP，矩阵优化）
  • 10.21
  • • T1 （同余）最短路
    • T2 区间 DP
  • 10.22
  • • P5664 [CSP-S2019] Emiya 家今天的饭 容斥 计数 DP 逐步优化
    • P4513 小白逛公园 线段树 最优子结构

10.13

10.14

AT2039 [ARC060C] 高橋君とホテル / Tak and Hotels （贪心，二分，倍增）

AT2039 [ARC060C] 高橋君とホテル / Tak and Hotels
看似很简单，纯粹贪心，每一步能跳多远就跳多远，但是数据范围很大，我们没有办法暴力跳。然后考虑到旅店距离的单调性，我们可以处理出对于全部起点，最远可以到达哪里，但是要查询的时候，时间复杂度还是很大。既然不能一步一步地跳，那就几步几步的跳吧，于是可以想到倍增。
用二分预处理出一步可达的最远距离后，我们尝试计算 2 k 2^k 2k 步后，能到达的最远的地方。
然后对于每次询问，我们就可以根据预处理的数据开始跳了，先尝试大步数，如果超过了目的地，就尝试小一些的步数，直至没有越过目的地，就跳这一步，然后继续从大步数尝试到小步数，直到不能动为止。跳的过程中累计答案。
如果跳的过程中已经到达了目的地，那么直接输出答案即可，否则由于我们记的是跳 2 k 2^k 2k 步最远的距离，所以可能停在目的地之前，这时判断一下然后再跳一步就可以了。
总的时间复杂度 O ( ( N + Q ) log ⁡ N ) O((N+Q)\log N) O((N+Q)logN)

int main()
{pow2[0] = 1;for(int i = 1;i <= 22;i ++) pow2[i] = pow2[i - 1] << 1;scanf("%d",&n);for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);scanf("%d",&L);for(int i = 1;i <= n;i ++)f[i][0] = bisearch(a[i]);//计算第一步f[n][0] = n + 1;f[n + 1][0] = n + 1;//有一些步数越过最后一个旅店，这里处理一下防止出错for(int j = 1;j <= 20;j ++)for(int i = 1;i <= n + 1;i ++)f[i][j] = f[f[i][j - 1]][j - 1];scanf("%d",&Q);for(int t = 1;t <= Q;t ++){scanf("%d%d",&x,&y);if(x > y) swap(x,y);//正着跳与反着跳都一样ans = 0;for(int j = 20;j >= 0;j --)//查询{if(f[x][j] <= y){ans += pow2[j];//累计答案x = f[x][j];//更新位置if(x == y) break;}}if(x < y) ans ++;//还差一步printf("%d\n",ans);}return 0;
} 

10.18

AT2021 [ARC059C] キャンディーとN人の子供 / Children and Candies (递推，数学，DP，前缀和优化)

AT2021 [ARC059C] キャンディーとN人の子供 / Children and Candies

说白了就是要计算式子：
∑ x 1 = A 1 B 2 ∑ x 2 = A 1 B 2 ⋯ ∑ x n = A n B n f ( x 1 , x 2 , ⋯ , x n ) \sum_{x_1=A_1}^{B_2}\sum_{x_2=A_1}^{B_2}\cdots\sum_{x_n=A_n}^{B_n}f(x_1,x_2,\cdots,x_n) x1​=A1​∑B2​​x2​=A1​∑B2​​⋯xn​=An​∑Bn​​f(x1​,x2​,⋯,xn​)
f ( x 1 , x 2 , ⋯ , x n ) f(x_1,x_2,\cdots,x_n) f(x1​,x2​,⋯,xn​) 表示将 C C C 颗糖分给所有小朋友的所有情况的活跃指数之和，即
f ( x 1 , x 2 , ⋯ , x n ) = ∑ ∑ k i = C x 1 k 1 x 2 k 2 ⋯ x n k n f(x_1,x_2,\cdots,x_n)=\sum_{\sum k_i=C} x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n} f(x1​,x2​,⋯,xn​)=∑ki​=C∑​x1k1​​x2k2​​⋯xnkn​​
算是积累经验了吧，对于求方案，我们可以考虑 DP.
首先考虑简单的情况，就是 x i x_i xi​ 只有一个取值，那么设 F ( i , j ) F(i,j) F(i,j) 表示前 i i i 个小朋友分 j j j 颗糖的所有情况的活跃指数之和，那么有
F ( i , j ) = ∑ k = 0 j F ( i − 1 , j − k ) × x i k F(i,j) = \sum_{k=0}^{j}F(i-1,j-k)\times x_i^k F(i,j)=k=0∑j​F(i−1,j−k)×xik​
然后尝试将方程推广到复杂的情况，考虑 x n x_n xn​ 有不同的取值，那么答案是
∑ x n = A n B n f ( x 1 , x 2 , ⋯ , x n ) = ∑ x n = A n B n ∑ ∑ k i = C x 1 k 1 x 2 k 2 ⋯ x n k n = ∑ x n = A n B n ∑ k n = 0 n x k n ∑ ∑ k i = C − k n x 1 k 1 x 2 k 2 ⋯ x n − 1 k n − 1 \begin{aligned} &\sum_{x_n=A_n}^{B_n}f(x_1,x_2,\cdots,x_n)\\[2ex]=&\sum_{x_n=A_n}^{B_n}\sum_{\sum k_i=C} x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}\\[2ex]=&\sum_{x_n=A_n}^{B_n}\sum_{k_n=0}^{n}x^{k_n}\sum_{\sum k_i=C-k_n} x_1^{k_1}x_2^{k_2}\cdots x_{n-1}^{k_{n-1}} \end{aligned} ==​xn​=An​∑Bn​​f(x1​,x2​,⋯,xn​)xn​=An​∑Bn​​∑ki​=C∑​x1k1​​x2k2​​⋯xnkn​​xn​=An​∑Bn​​kn​=0∑n​xkn​∑ki​=C−kn​∑​x1k1​​x2k2​​⋯xn−1kn−1​​​
于是我们发现：
F ( n , j ) = ∑ k = 0 j F ( n − 1 , j − k ) × ∑ x n = A n B n x n k F(n,j)=\sum_{k=0}^{j}F(n-1,j-k)\times\sum_{x_n=A_n}^{B_n} x_n^{k} F(n,j)=k=0∑j​F(n−1,j−k)×xn​=An​∑Bn​​xnk​
进一步推广，得到：
F ( i , j ) = ∑ k = 0 j F ( i − 1 , j − k ) × ∑ x i = A i B i x i k F(i,j)=\sum_{k=0}^{j}F(i-1,j-k)\times\sum_{x_i=A_i}^{B_i} x_i^{k} F(i,j)=k=0∑j​F(i−1,j−k)×xi​=Ai​∑Bi​​xik​

AT2688 [ARC080C] Young Maids （性质，分治，数据结构优化）

AT2688 [ARC080C] Young Maids
手算样例，发现其实按照题目给的选数顺序，不能找到一个最佳策略，因为从后往前确定序列的话，无法得知前面的情况，不能从局部最优推到全局最优。于是考虑逆向思维，能不能从前往后确定序列，然后就可以发现性质：

1. 作为开头 q 1 q_1 q1​ 的数一定在奇数位置上，紧跟着的 q 2 q_2 q2​ 在 p p p 中的位置一定比 q 1 q_1 q1​ 在 p p p 中的位置靠后，且一定在偶数位置上。
2. 下一次选的两个数在 p p p 中的位置一定不会跨越之前选过的数在 p p p 中的位置，也就是说，每次选完一次数，可以将原区间分成三个子区间，而且子区间同样具备性质 1.

于是我们考虑分治，最朴素的办法就是在区间内暴力搜奇数位置上最小的数，然后在这个位置之后再暴力搜偶数位置上的最小的数，然后将这两个数存入待定数组，继续分治，最后回溯的时候合并答案，原先搜到的两个数一定在最前面，然后就有了大概 O ( N 2 ) O(N^2) O(N2) 的做法。
然后考虑优化，找数可以用线段树处理，合并答案可以归并排序，于是我自认为稳稳地 O ( N log ⁡ N ) O(N\log N) O(NlogN) 要切掉这一题了，结果 TLE 了 4 次，T 飞了 …我也不知道为什么…
T 飞代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>using namespace std;
const int inf = 0xfffffff;
int N,a[200005],mint[3][800005],pos[3][800005];
vector<int > ans;void Build(int k,int l,int r,int p)
{if(l == r){mint[p][k] = inf;pos[p][k] = l;return ;}int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;Build(lson,l,mid,p);Build(rson,mid + 1,r,p);if(mint[p][lson] < mint[p][rson]){mint[p][k] = mint[p][lson];pos[p][k] = pos[p][lson];}else{mint[p][k] = mint[p][rson];pos[p][k] = pos[p][rson];}return ;
}void Modify(int k,int l,int r,int x,int y,int p)
{if(l > x || r < x) return ;if(l == r && l == x) {mint[p][k] = y;pos[p][k] = x;return ;}int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;Modify(lson,l,mid,x,y,p);Modify(rson,mid + 1,r,x,y,p);if(mint[p][lson] < mint[p][rson]){mint[p][k] = mint[p][lson];pos[p][k] = pos[p][lson];}else{mint[p][k] = mint[p][rson];pos[p][k] = pos[p][rson];}return ;
}pair<int ,int > Query(int k,int l,int r,int x,int y,int p)
{if(l > y || r < x || l > r) return make_pair(inf,0);if(x <= l && r <= y) return make_pair(mint[p][k],pos[p][k]);int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;pair<int ,int > res1,res2;res1 = Query(lson,l,mid,x,y,p);res2 = Query(rson,mid + 1,r,x,y,p);return res1.first < res2.first ? res1 : res2;
}vector<int > Solve(int l,int r,int p)
{vector<int > res;if(l > r) return res;if(l + 1 == r){	res.push_back(a[l]);res.push_back(a[r]);return res;}int lpos = 0;int rpos = 0;int i = 0;int j = 0;vector<int > b[3],tmp;lpos = Query(1,1,N,l,r,p).second;rpos = Query(1,1,N,lpos+1,r,p^1).second;res.push_back(a[lpos]);res.push_back(a[rpos]);b[0] = Solve(l,lpos - 1,p);b[1] = Solve(lpos + 1,rpos - 1,p^1);b[2] = Solve(rpos + 1,r,p);for(i = 0,j = 0;i < b[0].size() && j < b[1].size();){if(b[0][i] < b[1][j]) {tmp.push_back(b[0][i]);tmp.push_back(b[0][i + 1]);i += 2;}else {tmp.push_back(b[1][j]);tmp.push_back(b[1][j + 1]);j += 2;}}for(;i < b[0].size();i ++) tmp.push_back(b[0][i]);for(;j < b[1].size();j ++) tmp.push_back(b[1][j]);for(i = 0,j = 0;i < b[2].size() && j < tmp.size();){if(b[2][i] < tmp[j]) {res.push_back(b[2][i]);res.push_back(b[2][i + 1]);i += 2;}else {res.push_back(tmp[j]);res.push_back(tmp[j + 1]);j += 2;}}for(;i < b[2].size();i ++) res.push_back(b[2][i]);for(;j < tmp.size();j ++) res.push_back(tmp[j]);return res;
}int main()
{scanf("%d",&N);Build(1,1,N,0);Build(1,1,N,1);for(int i = 1;i <= N;i ++){scanf("%d",&a[i]);Modify(1,1,N,i,a[i],i&1);}ans = Solve(1,N,1);for(int i = 0;i < ans.size();i ++)printf("%d ",ans[i]);return 0;} 

再考虑优化，其实是合并答案的时候复杂度太高，能不能每次都取最优解，然后直接输出？可以考虑先计算子区间所取的数，然后使用优先队列维护子区间，那么下一次处理的区间所取的数就是最优解。
于是就出现了暴力开 6 重嵌套 pair的奇观：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>using namespace std;
const int inf = 0xfffffff;
int N,a[200005],mint[3][800005],pos[3][800005];
vector<int > ans;void Build(int k,int l,int r,int p)
{if(l == r){mint[p][k] = inf;pos[p][k] = l;return ;}int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;Build(lson,l,mid,p);Build(rson,mid + 1,r,p);if(mint[p][lson] < mint[p][rson]){mint[p][k] = mint[p][lson];pos[p][k] = pos[p][lson];}else{mint[p][k] = mint[p][rson];pos[p][k] = pos[p][rson];}return ;
}void Modify(int k,int l,int r,int x,int y,int p)
{if(l > x || r < x) return ;if(l == r && l == x) {mint[p][k] = y;pos[p][k] = x;return ;}int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;Modify(lson,l,mid,x,y,p);Modify(rson,mid + 1,r,x,y,p);if(mint[p][lson] < mint[p][rson]){mint[p][k] = mint[p][lson];pos[p][k] = pos[p][lson];}else{mint[p][k] = mint[p][rson];pos[p][k] = pos[p][rson];}return ;
}pair<int ,int > Query(int k,int l,int r,int x,int y,int p)
{if(l > y || r < x || l > r) return make_pair(inf,0);if(x <= l && r <= y) return make_pair(mint[p][k],pos[p][k]);int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;pair<int ,int > res1,res2;res1 = Query(lson,l,mid,x,y,p);res2 = Query(rson,mid + 1,r,x,y,p);return res1.first < res2.first ? res1 : res2;
}pair<int ,pair<int ,pair<int ,pair<int ,pair<int ,int > > > > > make_elem(int a,int b,int c,int d,int e,int f)
{return make_pair(a,make_pair(b,make_pair(c,make_pair(d,make_pair(e,f)))));
}int main()
{scanf("%d",&N);Build(1,1,N,0);Build(1,1,N,1);for(int i = 1;i <= N;i ++){scanf("%d",&a[i]);Modify(1,1,N,i,a[i],i&1);}priority_queue<pair<int ,pair<int ,pair<int ,pair<int ,pair<int ,int > > > > > > q;int lpos = Query(1,1,N,1,N,1).second;int rpos = Query(1,1,N,lpos+1,N,0).second;int tmplpos = 0;int tmprpos = 0;int l = 0;int r = 0;q.push(make_pair(-a[lpos],make_pair(-a[rpos],make_pair(lpos,make_pair(rpos,make_pair(1,N))))));for(;!q.empty();){printf("%d %d ",-q.top().first,-q.top().second.first);lpos = q.top().second.second.first;rpos = q.top().second.second.second.first;l = q.top().second.second.second.second.first;r = q.top().second.second.second.second.second;q.pop();if(l  < lpos - 1){tmplpos = Query(1,1,N,l,lpos - 1,l&1).second;tmprpos = Query(1,1,N,tmplpos + 1,lpos - 1,(l&1)^1).second;q.push(make_elem(-a[tmplpos],-a[tmprpos],tmplpos,tmprpos,l,lpos - 1));}if(lpos + 1  < rpos - 1)	{tmplpos = Query(1,1,N,lpos + 1,rpos - 1,(lpos + 1)&1).second;tmprpos = Query(1,1,N,tmplpos + 1,rpos - 1,((lpos + 1)&1)^1).second;q.push(make_elem(-a[tmplpos],-a[tmprpos],tmplpos,tmprpos,lpos + 1,rpos - 1));}if(rpos + 1  < r){tmplpos = Query(1,1,N,rpos + 1,r,(rpos + 1)&1).second;tmprpos = Query(1,1,N,tmplpos + 1,r,((rpos + 1)&1)^1).second;q.push(make_elem(-a[tmplpos],-a[tmprpos],tmplpos,tmprpos,rpos + 1,r));}}return 0;} 

10.19

AT2272 [ARC066B] Xor Sum （性质，递推）

再次强调了求方案数用 DP 的思想（其实是递推思想）
首先比较容易发现的是 a ⊕ b ⩽ a + b a\oplus b \leqslant a + b a⊕b⩽a+b，因为异或运算总是不进位的，所以只要 v ⩽ N v\leqslant N v⩽N ，那么 u u u 就满足了。
以什么作为阶段递推？我们可以一位一位地考虑，比如设 f ( i , j ) f(i,j) f(i,j) 表示 a + b a+b a+b 前 i i i 位的所有情况中， v ⩽ j v\leqslant j v⩽j 的方案数，考虑如何求出 f ( i + 1 , k ) f(i+1,k) f(i+1,k)
下一位中，有三种情况

1. a i + 1 = 0 , b i + 1 = 0 a_{i+1}=0,b_{i+1}=0 ai+1​=0,bi+1​=0 ，就是两位均为 0 的情况，那么 k = 2 j k=2j k=2j
2. a i + 1 = 1 , b i + 1 = 0 a_{i+1}=1,b_{i+1}=0 ai+1​=1,bi+1​=0 或 a i + 1 = 0 , b i + 1 = 1 a_{i+1}=0,b_{i+1}=1 ai+1​=0,bi+1​=1 ，有一位为 1 的情况，那么 k = 2 j + 1 k=2j+1 k=2j+1
3. a i + 1 = 1 , b i + 1 = 1 a_{i+1}=1,b_{i+1}=1 ai+1​=1,bi+1​=1 ，两位都为 1 的情况， k = 2 j + 2 k=2j+2 k=2j+2

所以有
f ( i , j ) = f ( i − 1 , ⌊ j − 2 2 ⌋ ) + f ( i − 1 , ⌊ j − 1 2 ⌋ ) + f ( i − 1 , ⌊ j 2 ⌋ ) f(i,j)=f(i-1,\lfloor\dfrac{j-2}{2}\rfloor) + f(i-1,\lfloor\dfrac{j-1}{2}\rfloor) + f(i-1,\lfloor\dfrac{j}{2}\rfloor) f(i,j)=f(i−1,⌊2j−2​⌋)+f(i−1,⌊2j−1​⌋)+f(i−1,⌊2j​⌋)

由于 N N N 很大，考虑递归实现，为了避免超时，用 map做记忆化辅助。

#include<iostream>
#include<cstdio>
#include<map>using namespace std;
typedef long long ll;
const ll modn = 1e9 + 7;
ll N,ans,M;map<ll ,ll > rec;ll F(ll x)
{if(!rec[x]) rec[x] = ((F((x-2)>>1)%modn + F(x>>1)%modn)%modn + F((x-1)>>1)%modn)%modn;return rec[x];
}int main()
{scanf("%lld",&N);rec[0] = 1;//b = 0,a = 0;rec[1] = 2;//a = 1,b = 1;a = 0,b = 0ans = F(N)%modn;printf("%lld",ans%modn);return 0;} 

这样一道看似十分数论的题，最后通过 DP 解决了，这再次启示我们递推是计算方案数的重要手段，而且我们可以将数转化为二进制逐位考虑。

T2 数位 DP ，矩阵优化

zxt走在路上，一个小朋友拉住zxt，送了他一颗糖，等zxt吃下那颗糖后，他被邀请去打羽毛球，于是他傻乎乎地被骗走了，而且还连着输了111把，zxt从那天开始发誓，要把这个数字记住，可是他是一只3岁的猪，只能发明一些特殊的方法记住他。

这种方法是这样的：对于给定的n位数，zxt想记住有多少个包含111的数。如6位数中有111078，111111，511106等，可是他真的只是一只3岁的猪，而且脑容量有限（对998244353取模），所以请你帮帮他。(允许前导零的存在)
n ⩽ 1 0 18 n\leqslant 10^{18} n⩽1018

要统计特殊数的个数考虑 DP ，设 f ( i , j ) f(i,j) f(i,j) 表示前 i i i 位中，开头有连续 j j j 个 1 的方案数。
f ( i , 0 ) = 9 × ( f ( i − 1 , 0 ) + f ( i − 1 , 1 ) + f ( i − 1 , 2 ) ) f(i,0) = 9\times(f(i-1,0)+f(i-1,1) +f(i-1,2)) f(i,0)=9×(f(i−1,0)+f(i−1,1)+f(i−1,2))
f ( i , 1 ) = f ( i − 1 , 0 ) f(i,1)=f(i-1,0) f(i,1)=f(i−1,0)
f ( i , 2 ) = f ( i − 1 , 1 ) f(i,2)=f(i-1,1) f(i,2)=f(i−1,1)
f ( i , 3 ) = f ( i − 1 , 2 ) + 10 × f ( i − 1 , 3 ) f(i,3)=f(i-1,2) + 10\times f(i-1,3) f(i,3)=f(i−1,2)+10×f(i−1,3)

由于 n n n 太大，但是我们看到递推式的线性关系，所以可以考虑用矩阵优化。
现在考虑构造矩阵 A A A 使得
( F i , 0 F i , 1 F i , 2 F i , 3 ) = A × ( F i − 1 , 0 F i − 1 , 1 F i − 1 , 2 F i − 1 , 3 ) \begin{pmatrix} F_{i,0}\\[1ex]F_{i,1}\\[1ex]F_{i,2}\\[1ex]F_{i,3} \end{pmatrix}=A\times \begin{pmatrix} F_{i-1,0}\\[1ex]F_{i-1,1}\\[1ex]F_{i-1,2}\\[1ex]F_{i-1,3} \end{pmatrix} ⎝⎜⎜⎜⎜⎛​Fi,0​Fi,1​Fi,2​Fi,3​​⎠⎟⎟⎟⎟⎞​=A×⎝⎜⎜⎜⎜⎛​Fi−1,0​Fi−1,1​Fi−1,2​Fi−1,3​​⎠⎟⎟⎟⎟⎞​
易得
A = ( 9 9 9 0 1 0 0 0 0 1 0 0 0 0 1 10 ) A=\begin{pmatrix} 9 &9&9&0\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&10 \end{pmatrix} A=⎝⎜⎜⎛​9100​9010​9001​00010​⎠⎟⎟⎞​
然后跑矩阵快速幂即可。

#include<iostream>
#include<cstdio>using namespace std;
typedef long long ll;
const ll modn = 998244353;
ll n,f[5][5] = {{ 1 , 0, 0 ,0}
};
ll res[5][5] = {{1 , 0 , 0 , 0},{ 0 , 1 , 0 , 0},{0 , 0 , 1, 0},{0 , 0 , 0, 1}};
ll dp[5][5] = {{ 9 , 9 , 9 , 0 },{ 1 , 0 , 0 , 0 },{ 0 , 1 , 0 , 0 },{ 0 , 0 , 1 , 10 }
}; void multidp2()
{ll a[5][5];ll b[5][5];ll c[5][5];for(int i = 0;i < 5;i ++)for(int j = 0;j < 5;j ++)a[i][j] = b[i][j] = dp[i][j],c[i][j] = 0;for(int i = 0;i < 5;i ++)for(int k = 0;k < 5;k ++)for(int j = 0;j < 5;j ++)c[i][j] = ((c[i][j] % modn) + ((a[i][k]%modn) * (b[k][j]%modn))%modn)%modn; for(int i = 0;i < 5;i ++)for(int j = 0;j < 5;j ++)dp[i][j] = c[i][j];return ;
}void multidp1()
{ll a[5][5];ll b[5][5];ll c[5][5];for(int i = 0;i < 5;i ++)for(int j = 0;j < 5;j ++)a[i][j] = res[i][j],b[i][j] = dp[i][j],c[i][j] = 0;for(int i = 0;i < 5;i ++)for(int k = 0;k < 5;k ++)for(int j = 0;j < 5;j ++)c[i][j] = ((c[i][j] % modn) + ((a[i][k]%modn) * (b[k][j]%modn))%modn)%modn; for(int i = 0;i < 5;i ++)for(int j = 0;j < 5;j ++)res[i][j] = c[i][j];return ;		
}void multians()
{ll a[5][5];ll b[5][5];ll c[5][5];for(int i = 0;i < 5;i ++)for(int j = 0;j < 5;j ++)a[i][j] = res[i][j],b[i][j] = f[i][j],c[i][j] = 0;for(int i = 0;i < 5;i ++)for(int k = 0;k < 5;k ++)for(int j = 0;j < 1;j ++)c[i][j] = ((c[i][j] % modn) + ((a[i][k]%modn) * (b[k][j]%modn))%modn)%modn; for(int i = 0;i < 5;i ++)for(int j = 0;j < 1;j ++)f[i][j] = c[i][j];return ;		
}void qpow( ll n)
{for(;n;){if(n & 1) multidp1();multidp2();n >>= 1;}return ;
}int main()
{scanf("%lld",&n);qpow(n);multians();printf("%lld",f[3][0] % modn);return 0;
} 

10.20

P3758 [TJOI2017]可乐 （DP，矩阵优化）

P3758 [TJOI2017]可乐

当我们得到一个邻接矩阵 G G G ，要求图中长度为 k k k 的路径的个数。

路径计数问题考虑用 DP 解决，设 f ( i , j , k ) f(i,j,k) f(i,j,k) 表示 i i i 到 j j j 的路径中，长度为 k k k 的个数。
f ( i , j , k ) = ∑ k ′ ⩽ k ∑ p = 1 n f ( i , p , k ′ ) × f ( p , j , k − k ′ ) f(i,j,k) = \sum_{k'\leqslant k}\sum_{p = 1}^{n}f(i,p,k')\times f(p,j,k-k') f(i,j,k)=k′⩽k∑​p=1∑n​f(i,p,k′)×f(p,j,k−k′)
尝试将其改为递推的一般形式，已知 f ( i , j , k 1 ) , f ( i , j , k 2 ) f(i,j,k_1),f(i,j,k_2) f(i,j,k1​),f(i,j,k2​) 有
f ( i , j , k 1 + k 2 ) = ∑ p = 1 n f ( i , p , k 1 ) × f ( p , j , k 2 ) f(i,j,k_1+k_2) = \sum_{p = 1}^{n} f(i,p,k_1)\times f(p,j,k_2) f(i,j,k1​+k2​)=p=1∑n​f(i,p,k1​)×f(p,j,k2​)
可以看成矩阵 F k 1 + k 2 F_{k_1+k_2} Fk1​+k2​​ 是 F k 1 F_{k_1} Fk1​​ 与 F k 2 F_{k_2} Fk2​​ 的积，可知 F 1 = G , F 2 = G 2 F_1 = G,F_2 = G^2 F1​=G,F2​=G2 ，由此知道 F k = G k F_k = G^k Fk​=Gk

但是本题还有一个自爆的选项，于是考虑建一个虚点，让机器人可以从任意城市走进去但不能出来即可。

#include<iostream>
#include<cstdio>using namespace std;
typedef long long ll;
const ll modn = 2017;
ll N,M,t,u,v,ans;
ll map[105][105],I[105][105],F[105][105];
ll res[105][105];void multidp1()
{ll a[105][105],b[105][105],c[105][105];for(int i = 0;i <= N;i ++)for(int j = 0;j <= N;j ++)a[i][j] = map[i][j],b[i][j] = res[i][j],c[i][j] = 0;for(int i = 0;i <= N;i ++)for(int k = 0;k <= N;k ++)for(int j = 0;j <= N;j ++)c[i][j] = (c[i][j]%modn + ((a[i][k]%modn)*(b[k][j]%modn))%modn);for(int i = 0;i <= N;i ++)for(int j = 0;j <= N;j ++)res[i][j] = c[i][j]; return ;
}void multidp2()
{ll a[105][105],b[195][105],c[105][105];for(int i = 0;i <= N;i ++)for(int j = 0;j <= N;j ++)a[i][j] = b[i][j] = map[i][j], c[i][j] = 0;for(int i = 0;i <= N;i ++)for(int k = 0;k <= N;k ++)for(int j = 0;j <= N;j ++)c[i][j] = (c[i][j]%modn + ((a[i][k]%modn)*(b[k][j]%modn))%modn);for(int i = 0;i <= N;i ++)for(int j = 0;j <= N;j ++)map[i][j] = c[i][j];return ;
}int main()
{scanf("%lld%lld",&N,&M);for(int i = 1;i <= M;i ++){scanf("%lld%lld",&u,&v);map[u][v] = 1;map[v][u] = 1;}for(int i = 0;i <= N;i ++) map[i][i] = 1,map[i][0] = 1,res[i][i] = 1;scanf("%lld",&t);for(;t;){if(t & 1) multidp1();multidp2();t >>= 1;}for(int i = 0;i <= N;i ++) ans = (ans%modn + res[1][i]%modn)%modn;printf("%lld",ans%modn);return 0;
}

10.21

T1 （同余）最短路

根据模运算与乘运算的性质建立最短路模型求最小价值，十分清奇的 idea

T2 区间 DP

最后一场模拟赛了，这种比较基础的 DP 都没有调出来，吐了…

10.22

P5664 [CSP-S2019] Emiya 家今天的饭 容斥 计数 DP 逐步优化

本来是想着练练骗分来着，然后 1h 敲了 64pts 的程序，比较满意。当然，骗完分后就要写正解了。
最开始的朴素 DP 是，设 f ( k , i , a 1 , a 2 , ⋯ , a m ) f(k,i,a_1,a_2,\cdots ,a_m) f(k,i,a1​,a2​,⋯,am​) 表示用前 i i i 种方法做了 k k k 道菜，每种主要食材使用情况为 a 1 , a 2 , ⋯ , a m a_1,a_2,\cdots ,a_m a1​,a2​,⋯,am​ 的总方案数，针对 m ⩽ 3 m\leqslant 3 m⩽3 的情况只需要 5 维，再滚动 k k k 可以骗得 64pts 的好成绩。
我们发现，瓶颈在于我们无法表示 a 1 , a 2 , ⋯ , a m a_1,a_2,\cdots ,a_m a1​,a2​,⋯,am​ 如此庞大的状态，于是考虑状态设计优化。最令人难受的其实是限制 3 ，考虑限制 3 给我们带来限制的同时，带来了什么性质。
一个重要的性质是：做菜所用的其中一种主要食材出现次数不超过 n 2 \dfrac{n}{2} 2n​ ⟺ \Longleftrightarrow ⟺ 如果存在主要食材超过这个限制，那么有且仅有一种主要食材超出这个限制
这也就意味着，我们可以求出超出限制的方案数，然后用总方案数减去不满足限制的方案数。于是我们枚举每一种食材，计算当它超出限制时做菜的方案数。
假设我们枚举了食材 p p p ，设 f ( k , i , x , y ) f(k,i,x,y) f(k,i,x,y) 表示前 k k k 道菜用前 i i i 种方法做，使用食材 p p p 的菜有 x x x 道，不使用食材 k k k 的菜有 y y y 道的方案数。那么：

1. 第 k k k 道菜可以用 i i i 方法和 p p p 食材
2. 第 k k k 道菜用 i i i 方法和非 p p p 食材
3. 第 k k k 道菜不用 i i i 方法

f ( k , i , x , y ) = f ( k − 1 , i − 1 , x − 1 , y ) × a i , p + f ( k − 1 , i − 1 , x , y − 1 ) × ∑ j ≠ p a i , p + f ( k , i − 1 , x , y ) f(k,i,x,y)=f(k-1,i-1,x-1,y)\times a_{i,p} + f(k-1,i-1,x,y-1)\times \sum_{j\neq p} a_{i,p} +f(k,i-1,x,y) f(k,i,x,y)=f(k−1,i−1,x−1,y)×ai,p​+f(k−1,i−1,x,y−1)×j​=p∑​ai,p​+f(k,i−1,x,y)
因为我们最后求的是做完 n n n 道菜的方案数，求前 k k k 道菜用前 k k k 种方法得到的最终结果与以上求法都是前 n n n 道菜用 n n n 种方法的方案数，所以我们可以将 i i i 从状态中去除，直接设 f ( k , x , y ) f(k,x,y) f(k,x,y) 表示前 k k k 道菜用食材 p p p 的有 x x x 道，不用食材 p p p 的有 y y y 道，于是我们就有：
f ( k , x , y ) = f ( k − 1 , x , y ) + f ( k − 1 , x − 1 , y ) × a i , p + f ( k − 1 , x , y − 1 ) × ∑ j ≠ p a i , p f(k,x,y) = f(k-1,x,y) + f(k - 1,x -1,y)\times a_{i,p} + f(k-1,x,y-1)\times \sum_{j\neq p} a_{i,p} f(k,x,y)=f(k−1,x,y)+f(k−1,x−1,y)×ai,p​+f(k−1,x,y−1)×j​=p∑​ai,p​
我们对于每一个 p p p 计算 f p ( n , x , y ) f_p(n,x,y) fp​(n,x,y) ，超出限制的部分就是
∑ x > n 2 f p ( n , x , y ) \sum_{x > \frac{n}{2}} f_p(n,x,y) x>2n​∑​fp​(n,x,y)

时间复杂度 O ( n 3 m ) O(n^3m) O(n3m)
尽管时间与空间都得到了很大的优化，但是还是不足以通过此题，只能继续优化了。
最后我们发现 x + y = n x+y=n x+y=n ，所以减少一维的枚举，同时状态设计也可以进一步优化为 f ( k , Δ x ) f(k,\Delta x) f(k,Δx) 表示前 k k k 道菜中 x − y = Δ x x-y=\Delta x x−y=Δx 的方案数，最终就有
f ( k , Δ x ) = f ( k − 1 , Δ x + 1 ) × a i , p + f ( k − 1 , Δ x − 1 ) × ∑ j ≠ p a i , p + f ( k − 1 , Δ x ) f(k,\Delta x) = f(k-1,\Delta x + 1)\times a_{i,p} + f(k-1,\Delta x - 1)\times \sum_{j\neq p} a_{i,p} + f(k - 1,\Delta x) f(k,Δx)=f(k−1,Δx+1)×ai,p​+f(k−1,Δx−1)×j​=p∑​ai,p​+f(k−1,Δx)
时间复杂度 O ( n 2 m ) O(n^2m) O(n2m)，代码很短

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>using namespace std;
typedef long long ll;
const ll modn = 998244353;
ll n,m;
ll f[105][505],ans2,ans1;
ll a[105][3005],sum[105],ans;int main()
{scanf("%lld%lld",&n,&m);for(int i = 1;i <= n;i ++)for(int j = 1;j <= m;j ++){scanf("%lld",&a[i][j]);sum[i] += a[i][j];sum[i] %= modn;}ans1 = 1;for(int i = 1;i <= n;i ++)ans1 = (((sum[i] + (ll)1)%modn) * ans1)%modn;ans1 --;for(int k = 1;k <= m;k ++){memset(f,0,sizeof(f));f[0][n] = 1;for(int i = 1;i <= n;i ++)for(int j = n - i;j <= n + i;j ++){f[i][j] = f[i - 1][j]%modn;if(j > 0) f[i][j] = (f[i][j]%modn + (((f[i - 1][j - 1]%modn) * (a[i][k]%modn))%modn))%modn;f[i][j] = (f[i][j]%modn + ((f[i - 1][j + 1]%modn) * ((sum[i] - a[i][k] + modn)%modn))%modn)%modn;}for(int i = 1;i <= n;i ++)ans2 = (ans2%modn + (f[n][i + n]%modn))%modn;}printf("%lld",(ans1%modn - ans2%modn + modn)%modn);return 0;} 

P4513 小白逛公园 线段树 最优子结构

逆向思维思考问题，寻找最优解的性质与条件
假设我们已经得到了两个区间的最优连续段，考虑这两个区间合并后的最优连续段是哪几种情况。

1. 这两个最优连续段刚好拼在一起
2. 这两个最优连续段中间有小于 0 的元素存在

显然，对于第一种情况，我们直接合并这两个最优的连续段就好了。
对于第二种情况，我们可以分类讨论：

1. 要跨越左右区间，那么我们将其转化为上述第一种情况：左区间的包括右端点的最优连续段 和 右区间的包括左端点的最优连续段 合并在一起
2. 左区间中的最优连续段
3. 右区间中的最优连续段

然后就做完了。
两个关键点：

1. 从已经得到最优解的角度出发，考虑如何再次得到最优解。最优子结构的思想。
2. 将跨越左右区间的情况转化成为最优子结构中的情况。

#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;
const int inf = 0xfffffff;
int n,m,a[500005],opt,x,y;
int t[3000005];
int lsum[3000005],rsum[3000005],sum[3000005];pair<int ,pair<int ,pair<int ,int > > > mymax(pair<int ,pair<int ,pair<int ,int > > > p,pair<int ,pair<int ,pair<int ,int > > > q)
{int tmp = max(max(p.first,q.first),p.second.second.second + q.second.second.first);int tmpl = max(p.second.second.first,p.second.first + q.second.second.first);int tmpr = max(q.second.second.second,q.second.first + p.second.second.second);int tmpx = p.second.first + q.second.first;return make_pair(tmp,make_pair(tmpx,make_pair(tmpl,tmpr)));
}void Update(int k,int lson,int rson)
{int tmp = rsum[lson] + lsum[rson];t[k] = max(tmp,max(t[lson],t[rson]));lsum[k] = max(lsum[lson],sum[lson] + lsum[rson]);rsum[k] = max(rsum[rson],sum[rson] + rsum[lson]);sum[k] = sum[lson] + sum[rson];return ;
}void Build(int k,int l,int r)
{if(l == r){t[k] = a[l];lsum[k] = rsum[k] = t[k];sum[k] = t[k];return ;} int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;Build(lson,l,mid);Build(rson,mid + 1,r);Update(k,lson,rson);return ;
}void Modify(int k,int l,int r,int x,int y)
{if(l > x || r < x) return ;if(l == r && l == x){t[k] = y;lsum[k] = rsum[k] = y;sum[k] = y;return ;} int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;Modify(lson,l,mid,x,y);Modify(rson,mid + 1,r, x,y);Update(k,lson,rson);return ;
}pair<int ,pair<int,pair<int ,int > > > Query(int k,int l,int r,int x,int y)
{if(l > y || r < x) return make_pair(-inf,make_pair(-inf,make_pair(-inf,-inf)));if(x <= l && r <= y)return make_pair(t[k],make_pair(sum[k],make_pair(lsum[k],rsum[k])));int mid = (l + r) >> 1;int lson = k << 1;int rson = lson + 1;pair<int ,pair<int ,pair<int ,int > > > ltmp,rtmp;ltmp = Query(lson,l,mid,x,y);rtmp = Query(rson,mid + 1,r,x,y);if(ltmp.first == -inf) return rtmp;if(rtmp.first == -inf) return ltmp;return mymax(ltmp,rtmp);
}int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);Build(1,1,n);for(int i = 1;i <= m;i ++){scanf("%d",&opt);if(opt == 1){scanf("%d%d",&x,&y);if(x > y) swap(x,y);printf("%d\n",Query(1,1,n,x,y).first);}else{scanf("%d%d",&x,&y);Modify(1,1,n,x,y);}}return 0;
}