一些经典的 DP 类型。
I.数位 DP
数位 DP 归在此处，无论是高位往低位还是低位往高位。需要注意数位 DP 的本质是一种按位比较的贪心思想，因而可以加以扩展。
I.[CQOI2013]二进制A+B
最后判无解试了很多次才判成功……主要是因为“\(a,b,c\leq2^{30}\)中有个\(\leq\)而不是\(<\)就很烦人。
思路很简单：设\(f[i][j][k][l][0/1]\)表示：
按位DP到第\(i\)位，
\(a,b,c\)中分别用了\(j,k,l\)个\(1\)，
并且进位的情况是\(0/1\)，
的最小方案。
转移之间枚举这一位\(a,b\)分别填\(1\)还是填\(0\)即可。
复杂度约是\(O(\log^4)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int lim=31;
int a,b,c,f[lim][lim][lim][lim][2],res=0x3f3f3f3f3f3f3f3f;
void read(int &x){
int t;
x=0;
scanf("%lld",&t);
for(int i=0;i<lim;i++)x+=((t>>i)&1);
}
void chmin(int &a,int b){
a=min(a,b);
}
signed main(){
read(a),read(b),read(c),memset(f,0x3f3f3f3f,sizeof(f));
// printf("%d %d %d\n",a,b,c);
f[0][0][1][1][0]=1;
f[0][1][0][1][0]=1;
f[0][1][1][0][1]=0;
f[0][0][0][0][0]=0;
for(int i=0;i<lim-1;i++)for(int j=0;j<=a;j++)for(int k=0;k<=b;k++)for(int l=0;l<=c;l++)for(int p=0;p<2&&j+p<=a;p++)for(int q=0;q<2&&k+q<=b;q++){
chmin(f[i+1][j+p][k+q][l+((p+q)&1)][(p+q)>1],f[i][j][k][l][0]+(((p+q)&1)<<(i+1)));
chmin(f[i+1][j+p][k+q][l+((p+q+1)&1)][(p+q)>0],f[i][j][k][l][1]+(((p+q+1)&1)<<(i+1)));
}
// for(int i=0;i<lim-1;i++)for(int j=0;j<=a;j++)for(int k=0;k<=b;k++)for(int l=0;l<=c;l++)for(int m=0;m<2;m++)printf("%d %d %d %d %d:%d\n",i,j,k,l,m,f[i][j][k][l][m]);
for(int i=0;i<lim;i++)res=min(res,f[i][a][b][c][0]);
printf("%lld\n",res>(0x7f7f7f7f)?-1:res);
return 0;
}
II.CF1073E Segment Sum
数位DP裸题。
设\(f(pos,sta,lim,lead)\)表示：
到第\(pos\)个位置时，
\(0\sim9\)的出现状态状压出来是\(sta\)，
是否压上限/是否有前导零的状态是\(lim\)和\(lead\)。
\(f\)要维护这样的数的个数和他们的和。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int mod=998244353;
int l,r,k,num[23],pov[23],tp;
pii f[23][1<<10];
pii dfs(int pos,int sta,bool lim,bool lead){
if(__builtin_popcount(sta)>k)return make_pair(0,0);
if(!pos)return make_pair(0,1);
if(!lim&&!lead&&f[pos][sta]!=make_pair(-1ll,-1ll))return f[pos][sta];
pii res=make_pair(0,0);
for(int i=0;i<=(lim?num[pos]:9);i++){
pii tmp=dfs(pos-1,sta|(lead&&!i?0:(1<<i)),lim&&(i==num[pos]),lead&&(!i));
(res.first+=tmp.first)%=mod;
(res.second+=tmp.second)%=mod;
(res.first+=tmp.second*i%mod*pov[pos]%mod)%=mod;
}
if(!lim&&!lead)f[pos][sta]=res;
return res;
}
int calc(int ip){
tp=0;
while(ip)num[++tp]=ip%10,ip/=10;
return dfs(tp,0,1,1).first;
}
signed main(){
scanf("%lld%lld%lld",&l,&r,&k),l--,memset(f,-1,sizeof(f));
pov[1]=1;
for(int i=2;i<23;i++)pov[i]=(pov[i-1]*10)%mod;
printf("%lld\n",(calc(r)-calc(l)+mod)%mod);
return 0;
}
III.CF288E Polo the Penguin and Lucky Numbers
IV.[HNOI2007]梦幻岛宝珠
好题。
明显它是01背包的模型，但值域过大。咋办呢？
我们考虑令 \(f_{i,j}\) 表示只考虑 \(a\times 2^i\) 类型的物品，关于 \(a\) 做的一个背包。显然，暴力求出这个东西的时空复杂度都是可接受的。
我们再考虑 \(g_{i,j}\) 表示有 \(j\times2^i+w\operatorname{and}(2^i-1)\) 这么多的背包容量时的答案，即只考虑 \(w\) 的下 \(i\) 位，且第 \(i\) 位上选了 \(j\) 单位的物品。我们考虑由 \(g_{i,j}\) 更新 \(g_{i+1}\)。
显然，如果 \(w\) 的第 \(i\) 位有一个 \(1\)，在第 \(i+1\) 位上，\(g_{i,j}\) 就与一个大小为 \(\left\lfloor\dfrac{j}{2}\right\rfloor\) 的物品等价；否则，即 \(w\) 的第 \(i\) 位没有 \(1\)，它与 \(\left\lceil\dfrac{j}{2}\right\rceil\) 等价。
于是我们就用 \(g_i\) 和 \(f_{i+1}\) 即可拼凑出 \(g_{i+1}\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int> >v[40];
int f[40][2000],lim[40],g[40][2000];
void chmx(int &x,int y){if(x<y)x=y;}
int main(){
while(true){
scanf("%d%d",&n,&m);
if(n==-1&&m==-1)break;
memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(lim,0,sizeof(lim));
for(int i=0;i<=30;i++)v[i].clear();
for(int i=1,a,b,c;i<=n;i++){
scanf("%d%d",&a,&b),c=0;
while(!(a&1))a>>=1,c++;
v[c].push_back(make_pair(a,b));
}
for(int i=0;i<=30;i++){
for(auto k:v[i]){
for(int j=lim[i];j>=0;j--)chmx(f[i][j+k.first],f[i][j]+k.second);
lim[i]+=k.first;
// printf("(%d,%d)\n",k.first,k.second);
}
// for(int j=0;j<=lim[i];j++)printf("%d ",f[i][j]);puts("");
}
for(int i=0;i<=lim[0];i++)g[0][i]=f[0][i];
for(int i=0;i<=30;i++){
for(int j=0;j<=lim[i];j++)for(int k=lim[i+1];k>=0;k--)chmx(g[i+1][k+((j+!((m>>i)&1))>>1)],f[i+1][k]+g[i][j]);
lim[i+1]+=(lim[i]+!((m>>i)&1))>>1;
}
printf("%d\n",g[31][0]);
}
return 0;
}
V.CF1290F Making Shapes
首先，如果每个向量的出现次数确定——假设向量 \(\vec p_i=(x_i,y_i)\) 的出现次数是 \(c_i\)——则该凸包亦是唯一确定的。具体构造方式是将所有向量按照倾角排序——因为没有共线向量所以排序结果唯一——然后依次连接在一起就能构造凸包。
所以我们只需要满足以下两个条件即可：
\[\sum\limits_{x_i>0}c_ix_i=-\sum\limits_{x_i<0}c_ix_i\leq m \]\[\sum\limits_{y_i>0}c_iy_i=-\sum\limits_{y_i<0}c_iy_i\leq m \]常规的方法不太好处理这样的计数。我们考虑倍增。
具体而言，设以上四个值分别为 \(a,b,c,d\)。现在我们已经确定了每个 \(c_i\) 的最低 \(k\) 位的值是 \(0\) 还是 \(1\)。
则，因为 \(|x_i|,|y_i|\leq4\)，所以 \(a,b,c,d\leq 4n\times2^k\)。
那么，考虑在状态中维护 \(a,b,c,d\) 除以 \(2^k\) 后下取整的结果。显然这一结果不会超过 \(4n\)。
然后还要考虑低 \(k\) 位的结果。故我们还要额外维护两个值 \(x,y\) 表示 \(a,c\) 两个值的低 \(k\) 位是否不大于 \(m\) 的低 \(k\) 位。
考虑分析复杂度。如设向量坐标值域是 \(V\)（在本题中有 \(V\leq4\)），显然是 \(O(\log m(Vn)^42^n)\)。
不要忘记减去所有 \(c_i\) 全为 \(0\) 的情形。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int f[30][21][21][21][21][2][2],n,m,X[5],Y[5];
int dfs(int bit,int a,int b,int c,int d,bool x,bool y){
if(bit==30)return !a&&!b&&!c&&!d&&!x&&!y;
int&res=f[bit][a][b][c][d][x][y];
if(res!=-1)return res;
res=0;
int A=a,B=b,C=c,D=d;
bool xx=x,yy=y;
for(int i=0;i<(1<<n);i++){
a=A,b=B,c=C,d=D,x=xx,y=yy;
for(int j=0;j<n;j++){
if(!(i&(1<<j)))continue;
if(X[j]>0)a+=X[j];
if(X[j]<0)b-=X[j];
if(Y[j]>0)c+=Y[j];
if(Y[j]<0)d-=Y[j];
}
if((a&1)>((m>>bit)&1))x=true;
if((a&1)<((m>>bit)&1))x=false;
if((c&1)>((m>>bit)&1))y=true;
if((c&1)<((m>>bit)&1))y=false;
if((a&1)!=(b&1))continue;
if((c&1)!=(d&1))continue;
a>>=1,b>>=1,c>>=1,d>>=1;
(res+=dfs(bit+1,a,b,c,d,x,y))%=mod;
}
// printf("%d %d %d %d %d %d %d:%d\n",bit,A,B,C,D,xx,yy,res);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d%d",&X[i],&Y[i]);
memset(f,-1,sizeof(f));
printf("%d\n",(dfs(0,0,0,0,0,false,false)+mod-1)%mod);
return 0;
}
VI.[TopCoder10232]TheSum
显然的想法是一位一位处理。到底是从低位向高位还是高位向低位呢？低向高易于处理进位，高向低易于处理前导零，各有利弊。这里选择高向低处理。
于是设 \(f(a,b,c,car,A,B,C)\) 表示分别 DP 到位置 \(a,b,c\)，进位的状态是 \(car\)，前导零的状态是 \(A,B,C\) 的最优方案。转移分两种，一种是删一个数，转移到 \(a+1\) 或 \(b+1\) 或 \(c+1\)。一种是枚举下一位填入的数码，然后分啥也不做、用一次 I、用一次 R 三种情形讨论即可。
细节很多。
代码：
#include<bits/stdc++.h>
using namespace std;
class TheSum{
private:
int a,b,c,I,D,R,_a[10],_b[10],_c[10],_A,_B,_C;
int f[20][20][20][2][2][2][2];
void chmn(int&x,int y){if(x>y)x=y;}
int dfs(int A,int B,int C,bool car,bool a_,bool b_,bool c_){
int&val=f[A][B][C][car][a_][b_][c_];if(val!=-1)return val;val=0x3f3f3f3f;
if(A)chmn(val,dfs(A-1,B,C,car,a_,b_,c_)+D);
if(B)chmn(val,dfs(A,B-1,C,car,a_,b_,c_)+D);
if(C)chmn(val,dfs(A,B,C-1,car,a_,b_,c_)+D);
for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)for(int CAR=0;CAR<2;CAR++){
if(car!=(i+j+CAR)/10)continue;
int k=(i+j+CAR)%10;
int A_=a_|!!i,B_=b_|!!j,C_=c_|!!k;
if(!A_&&!B_&&!C_)continue;
for(int u=0;u<3;u++)for(int v=0;v<3;v++)for(int w=0;w<3;w++){//0:match. 1:insert. 2:replace.
if(u==0&&(!A||_a[A-A_]!=i))continue;
if(v==0&&(!B||_b[B-B_]!=j))continue;
if(w==0&&(!C||_c[C-C_]!=k))continue;
if(u==2&&!A)continue;
if(v==2&&!B)continue;
if(w==2&&!C)continue;
int _1=((int)(u==1)+(v==1)+(w==1)),_2=((int)(u==2)+(v==2)+(w==2));
chmn(val,dfs(A-(A_&&u!=1),B-(B_&&v!=1),C-(C_&&w!=1),CAR,A_,B_,C_)+_1*I+_2*R);
}
}
// printf("%d,%d,%d|%d|%d,%d,%d:%d\n",A,B,C,car,a_,b_,c_,val);
return val;
}
public:
int minCost(int aa,int bb,int cc,int II,int DD,int RR){
a=aa,b=bb,c=cc,I=II,D=DD,R=RR;
while(a)_a[_A++]=a%10,a/=10;_a[_A]=0;
while(b)_b[_B++]=b%10,b/=10;_b[_B]=0;
while(c)_c[_C++]=c%10,c/=10;_c[_C]=0;
memset(f,-1,sizeof(f));
f[0][0][0][0][1][1][1]=0;
return dfs(_A,_B,_C,0,0,0,0);
}
}my;
VII.CF776G Sherlock and the Encrypted Data
考虑一个数 \(x\)：其对应的和是一个非零数（除了零这个特例，但是我们手动判掉零）。一个数异或一个非零数后的大小变化，端看该非零数的最高位：假如在最高位上，被异或的数是零则变大，否则则变小。
那么我们就可以计数了。钦定这个数中出现的最大位是 \(x\)，然后计数在第 \(x\) 位上为 \(1\)、出现的数全部不超过 \(x\)、\(x\) 至少出现一次的数的数量即可。可以简单 DP 求解。
具体而言，设 \(f_{i,0/1,0/1}\) 表示：当前 DP 到了第 \(i\) 个 二进制位，该二进制位对应的 十六进制位 能否与枚举的字符对应，之前是否已经存在与该十六进制位对应的位。转移是简单的。
单次询问复杂度 \(O(16\times \log V)\)，带若干个二的常数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int q;
ll L,R,X,f[16][60][2][2],ans;
ll dfs(int cha,int pos,bool cur,bool occ,bool lim){
if(pos==-1)return occ;
if(!lim&&f[cha][pos][cur][occ]!=-1)return f[cha][pos][cur][occ];
ll res=0;
for(int i=0;i<=(lim?((X>>pos)&1):1);i++){
if(pos==cha&&i==0)continue;
bool CUR=cur&&(i==((cha>>(pos&3))&1));
if(cur&&!CUR&&i)continue;
bool OCC=occ||(!(pos&3)&&CUR);
if(!(pos&3))CUR=true;
res+=dfs(cha,pos-1,CUR,OCC,lim&&(i==((X>>pos)&1)));
}
// if(res)printf("%d,%d,%d,%d,%d:%d\n",cha,pos,cur,occ,lim,res);
if(!lim)f[cha][pos][cur][occ]=res;
return res;
}
void mina(){
scanf("%llx%llx",&L,&R);if(L)L--;ans=0;
X=R;for(int i=1;i<16;i++)ans+=dfs(i,59,true,false,true);
X=L;for(int i=1;i<16;i++)ans-=dfs(i,59,true,false,true);
printf("%lld\n",ans);
}
int main(){
memset(f,-1,sizeof(f));
scanf("%d",&q);
while(q--)mina();
return 0;
}
VIII.CF756F Long number
IX.[SDOI/SXOI2022] conversion
X.[HDU7241]Simple Math 4
首先盲猜一个盲猜，未贴到 \(R\) 的元素不会很多，具体而言仅有 \(O(\log R)\) 个。一个感性证明是线性基的大小是对数的，故只需 \(\log R\) 个元素即可组合出一切方案；一个理性证明是考虑任一组异或和恰为 \(X\) 的方案，若其中非贴 \(R\) 的元素超过 \(\log\) 个，由抽屉原理则必然有至少两个元素后缀的一数量相同，进而同时加一不改变异或和。不断调整，最终得到非贴 \(R\) 的元素仅有 \(\log R\) 个。
紧接着就可以设计 DP 了。令 \(f_{i,j,k}\) 为当前处理到第 \(i\) 位，其中有 \(j\) 个元素贴 \(L\)、\(k\) 个元素贴 \(R\) 的方案数。转移暴力枚举 \(j,k\) 有多少元素不再贴着界，复杂度 \(O(\log^5R)\)。
优化可以用二维前缀和优化，这样复杂度变为 \(O(\log^3R)\)。代码偷懒写的是 \(O(\log^4R)\) 的。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll fni=0xc0c0c0c0c0c0c0c0;
int n,L,R,X,m;
ll f[40][40][40],res;
ll g[40][40][2];
void chmx(ll&x,ll y){if(x<y)x=y;}
void mina(){
scanf("%d%d%d%d",&n,&L,&R,&X);
for(m=0;(1<<m)<=R;m++);m++;
m=min(m,n);
if((n-m)&1)m++;
int LG=31;
while(LG>=0&&((L>>LG)&1)==((R>>LG)&1))LG--;
if((n&1)&&(R>>(LG+1))!=(X>>(LG+1))){puts("-1");return;}
if(!(n&1)&&(X>>(LG+1))){puts("-1");return;}
if(LG==-1){printf("%lld\n",1ll*R*n);return;}
memset(f,0xc0,sizeof(f)),res=fni;
for(int i=0;i<=LG-1;i++)for(int j=0;j<=m;j++)for(int k=0;j+k<=m;k++){
if(((L>>i)&1)||!((R>>i)&1)){
for(int J=0;J<=(((L>>i)&1)?0:j);J++)for(int K=0;K<=(!((R>>i)&1)?0:k);K++){
int num=(((L>>i)&1)?(j-J):J)+(!((R>>i)&1)?K:k-K);
if((num&1)==((X>>i)&1))
chmx(f[i][j][k],(!i?0:f[i-1][j-J][k-K])+(1ll<<i)*(num+(m-j-k-((m-j-k)&1))));
else if(j+k!=m)
chmx(f[i][j][k],(!i?0:f[i-1][j-J][k-K])+(1ll<<i)*(num+(m-j-k-!((m-j-k)&1))));
}
}else{
g[j][k][k&1]=(!i?0:f[i-1][j][k])+(1ll<<i)*k;
g[j][k][!(k&1)]=fni;
if(k)for(int _=0;_<2;_++)chmx(g[j][k][_],g[j][k-1][_]);
if(j)for(int _=0;_<2;_++)chmx(g[j][k][_],g[j-1][k][!_]+(1<<i));
for(int _=0;_<2;_++){
if(_==((X>>i)&1))
chmx(f[i][j][k],g[j][k][_]+(1ll<<i)*((m-j-k-((m-j-k)&1))));
else if(j+k!=m)
chmx(f[i][j][k],g[j][k][_]+(1ll<<i)*((m-j-k-!((m-j-k)&1))));
}
}
// if(f[i][j][k]>=0)printf("<%d,%d,%d>:%d\n",i,j,k,f[i][j][k]);
}
// printf("<%d>\n",LG);
for(int i=((X>>LG)&1);i<=m;i+=2)chmx(res,(!LG?0:f[LG-1][m-i][i])+(1ll<<LG)*i);
if(res<0){puts("-1");return;}
res+=1ll*(n-m)*R;
res+=1ll*((R>>(LG+1))<<(LG+1))*m;
printf("%lld\n",res);
}
int T;
int main(){scanf("%d",&T);while(T--)mina();return 0;}
XI.CF1734F Zeros and Ones
有个家伙连 2500 的题都做不出来了。
一个显然的想法是递归处理。但是实际实现后发现效果很糟糕。
事实上，直接数位 DP 即可：
我们要求 \(\sum\limits_{i=0}^{m-1}\text{popcount-parity}(i\operatorname{xor}(i+n))\)。关于 \(m\) 直接按位处理即可。要记录 \(i+n\) 是否有进位。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll f[62][2][2][2];
ll DP(int pos,bool par,bool car,bool lim){
if(pos==-1)return par&&!car;
ll&res=f[pos][par][car][lim];if(res!=-1)return res;res=0;
for(int i=0;i<=(lim?(m>>pos)&1:1);i++)for(int j=0;j<2;j++)
if(((((n>>pos)&1)+i+j)>=2)==car)
res+=DP(pos-1,par^((n>>pos)&1)^j,j,lim&&(i==((m>>pos)&1)));
return res;
}
int T;
void mina(){
scanf("%lld%lld",&n,&m),m--;
memset(f,-1,sizeof(f));
printf("%lld\n",DP(61,false,false,true));
}
int main(){
scanf("%d",&T);
while(T--)mina();
return 0;
}
XII.签到
对满足如下条件的 \(n\) 元整数组 \(a\) 模 \(998244353\) 计数：
- \(0\leq a_i\leq b^i-c\)。
- \(\sum a_i<m\)。
数据范围：\(2\leq b\leq10^8,-10^8\leq c\leq b,n\leq80,m\leq b^{n+1}\)。
假如 \(c\) 是正数，那么考虑 \(b^i-c\) 的 \(b\) 进制表达，就能发现除了最低位会受到影响以外，更高位的影响是不显著的。同时，全部最低位的和不超过 \(80b\)，于是我们可以令 \(f(i,j)\) 表示：
- 更高位的元素和距离 \(m\) 的上界差是 \(ib\)（\(i\) 与 \(n\) 取 \(\min\)）。
- 更高位的元素共有 \(j\) 个贴到了上限（最低位仅能填 \(c-b\)）。
这个可以简单数位 DP 求出。求完后对于最低位就要解决 \(O(n)\) 个如下的问题：
- 有 \(n\) 个数，其中 \(n'\) 个数的限制是 \(\leq x\)，\(n-n'\) 个数的限制是 \(\leq y\)，要求和 \(\leq L\) 的方案数。
简单容斥，将问题转化成 \(n\) 个非负数和 \(\leq L'\) 的方案数。是列上二项式系数求和的形式，简单转化成二项式系数单点求值，因为要求的 \(\dbinom ab\) 中 \(b\) 很小（\(O(n)\) 级别）所以直接 \(O(n)\) 算即可。
分析一下复杂度：要枚举多少个取 \(>x\)，多少个取 \(>y\)，外面还有 \(f(i,j)\) 要枚举，单个组合数又要 \(O(n)\) 算……复杂度 \(O(n^5)\)。
但是对于不同的 \((i,j)\)，\(x,y\) 的值总是相同的；\(i\) 固定时，\(L\) 也是固定的；因此 \(i\) 固定时的全体组合数可以 \(O(n^3)\) 求出，复杂度就变成了 \(O(n^4)\)。
那么 \(c\) 是负数又应该怎么办呢？答案是把最低 \(\log_b-c\) 位单独摘出来，限制是低位的元素小于等于 \(b^{\left\lceil\log_bc\right\rceil}-c\) 然后高位就看有没有贴上界即可。
但是这就引发了一个新问题：最低的 \(\log_b-c\) 位，每一位的值都不一样，就算你尝试容斥也没法枚举每一位要不要容斥。
尝试换一种写法。
首先解决这样一个问题：\(n\) 个非负数和不超过 \(m\) 有多少种方法？
\[\sum\limits_{x=0}^m\dbinom{m+n-1}{n-1}=\dbinom{m+n}{n} \]于是在本题中，先把 \(m\) 增加 \(n-1\)（因为本题中的 \(m\) 是小于）然后容斥：枚举集合 \(\mathbb S\)，则要计数
\[\sum\limits_{\mathbb S}(-1)^{|\mathbb S|}\dbinom{m+(c-1)|\mathbb S|-\sum\limits_{i\in\mathbb S}b^i}{n} \]令 \(A=m+(c-1)|\mathbb S|\)，则若 \(A\geq\sum\limits_{i\in\mathbb S}b^i\) 则其是关于 \(\sum\limits_{i\in\mathbb S}b^i\) 的 \(n\) 次多项式。这意味着我们可以尝试维护多项式。
枚举 \(|\mathbb S|\) 固定 \(A\)。\(A\) 固定后令其对应多项式是 \(f(\sum b)\)，然后就只需对于每个 \(k\) 都求出 \(\sum\limits_{\mathbb S}(\sum\limits_{i\in\mathbb S}b^i)^k\) 了。这个仍然可以从上往下 DP，即枚举当前东西与 \(A\) 间差多少个 \(b\)（事实上，仅能是零个或一个，因为更低位一共也不会产生多于一个 \(b\)），并处理 \(\sum b\) 的影响。
大力实现，要枚举 \(|\mathbb S|\)，然后内层要枚举当前位、差几个 \(b\)（这个是 \(O(1)\) 的）、选了几个 \(b\)、当前的幂次和，然后转移是卷积，复杂度 \(O(n^5)\)，会被卡掉。
优化到 \(O(n^4)\) 就预处理 DP 然后每次枚举首次与 \(A\) 差 \(1\) 的位置即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
typedef long long ll;
int n,b,c,S,m,LG,res;
char s[1010];
ll a[150];
//i:position i from above.
//j:j from the upper bound.
//k:choose k elements at all.
//l:the sum of l-th powers.
int f[90][90][90];
bool ADD(ll val){
a[0]+=val;
for(int i=0;i<m;i++){
a[i+1]+=a[i]/b,a[i]%=b;
if(a[i]<0)a[i]+=b,a[i+1]--;
}
if(a[m]<0)return false;
while(a[m])a[m+1]+=a[m]/b,a[m]%=b,m++;
while(m&&!a[m-1])m--;
return true;
}
int lam[150],fac[150],inv[150];
void gene(int _){
memset(lam,0,sizeof(lam));
lam[0]=1;
int V=0;
for(int i=m-1;i>=0;i--)V=(1ll*V*b+a[i])%mod;
// printf("<%d>\n",V);
for(int i=0;i<n;i++)for(int j=i;j>=0;j--)
(lam[j+1]+=mod-lam[j])%=mod,
lam[j]=1ll*lam[j]*(V+mod-i)%mod;
for(int i=0;i<=n;i++)lam[i]=1ll*lam[i]*inv[n]%mod;
}
int pov[150];
int C[150][150];
int main(){
freopen("checkin.in","r",stdin);
freopen("checkin.out","w",stdout);
scanf("%d%d%d%s",&n,&b,&c,s),S=strlen(s),reverse(s,s+S);
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n]);for(int i=n;i;i--)inv[i-1]=1ll*inv[i]*i%mod;
pov[0]=1;for(int i=1;i<=n;i++)pov[i]=1ll*pov[i-1]*b%mod;
for(int i=0;i<=n;i++)C[i][0]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
for(int i=0;i<S;i++)s[i]-='0';
while(S){
int rem=0;
for(int i=S-1;i>=0;i--){
rem=10*rem+s[i];
s[i]=rem/b,rem%=b;
}
while(S&&!s[S-1])S--;
a[m++]=rem;
}
f[0][0][0]=1;
for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++){
f[i][j][k]=f[i-1][j][k];
for(int p=0,q=1;p<=k;p++,q=1ll*q*pov[i]%mod)
f[i][j][k]=(1ll*q*f[i-1][j-1][k-p]%mod*C[k][p]+f[i][j][k])%mod;
}
ADD(n-1);
for(int _=0;_<=n;_++){
// printf("%d:",_);
// for(int i=0;i<m;i++)printf("%d ",a[i]);puts("");
gene(_);
int now=0;
int sum=0,num=0;
if(m>n+1)
for(int i=0;i<=n;i++)now=(1ll*lam[i]*f[n][_][i]+now)%mod;
else{
for(int i=n;;i--){
if(!i||a[i]>=2){
for(int j=0;j<=n;j++)
for(int p=0,q=1;p<=j;p++,q=1ll*q*sum%mod)
now=(1ll*lam[j]*f[i][_-num][j-p]%mod*q%mod*C[j][p]+now)%mod;
sum=num=-1;
break;
}
if(!a[i])continue;
for(int j=0;j<=n;j++)
for(int p=0,q=1;p<=j;p++,q=1ll*q*sum%mod)
now=(1ll*lam[j]*f[i-1][_-num][j-p]%mod*q%mod*C[j][p]+now)%mod;
(sum+=pov[i])%=mod,num++;
if(num>_){sum=num=-1;break;}
}
if(sum!=-1&&num!=-1){
for(int j=0;j<=n;j++)
for(int p=0,q=1;p<=j;p++,q=1ll*q*sum%mod)
now=(1ll*lam[j]*f[0][_-num][j-p]%mod*q%mod*C[j][p]+now)%mod;
}
}
// for(int i=0;i<=n;i++)printf("%d ",f[n][m>n+1][_][i]);puts("");
// for(int i=0;i<=n;i++)printf("%d ",lam[i]);puts("");
if(_&1)(res+=mod-now)%=mod;else(res+=now)%=mod;
// printf("%d\n",now);
if(!ADD(c-1))break;
}
printf("%d\n",res);
return 0;
}
II.字典序 DP
与字典序或类似事物上贪心有关的 DP 归在此处。
I.[HAOI2010]计数
我不得不吐槽出题人的语文实在太……那个了。
翻译一下：给你一个数，求它是全排列中第几个。
为什么呢？我们看一下给定的那个\(\{1,2\}\)的例子。显然，在任何合法的数中，所有的非零数的出现次数，在每个数中都是相同的。如果我们允许前导零，那么所有的\(0\)的出现次数也都相同了。（删去\(0\)可以看作将\(0\)移到了开头）
我们考虑借鉴数位DP的思想：从高位向低位枚举，并考虑当前这位填入比原数小的数还是和原数相同的数。
如果填入一个比它小的数，那么后面的位就可以全排列了。
考虑每个数\(i\)共出现了\(cnt_i\)次，所有数总共出现了\(tot\)次。
数字\(0\)可以在这\(tot\)个位置里面随便填，共\(C_{tot}^{cnt_0}\)种方案。
数字\(1\)可以在剩下\(tot-cnt_0\)个位置里面随便填，共\(C_{tot-cnt_0}^{cnt_1}\)种方案。
以此类推。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,num[100],cnt[10],C[100][100],res;
char s[100];
int calc(int tot){
int ans=1;
for(int i=0;i<10;i++)ans*=C[tot][cnt[i]],tot-=cnt[i];
return ans;
}
signed main(){
scanf("%s",s+1),n=strlen(s+1);
for(int i=0;i<=n;i++)C[i][0]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
// for(int i=0;i<=n;i++){for(int j=0;j<=i;j++)printf("%d ",C[i][j]);puts("");}
for(int i=1;i<=n;i++)num[i]=s[i]-'0',cnt[num[i]]++;
for(int i=1;i<=n;i++){
for(int j=0;j<num[i];j++){
if(!cnt[j])continue;
cnt[j]--;
res+=calc(n-i);
cnt[j]++;
}
cnt[num[i]]--;
}
printf("%lld\n",res);
return 0;
}
II.[USACO18DEC]Sort It Out P
集合中的数一定是某一条LIS的补集，这点还是比较好想的。
我们要集合的字典序最小，就是让集合的补集的字典序最大。
最大就可以考虑按位处理LIS中的数。
我们从后往前求LIS。我们设\(f[i]\)表示以当前位置开头的LIS的长度以及数量（类型是一个pair）。\(f[i]\)可以直接套BIT解决。
然后，对于每个\(k\)，我们将所有长度为\(k\)的位置丢到一个vector里面，即为确定序列正数第\(k\)位时的过程；然后从小往大遍历这些位置。就是正常的求第\(k\)大的常规思路。
注意，因为是LIS，当你将一个数选入序列后，所有比它小的位置都不能再选了！！！
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,ll>
#define X first
#define Y second
#define mp make_pair
#define O mp(0,0)
const ll lim=1e18;
int n,a[100100],len;
bool on[100100];
pii f[100100],t[100100];
void operator +=(pii &x,const pii &y){
if(x.X<y.X)x=y;
else if(x.X==y.X)x.Y=min(lim,x.Y+y.Y);
}
void ADD(int x,pii y){while(x)t[x]+=y,x-=x&-x;}
pii ASK(int x){pii ret=O;while(x<=n)ret+=t[x],x+=x&-x;return ret;}
ll m;
vector<int>v[100100];
int main(){
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
ADD(n,mp(0,1));
for(int i=n;i;i--)f[i]=ASK(a[i]),f[i].X++,ADD(a[i],f[i]),len=max(len,f[i].X),v[f[i].X].push_back(i);
printf("%d\n",n-len);
for(int i=len,k=1;i;i--){
reverse(v[i].begin(),v[i].end());
for(auto j:v[i]){
if(f[j].Y<m)m-=f[j].Y;
else{
on[a[j]]=true;
while(k<j)f[k++]=O;
break;
}
}
}
for(int i=1;i<=n;i++)if(!on[i])printf("%d\n",i);
return 0;
}
III.CF938F Erasing Substrings
一个naive的想法是设\(f_{i,j}\)表示在位置\([1,i]\)中，我们删去了长度为\(2^k(k\in j)\)的一些串，所能得到的最小字典序。使用二分+hash可以做到\(O(n^2\log^2 n)\)，无法承受。
发现对于状态\(f_{i,j}\)，它已经确定了\(i-j\)位的串（因为所有\(\in j\)的\(2^k\)之和就是\(j\)）；而依据字典序的性质，只有这\(i-j\)位所表示的字典序最小的那些状态，才会成为最终的答案。（当然，前提是状态\(f_{i,j}\)合法，即剩下的部分中可以安放下尚未被删去的串）
于是我们就可以考虑直接令\(f_{i,j}\)表示在所有长度为\(i-j\)的串中，它是否是字典序最小的串之一；然后，就可以按照\(i-j\)递增的顺序进行DP。你自然可以倒着复原出路径，但是更好的方法是在DP第\(i-j\)位的时候，当我们找出了这位最小能填入什么字符后，直接输出。
下面我们考虑转移。一种情况是\(f_{i,j}\rightarrow f_{i+1,j}\)，此时是第\(i+1\)位被保留下来，因此这个转移的前提是第\(i+1\)位上可以填入最小的字符；
还有一种情况就是第\(i+1\)位被删去，于是我们枚举\(k\notin j\)，直接转移即可。
注意到代码实现与此处描述有一些区别——描述中的递推式是刷表法，而代码中的递推式是填表法；同时，代码中的DP顺序上文已经提到，是\(i-j\)递增的顺序。
#include<bits/stdc++.h>
using namespace std;
int n,m,all;
bool f[5010][5010];//f[i][j]:after erasing strings in j from the section [1,i-1], whether the (i-j) prefix can be the minimum or not
char s[5010];
int main(){
scanf("%s",s+1),n=strlen(s+1);
while((2<<m)<=n)m++;all=(1<<m);
for(int i=0;i<all;i++)f[i][i]=true;//initial state:erasing all i characters in the prefix
for(int i=1;i<=n-all+1;i++){
char lim=127;
for(int j=i;j<i+all;j++)if(f[j-1][j-i])lim=min(lim,s[j]);//find the minimum on the (i+1)-th character
putchar(lim);
for(int j=i;j<i+all;j++)f[j][j-i]=(f[j-1][j-i]&&(s[j]==lim));//leave j+1 empty
for(int j=i;j<i+all;j++)for(int k=0;k<m;k++)if((j-i)&(1<<k))f[j][j-i]|=f[j-(1<<k)][j-i-(1<<k)];//put something on j+1
}
return 0;
}
IV.CF1542E2 Abnormal Permutation Pairs (hard version)
两个限制：字典序小、逆序对大，一个显然的想法就是确保一对关系，统计另一对关系。
确保哪一对呢？我们想了想，决定确保字典序小，因为字典序是可以贪心的。
具体而言，我们考虑两个排列自第 \(i\) 位开始出现了不同。这样子，我们便将两个排列各自划成两段，即 \([1,i-1]\) 与 \([i,n]\)。则两排列的第一段是相同的。
考虑借鉴CDQ分治的思想，将逆序对分为三类，即首段中、末段中、两段间。因为两排列首段相同，所以首段中的逆序对数相等；因为两排列中每一段的组成元素相同，所以两段间的逆序对数亦相等；有区别的只有末端中的逆序对数。
于是，我们考虑枚举这个 \(i\)，则前 \(i-1\) 位就有 \(n^{\underline{i-1}}\) 种取值方案。
我们还剩下 \(n-i+1\) 个互不相同的数。因为逆序对仅与大小关系相关，所以我们完全可以将其映射作一个长度为 \(n-i+1\) 的排列而不改变逆序对数。
现在考虑枚举第 \(i\) 位两个排列分别填了什么。设排列 \(p\) 填了 \(j\)（实际上是剩余数中第 \(j\) 小的数），\(q\) 填了 \(k\)（同理，实质是第 \(k\) 小的数），则要满足字典序限制则应有 \(j<k\)。\(j\) 对后面元素贡献了 \(j-1\) 个逆序对，\(k\) 对后面元素贡献了 \(k-1\) 个逆序对，则现在 \(p\) 比 \(q\) 少了 \(k-j\) 个逆序对。
因为后 \(n-i\) 位以后就可以随便填了，所以我们就设一个DP \(f_{i,j}\) 表示长度为 \(i\) 的排列出现 \(j\) 个逆序对的方案数。枚举数字 \(i\) 填哪里就可以做到 \(n^4\)，用前缀和/差分优化就能做到 \(n^3\)，过于基础不再赘述。
现在回到 \(p\) 填 \(j\)、\(q\) 填 \(k\) 的情形。则，\(p\) 要保证后 \(n-i\) 位中逆序对数至少比 \(q\) 多 \(k-j+1\) 个才能满足逆序对的限制。
考虑枚举 \(i,j,k\) 以及 \(p,q\) 在后 \(n-i\) 位中逆序对数分别是 \(J,K\)，可以做到垃圾的 \(n^7\) 复杂度；
但注意到我们对于同样的 \(J-K\) 只关心 \(k-j+1\)，于是我们仅枚举 \(J,K\)，再预处理出此时合法的 \(j,k\) 对数，就能做到 \(n^5\)；
假如再观察到 \(j-k+1\) 最大只到 \(n-i\)，这样 \(J-K\) 在大于 \(n-i\) 后，对于再之前的所有 \(K\) 来说合法的 \(j,k\) 对数便会一直相等，这样枚举 \(K\) 时就只用枚举 \(J\) 之前的 \(n-i\) 个位置，之前的用一个前缀和就能解决，这样就能做到 \(n^4\)；
优化到正解 \(n^3\) 的做法是考虑 \(J\) 增加时，对于不同的 \(K\) 来说 \(j-k\) 数对的增量是什么；然后发现这一增量在 \(J-K=2\) 时是 \(n-i\)，\(=3\) 时是 \(n-i-1\)……\(=k\) 时是 \(n-i-k+2\)。放到平面直角坐标系上就是一个三角形的形式，可以通过预处理 \(f_{i,j}\) 数组的前缀和以及 \(j\times f_{i,j}\) 的前缀和来 \(O(1)\) 求出。
细节很多，详见代码。
#include<bits/stdc++.h>
using namespace std;
int n,mod,com[510],f[125100],fac[510],s[125100],t[125100],C[510][510],d[510],res;
int main(){
scanf("%d%d",&n,&mod);
for(int i=1;i<=n;i++)com[i]=i*(i-1)/2;
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(int i=0;i<=n;i++)C[i][0]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
f[0]=1;
for(int i=0;i<n;i++){
for(int j=1;j<=com[i];j++)(f[j]+=f[j-1])%=mod;f[com[i]+1]=0;
// for(int j=0;j<=com[i];j++)printf("%d ",f[j]);puts("");
for(int j=0;j<=i;j++)d[j]=0;
for(int J=0;J<=i;J++)for(int K=J+1;K<=i;K++)d[K-J]++;
for(int j=1;j<=i;j++)d[j]+=d[j-1];
// for(int j=0;j<=i;j++)printf("%d ",d[j]);puts("");
for(int j=0;j<=com[i];j++)s[j]=f[j],t[j]=1ll*f[j]*j%mod;
for(int j=1;j<=com[i];j++)(s[j]+=s[j-1])%=mod,(t[j]+=t[j-1])%=mod;
for(int j=2,k=0;j<=com[i];j++){
if(j>i)(res+=1ll*d[i]*fac[n-i-1]%mod*C[n][n-i-1]%mod*f[j]%mod*s[j-i-1]%mod)%=mod,(k+=mod-1ll*f[j-i-1]*d[i]%mod)%=mod;
(k+=(0ll+t[j-2]+mod-1ll*(j-i-2)*s[j-2]%mod)%mod)%=mod;
if(j-1>i)(k+=(2ll*mod-t[j-i-2]+1ll*(j-i-2)*s[j-i-2]%mod)%mod)%=mod;
(res+=1ll*C[n][n-i-1]*fac[n-i-1]%mod*f[j]%mod*k%mod)%=mod;
}
for(int j=com[i];j>=0;j--)(f[j+i+1]+=mod-f[j])%=mod;
// puts("");
}
printf("%d\n",res);
return 0;
}
III.区间 DP
区间 DP 归在此处。
I.[SCOI2003]字符串折叠
一眼区间DP。
设\(f[i][j]\)表示：将区间\([i,j]\)内的所有东西压一起的最短长度。
显然，有两种方法：
1.在中间一刀劈开，然后拼一起。
2.找到它的循环节，然后把整个串压一起。
至于找循环节吗……枚举循环节长度，然后无脑哈希一下。
注意，你可能会压出类似于\(10(AB)\)这种东西，记得\(10\)是两位数！！！
代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
ull val1,val2;
int len;
HASH(){
val1=val2=0ull;
len=0;
}
HASH(char ip){
val1=val2=ip;
len=1;
}
friend HASH operator +(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1*pov1[y.len]+y.val1;
z.val2=x.val2*pov2[y.len]+y.val2;
z.len=x.len+y.len;
return z;
}
friend HASH operator -(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1-y.val1*pov1[x.len-y.len];
z.val2=x.val2-y.val2*pov2[x.len-y.len];
z.len=x.len-y.len;
return z;
}
friend bool operator ==(const HASH &x,const HASH &y){
if(x.len!=y.len)return false;
if(x.val1!=y.val1)return false;
if(x.val2!=y.val2)return false;
return true;
}
}hs[110];
int calc(int x){
int res=0;
while(x)res++,x/=10;
return res;
}
int main(){
scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
pov1[0]=pov2[0]=1;
for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
for(int i=1;i<=n;i++)hs[i]=hs[i-1]+HASH(s[i]),f[i][i]=1;
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for(int k=1;k<l;k++){
if(l%k)continue;
if((hs[j]-hs[i+k-1])==(hs[j-k]-hs[i-1]))f[i][j]=min(f[i][j],f[i][i+k-1]+2+calc(l/k));
}
}
}
// for(int i=1;i<=n;i++){for(int j=i;j<=n;j++)printf("%d ",f[i][j]);puts("");}
printf("%d\n",f[1][n]);
return 0;
}
II.[SCOI2007]压缩
这种DP状态需要考虑到各种状态的题最讨厌了……
思路1.设\(f[i][j]\)表示将区间\([i,j]\)里面所有东西压一起的最小代价
有两种转移：
-
砍成两段拼一起
-
样例里面这种方法，
MaRR=aaaa这种倍增法
然后我就写出了这样的代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
ull val1,val2;
int len;
HASH(){
val1=val2=0ull;
len=0;
}
HASH(char ip){
val1=val2=ip;
len=1;
}
friend HASH operator +(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1*pov1[y.len]+y.val1;
z.val2=x.val2*pov2[y.len]+y.val2;
z.len=x.len+y.len;
return z;
}
friend HASH operator -(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1-y.val1*pov1[x.len-y.len];
z.val2=x.val2-y.val2*pov2[x.len-y.len];
z.len=x.len-y.len;
return z;
}
friend bool operator ==(const HASH &x,const HASH &y){
if(x.len!=y.len)return false;
if(x.val1!=y.val1)return false;
if(x.val2!=y.val2)return false;
return true;
}
friend bool operator !=(const HASH &x,const HASH &y){
return !(x==y);
}
}hs[110];
bool che(int ip){
return ip==(ip&-ip);
}
int main(){
scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
pov1[0]=pov2[0]=1;
for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
for(int i=1;i<=n;i++)hs[i]=hs[i-1]+HASH(s[i]),f[i][i]=1;
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for(int k=1;k<l;k++){
if(l%k)continue;
if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
if(!che(l/k))continue;
// printf("%d %d %d\n",i,j,l/k);
f[i][j]=min(f[i][j],f[i][i+k-1]+__builtin_ctz(l/k)+(i!=1));
}
}
}
// for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
printf("%d\n",f[1][n]);
return 0;
}
一交，WA，\(40\%\)。
怎么回事？
我费尽千辛万苦，找到一组hack数据：
xabababababab
按照我之前的这种压法，会压出来xMMabRabR这种东西。因为这时区间DP，按照我之前的思路，是按照括号的顺序压的：
x(M(MabR)abR)
因此，相同的左端点，如果已经有了一个M，就不用重复有M了。
我们设一个新状态\(f[i][j][0/1]\)表示：将区间\([i,j]\)压一起，左端点有无M的状态是\([0/1]\)。
然后写出来这样的东西：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
ull val1,val2;
int len;
HASH(){
val1=val2=0ull;
len=0;
}
HASH(char ip){
val1=val2=ip;
len=1;
}
friend HASH operator +(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1*pov1[y.len]+y.val1;
z.val2=x.val2*pov2[y.len]+y.val2;
z.len=x.len+y.len;
return z;
}
friend HASH operator -(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1-y.val1*pov1[x.len-y.len];
z.val2=x.val2-y.val2*pov2[x.len-y.len];
z.len=x.len-y.len;
return z;
}
friend bool operator ==(const HASH &x,const HASH &y){
if(x.len!=y.len)return false;
if(x.val1!=y.val1)return false;
if(x.val2!=y.val2)return false;
return true;
}
friend bool operator !=(const HASH &x,const HASH &y){
return !(x==y);
}
}hs[110];
bool che(int ip){
return ip==(ip&-ip);
}
int main(){
scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
pov1[0]=pov2[0]=1;
for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
for(int i=1;i<=n;i++){
hs[i]=hs[i-1]+HASH(s[i]);
f[i][i][0]=1;
f[i][i][1]=1+(i!=1);
}
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
for(int k=i;k<j;k++)f[i][j][0]=min(f[i][j][0],f[i][k][0]+min(f[k+1][j][0],f[k+1][j][1])),f[i][j][1]=min(f[i][j][1],f[i][k][1]+min(f[k+1][j][0],f[k+1][j][1]));
for(int k=1;k<l;k++){
if(l%k)continue;
if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
if(!che(l/k))continue;
// printf("%d %d %d\n",i,j,l/k);
f[i][j][1]=min(f[i][j][1],min(f[i][i+k-1][0]+1,f[i][i+k-1][1])+__builtin_ctz(l/k));
}
}
}
// for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
printf("%d\n",f[1][n][1]);
return 0;
}
//xabababababab
一交，WA，\(70\%\)。
然后我想了想，那种倍增的合并法也可以并入（左端点已经有了M）的情形。
然后我改成了这样的代码（这种情形实际上哈希都没必要了）
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
ull val1,val2;
int len;
HASH(){
val1=val2=0ull;
len=0;
}
HASH(char ip){
val1=val2=ip;
len=1;
}
friend HASH operator +(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1*pov1[y.len]+y.val1;
z.val2=x.val2*pov2[y.len]+y.val2;
z.len=x.len+y.len;
return z;
}
friend HASH operator -(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1-y.val1*pov1[x.len-y.len];
z.val2=x.val2-y.val2*pov2[x.len-y.len];
z.len=x.len-y.len;
return z;
}
friend bool operator ==(const HASH &x,const HASH &y){
if(x.len!=y.len)return false;
if(x.val1!=y.val1)return false;
if(x.val2!=y.val2)return false;
return true;
}
friend bool operator !=(const HASH &x,const HASH &y){
return !(x==y);
}
}hs[110];
int main(){
scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
pov1[0]=pov2[0]=1;
for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
for(int i=1;i<=n;i++){
hs[i]=hs[i-1]+HASH(s[i]);
f[i][i][0]=1;
f[i][i][1]=1+(i!=1);
}
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
for(int k=i;k<j;k++)f[i][j][0]=min(f[i][j][0],f[i][k][0]+min(f[k+1][j][0],f[k+1][j][1])),f[i][j][1]=min(f[i][j][1],f[i][k][1]+min(f[k+1][j][0],f[k+1][j][1]));
if(l&1)continue;
int k=l>>1;
if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
f[i][j][1]=min(f[i][j][1],min(f[i][i+k-1][0]+1,f[i][i+k-1][1])+1);
}
}
// for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
printf("%d\n",f[1][n][1]);
return 0;
}
//xabababababab
//xabcabcxabcabc
一交，WA，还是\(70\%\)。
我费劲千辛万苦，终于找到另一组hack数据：
xabcabcxabcabc
按照我之前的思路，会压出来这样的东西：
xMabcRR
因为我的程序是这样考虑的：
x(MabcR)R，根本没有考虑内部的情况
因此还要额外再加一维，表示该串内部有无M：
我们现在得到的是状态\(f[i][j][0/1][0/1]\)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
ull val1,val2;
int len;
HASH(){
val1=val2=0ull;
len=0;
}
HASH(char ip){
val1=val2=ip;
len=1;
}
friend HASH operator +(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1*pov1[y.len]+y.val1;
z.val2=x.val2*pov2[y.len]+y.val2;
z.len=x.len+y.len;
return z;
}
friend HASH operator -(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1-y.val1*pov1[x.len-y.len];
z.val2=x.val2-y.val2*pov2[x.len-y.len];
z.len=x.len-y.len;
return z;
}
friend bool operator ==(const HASH &x,const HASH &y){
if(x.len!=y.len)return false;
if(x.val1!=y.val1)return false;
if(x.val2!=y.val2)return false;
return true;
}
friend bool operator !=(const HASH &x,const HASH &y){
return !(x==y);
}
}hs[110];
int main(){
scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
pov1[0]=pov2[0]=1;
for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
for(int i=1;i<=n;i++){
hs[i]=hs[i-1]+HASH(s[i]);
f[i][i][0][0]=1;
f[i][i][1][0]=1+(i!=1);
}
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
for(int k=i;k<j;k++){
f[i][j][0][0]=min(f[i][j][0][0],f[i][k][0][0]+f[k+1][j][0][0]);
f[i][j][1][0]=min(f[i][j][1][0],f[i][k][1][0]+f[k+1][j][0][0]);
f[i][j][0][1]=min(f[i][j][0][1],min(f[i][k][0][1],f[i][k][0][0])+min(min(f[k+1][j][0][0],f[k+1][j][0][1]),min(f[k+1][j][1][0],f[k+1][j][1][1])));
f[i][j][1][1]=min(f[i][j][1][1],min(f[i][k][1][1],f[i][k][1][0])+min(min(f[k+1][j][0][0],f[k+1][j][0][1]),min(f[k+1][j][1][0],f[k+1][j][1][1])));
}
if(l&1)continue;
int k=l>>1;
if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
f[i][j][1][0]=min(f[i][j][1][0],min(f[i][i+k-1][0][0]+1,f[i][i+k-1][1][0])+1);
}
}
// for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
printf("%d\n",min(f[1][n][1][0],f[1][n][1][1]));
return 0;
}
//xabababababab
//xabcabcxabcabc
III.[HAOI2008]玩具取名
状压一下。
我们令\(f[i][j]\)为：区间\([i,j]\)的串，能转移到字母的状态（是个 bitmask ）
至于转移吗……劈开拼一起即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int m[4],n,tr[4][4],f[210][210];
int tran(char ip){
if(ip=='W')return 0;
if(ip=='I')return 1;
if(ip=='N')return 2;
if(ip=='G')return 3;
}
char s[210];
int main(){
for(int i=0;i<4;i++)scanf("%d",&m[i]);
for(int i=0;i<4;i++)for(int j=0;j<m[i];j++)scanf("%s",s),tr[tran(s[0])][tran(s[1])]|=(1<<i);
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<=n;i++)f[i][i]=(1<<tran(s[i]));
for(int l=2;l<=n;l++)for(int i=1,j=i+l-1;j<=n;i++,j++)for(int k=i;k<j;k++)for(int a=0;a<4;a++)for(int b=0;b<4;b++){
if(!(f[i][k]&(1<<a)))continue;
if(!(f[k+1][j]&(1<<b)))continue;
f[i][j]|=tr[a][b];
}
if(f[1][n]&(1<<0))putchar('W');
if(f[1][n]&(1<<1))putchar('I');
if(f[1][n]&(1<<2))putchar('N');
if(f[1][n]&(1<<3))putchar('G');
if(!f[1][n])puts("The name is wrong!");
return 0;
}
IV.CF149D Coloring Brackets
考虑设\(f[i][j][k=0/1/2][l=0/1/2]\)表示：将区间\([i,j]\)里的东西染色，左端染上颜色\(k\)，右端染上颜色\(l\)（\(0\)为红，\(1\)为蓝，\(2\)不染）的方案数。
因为这个\(n\)是\(700\)，\(n^3\)似乎过不了，考虑\(n^2\)的区间DP。
我们首先关于每个括号找出它匹配的位置。然后，约定只有合法的子串（连续的）的DP值是有效的，不合法的子串的DP值都为\(0\)。
当我们要求出\([i,j]\)的DP值时，
-
如果在位置\([i,j]\)上的括号本身就是匹配的，直接从\([i+1,j-1]\)转移过来；
-
否则，既然这个子串是合法的，那唯一的构成方式就是拼接（例如
()()）。直接从某个位置断开（比如说从右边界的匹配位置那边断开）拼一起即可。
复杂度为\(O((C+1)^4*n^2)\)，其中\(C\)是颜色数（本题中为\(2\)）。
代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int mat[710],n,f[710][710][3][3],res;
char s[710];
stack<int>stk;
int main(){
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<=n;i++){
if(s[i]=='(')stk.push(i);
else mat[stk.top()]=i,mat[i]=stk.top(),stk.pop();
}
for(int i=1;i<n;i++)if(mat[i]==i+1)f[i][i+1][0][2]=f[i][i+1][2][0]=f[i][i+1][1][2]=f[i][i+1][2][1]=1;
for(int l=4;l<=n;l+=2)for(int i=1,j=i+l-1;j<=n;i++,j++){
if(s[i]!='('||s[j]!=')')continue;
if(mat[i]==j){
for(int a=0;a<3;a++)for(int b=0;b<3;b++){
if(a==b)continue;
if(a!=2&&b!=2)continue;
for(int c=0;c<3;c++)for(int d=0;d<3;d++){
if(a!=2&&c!=2&&a==c)continue;
if(b!=2&&d!=2&&b==d)continue;
(f[i][j][a][b]+=f[i+1][j-1][c][d])%=mod;
}
}
}else{
int k=mat[j];
for(int a=0;a<3;a++)for(int b=0;b<3;b++)for(int c=0;c<3;c++)for(int d=0;d<3;d++){
if(b!=2&&c!=2&&b==c)continue;
f[i][j][a][d]=(1ll*f[i][k-1][a][b]*f[k][j][c][d]+f[i][j][a][d])%mod;
}
}
}
for(int i=0;i<3;i++)for(int j=0;j<3;j++)(res+=f[1][n][i][j])%=mod;
printf("%d\n",res);
return 0;
}
V.CF888F Connecting Vertices
这个奇怪的限制（两条边不能有交点）让我们想到什么？
对于任何一种方案，不存在\(x_0<x_1<y_0<y_1\)，其中连边\((x_0,y_0),(x_1,y_1)\)。
也就是说，对于任何一段区间\([i,j]\)，如果里面所有点全都连通：
要么\(i,j\)两点之间自己连了条边，此时，存在且仅存在一个\(k\)，使得区间\([i,k]\)和\([k+1,j]\)间有且只有\((i,j)\)一条边；
要么可以找到一个点\(k\)，使得区间\([i,k-1]\)与\([k+1,j]\)之间没有边，并且\(k\)与两个集合连通。
因此我们可以轻而易举写出：
\((a_{i,j}=1):f[i,j]=\sum\limits_{k=i}^{j} f[i,k]*f[k+1,j]\)
\(f[i,j]=\sum\limits_{k=i+1}^{j-1} f[i,k]*f[k,j]\)
但是这样会出问题：
要么可以找到一个点\(k\)，使得区间\([i,k-1]\)与\([k+1,j]\)之间没有边，并且\(k\)与两个集合连通。
并不表示这样的\(k\)唯一。例如，\((1,2)\rightarrow(2,3)\rightarrow(3,4)\)中，\(2\)是一个\(k\)，\(3\)也是一个\(k\)，这同一种方案就被算了两边！
因此，我们可以只拿最左边那个\(k\)为准。即，\(i\)与\(k\)直接连边的\(k\)才是好\(k\)。
我们新增维数：
设\(f[i,j][0/1]\)表示：区间\(i,j\)全部连通，并且\(i,j\)强制连边/强制不连边。
则有
\((a_{i,j}=1):f[i,j][0]=\sum\limits_{k=i}^{j} (f[i,k][0]+f[i,k][1])*(f[k+1,j][0]+f[k+1,j][1])\)
\(f[i,j]=\sum\limits_{k=i+1}^{j-1} f[i,k][0]*(f[k,j][0]+f[k,j][1])\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,f[510][510][2];
bool g[510][510];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&g[i][j]);
for(int i=1;i<=n;i++)f[i][i][0]=1;
for(int l=2;l<=n;l++)for(int i=1,j=i+l-1;j<=n;i++,j++){
if(g[i][j])for(int k=i;k<j;k++)(f[i][j][0]+=1ll*(f[i][k][0]+f[i][k][1])*(f[k+1][j][0]+f[k+1][j][1])%mod)%=mod;
for(int k=i+1;k<j;k++)if(g[i][k])(f[i][j][1]+=1ll*f[i][k][0]*(f[k][j][0]+f[k][j][1])%mod)%=mod;
}
printf("%d\n",(f[1][n][0]+f[1][n][1])%mod);
return 0;
}
VI.CF1178F1 Short Colorful Strip
考虑设\(f[i,j]\)表示：假设区间\([i,j]\)里面一开始所有格子的颜色都是相同的，那么，染成目标状态共有多少种染法。
我们找到\([i,j]\)中最小的那个颜色，设为\(mp\)。则显然，我们下一步要染上\(mp\)这种颜色。
设最终在位置\(p_{mp}\)上染上了颜色\(mp\)。则我们可以在所有这样的区间\([k,l]\)上染上\(mp\)（\(i\leq k\leq p_{mp}\leq l\leq j\)）。
或许你会以为这意味着\(f[i,j]=\sum\limits_{k=i}^{p_{mp}}\sum\limits_{l=p_{mp}}^jf[i,k-1]*f[k,l]*f[l+1,j]\)。
但是，这样是错误的，因为当\([k,l]=[i,j]\)时，\(f[i,j]\)便无法从子状态转移过来！
我们考虑拆开\(f[k,l]\)。因为再往后的染色中，位置\(p_{mp}\)一定没有再被染色过，因此有\(f[k,l]=f[k,p_{mp}-1]*f[p_{mp}+1,l]\)。
则\(f[i,j]=\sum\limits_{k=i}^{p_{mp}}\sum\limits_{l=p_{mp}}^jf[i,k-1]*f[k,p_{mp}-1]*f[p_{mp}+1,l]*f[l+1,j]\)。
特殊定义一下，对于\(f[i,j]\)，如果\(i>j\)，则\(f[i,j]=1\)。这也是为了转移的正确（在应用上述式子时可能会调用到这样的\(f[i,j]\)。
上面的转移是\(O(n^4)\)的；但当我们拆开两个\(\sum\)，就可以把它化成\(O(n^3)\)的。
\(f[i,j]=(\sum\limits_{k=i}^{p_{mp}}f[i,k-1]*f[k,p_{mp}-1])*(\sum\limits_{l=p_{mp}}^jf[p_{mp}+1,l]*f[l+1,j])\)
前后两个括号内的内容互不干涉，故可以分开计算。
复杂度\(O(n^3)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,num[510],f[510][510];
int main(){
scanf("%d%d",&n,&n);
for(int i=1;i<=n;i++)scanf("%d",&num[i]);
for(int i=1;i<=n+1;i++)for(int j=0;j<i;j++)f[i][j]=1;
for(int i=1;i<=n;i++)f[i][i]=1;
for(int l=2;l<=n;l++)for(int i=1,j=i+l-1;j<=n;i++,j++){
int mp=i;
for(int k=i;k<=j;k++)if(num[k]<=num[mp])mp=k;
int A=0,B=0;
for(int k=mp;k>=i;k--)(A+=(1ll*f[i][k-1]*f[k][mp-1]%mod))%=mod;
for(int l=mp;l<=j;l++)(B+=(1ll*f[mp+1][l]*f[l+1][j]%mod))%=mod;
f[i][j]=1ll*A*B%mod;
}
printf("%d\n",f[1][n]);
return 0;
}
VII.CF1178F2 Long Colorful Strip
首先，每一次染色，最多把一整段连续的同色格子，分成了三段。
并且，明显我们可以把连续的同色格子，直接看作一个。
这就意味着，在这么压缩后，有\(m<2n\)。
这就意味着\(O(m^3)\)的复杂度是可以接受的。
还是考虑和前一道题一样的DP。
但是这题，并非所有的\(f[i,j]\)都是合法的；只有对于每一种颜色，它所有的格子要么全都在段内，要么全都在段外，这样的\(f[i,j]\)才是合法的。因为，两个格子只要从什么时候开始颜色不一样了，那它们的颜色也会一直不一样下去。
考虑如何转移。
因为每种颜色都可能出现了不止一次，所以对于一种颜色\(c\)，我们有必要记录它出现的最左端\(mn_c\)与最右端\(mx_c\)。
则转移时的左右两端仍然可以采取和上一问一模一样的转移方式，即
\(f[i,j]=(\sum\limits_{k=i}^{mn_{mp}}f[i,k-1]*f[k,mn_{mp}-1])*(\sum\limits_{l=mx_{mp}}^jf[mx_{mp}+1,l]*f[l+1,j])\)
同时，对于区间\([mn_{mp},mx_{mp}]\)内的非\(mp\)的所有连续格子段\([p_x,q_x]\)，我们也都应该计算它们的贡献。
因此我们最终得到的是
\(f[i,j]=(\sum\limits_{k=i}^{mn_{mp}}f[i,k-1]*f[k,mn_{mp}-1])*(\sum\limits_{l=mx_{mp}}^jf[mx_{mp}+1,l]*f[l+1,j])*\prod f[p_x,q_x]\)
复杂度仍是\(O(n^3)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,num[1000100],f[1010][1010],mn[1010],mx[1010];
int main(){
scanf("%d%d",&n,&m);
memset(mn,0x3f3f3f3f,sizeof(mn));
for(int i=1;i<=m;i++){
scanf("%d",&num[i]);
if(num[i]==num[i-1])i--,m--;
}
if(m>2*n){puts("0");return 0;}
// for(int i=1;i<=m;i++)printf("%d ",num[i]);puts("");
for(int i=1;i<=m;i++)mx[num[i]]=max(mx[num[i]],i),mn[num[i]]=min(mn[num[i]],i);
// for(int i=1;i<=n;i++)printf("%d %d\n",mx[i],mn[i]);
for(int i=1;i<=m+1;i++)for(int j=0;j<i;j++)f[i][j]=1;
for(int l=1;l<=m;l++)for(int i=1,j=i+l-1;j<=m;i++,j++){
int mp=0x3f3f3f3f;
for(int k=i;k<=j;k++)mp=min(mp,num[k]);
if(mn[mp]<i||mx[mp]>j)continue;
int A=0,B=0;
for(int k=mn[mp];k>=i;k--)(A+=(1ll*f[i][k-1]*f[k][mn[mp]-1]%mod))%=mod;
for(int l=mx[mp];l<=j;l++)(B+=(1ll*f[mx[mp]+1][l]*f[l+1][j]%mod))%=mod;
f[i][j]=1ll*A*B%mod;
// printf("(%d,%d):\n",i,j);
for(int p=mn[mp]+1,q=mn[mp];p<mx[mp];){
while(q<j&&num[q+1]!=mp)q++;
// printf("(%d,%d)\n",p,q);
f[i][j]=1ll*f[i][j]*f[p][q]%mod;
q++,p=q+1;
}
// printf("%d\n",f[i][j]);
}
printf("%d\n",f[1][m]);
return 0;
}
VIII.CF GYM100739J.Longest cheap palindrome
我们设\(f[i,j,k,l,r]\)表示：
当前左端取到了位置\(i\)，右端取到了位置\(j\)；
当前选择的子序列长度为\(k\)；
区间\([i,l],[r,j]\)中所有字符都被选择时，最小要付出的代价。
转移很简单，枚举左右两边下一个字符选到哪里即可。
这里有一份\(O(n^8)\)的代码，按理说是过不去的，但是因为每一重循环内部都剪掉了很多枝，所以最终的结果是过掉了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,lim,res;
ll cost[34][34],f[2][34][34][34][34];//f[k,i,j,l,r]:leftmost at i, rightmost at j, length of 2k, [i,l] and [r,j] have been chosen
char s[50];
int main(){
scanf("%d%d%d",&n,&m,&lim),memset(f,0x3f,sizeof(f));
scanf("%s",s+1);
for(int i=1,a,b,c;i<=m;i++)scanf("%d%d%d",&a,&b,&c),cost[a][b]+=c;
for(int i=1;i<=n;i++)for(int j=i+2;j<=n;j++)if(s[i]==s[j])f[1][i][j][i][j]=cost[i][i]+cost[j][j];
for(int k=1;(k<<1)<=n;k++){
for(int i=1,j=i+(k<<1)-1;j<=n;i++,j++){
bool ok=true;
for(int l=0;l<k;l++)ok&=(s[i+l]==s[j-l]);
if(!ok)continue;
f[k&1][i][j][i+k-1][i+k]=0;
for(int u=i;u<=j;u++)for(int v=u;v<=j;v++)f[k&1][i][j][i+k-1][i+k]+=cost[u][v];
}
memset(f[!(k&1)],0x3f,sizeof(f[!(k&1)]));
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)for(int l=i;l<=j;l++)for(int r=j;r>l;r--){
if(f[k&1][i][j][l][r]>lim)continue;
res=max(res,k<<1);
for(int u=i-1;u;u--)for(int v=j+1;v<=n;v++){
if(s[u]!=s[v])continue;
if(l+1==r&&u==i-1&&v==j+1)continue;
ll now=f[k&1][i][j][l][r];
if(u==i-1)for(int w=u;w<=(l+1==r?j:l);w++)now+=cost[u][w];
else now+=cost[u][u];
if(v==j+1)for(int w=v;w>=(l+1==r?i:r);w--)now+=cost[w][v];
else now+=cost[v][v];
f[!(k&1)][u][v][u==i-1?l:u][v==j+1?r:v]=min(f[!(k&1)][u][v][u==i-1?l:u][v==j+1?r:v],now);
}
}
}
printf("%d\n",res);
return 0;
}
IX.[CERC2014]Outer space invaders
一种错误的思路是观察到一定可以构造出一种最优状态使得每次射击都发生在外星人消失的时刻，然后就将所有外星人按照消失时刻排序并设\(f[i,j]\)表示在第\(i\)个外星人消失的时刻如果你开了一炮高为（离散化后）\(j\)的最小费用——但很快就会发现这种DP需要记录下在这之前每一个高度上次被打的时间，于是就DP不了了。
正确的DP是将所有的端点离散化后，观察到如果我们要把被完整的包含在区间\([l,r]\)内的所有外星人全部干掉，则其中最远的那个必定要对它开一炮；于是我们便找出这一个外星人，然后枚举这一炮开在哪（设为\(p\)），就可以将其分作\([l,p-1]\)与\([p+1,r]\)两截（所有经过\(p\)的外星人都被干掉了）。
于是就可以区间DP了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
int T,n,m,f[610][610],l[310],r[310],d[310];
vector<int>v;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n),v.clear(),memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)scanf("%d%d%d",&l[i],&r[i],&d[i]),v.push_back(l[i]),v.push_back(r[i]);
sort(all(v)),v.resize(m=unique(all(v))-v.begin());
for(int i=1;i<=n;i++)l[i]=lower_bound(all(v),l[i])-v.begin()+1,r[i]=lower_bound(all(v),r[i])-v.begin()+1;
for(int i=1;i<=m;i++)for(int j=i;j;j--){
int id=-1;
for(int k=1;k<=n;k++)if(j<=l[k]&&r[k]<=i&&(id==-1||d[id]<d[k]))id=k;
if(id==-1)continue;
f[j][i]=0x3f3f3f3f;
for(int k=l[id];k<=r[id];k++)f[j][i]=min(f[j][i],f[j][k-1]+d[id]+f[k+1][i]);
}
printf("%d\n",f[1][m]);
}
return 0;
}
X.HDU6212 Zuma
一眼区间DP。
首先，我们将串压缩（即将相同颜色的相邻珠子合并）。记\(col_i\)为位置\(i\)的颜色，\(sz_i\)为位置\(i\)的珠子数。
我们设\(f[i,j]\)表示消去区间\([i,j]\)中所有东西的最小步数。
则有：
\[f[i,j]=\min\begin{cases}3-sz_i&|i=j\\f[i,k]+f[k+1,j]&|i\leq k<j\\f[i+1,j-1]+\max(0,3-sz_i-sz_j)&|col_i=col_j\\f[i+1,k-1]+f[k+1,j-1]&|col_i=col_j=col_k,(sz_i\neq 2\lor sz_j\neq 2)\land sz_k=1\end{cases} \]其中，第一条转移是直接补满\(3\)个球；第二条转移是找个地方切一刀；第三条转移是将\(i\)和\(j\)最终合并在一起进行消除；第四条转移是将\(i\)，\(j\)，以及区间中某一个\(k\)合并消除，但需要保证有一种消除顺序可以使得\(k\)可以先在不与某一边一起消掉的前提下消到那一边，然后再合并两边。
时间复杂度\(O(Tn^3)\)，需要保证常数。
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,m,sz[210],f[210][210];
bool col[210];
char s[210];
int main(){
scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%s",s+1),m=strlen(s+1),n=0;
col[1]=s[1]-'0',sz[1]=1,n++;
for(int i=2;i<=m;i++){
if(s[i]-'0'==col[n])sz[n]++;
else n++,col[n]=s[i]-'0',sz[n]=1;
}
for(int i=1;i<=n;i++)f[i][i]=3-sz[i];
for(int l=2;l<=n;l++)for(int i=1,j=i+l-1;j<=n;i++,j++){
f[i][j]=0x3f3f3f3f;
for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
if(col[i]!=col[j])continue;
f[i][j]=min(f[i][j],f[i+1][j-1]+max(0,3-sz[i]-sz[j]));
if(sz[i]==2&&sz[j]==2)continue;
for(int k=i+1;k<j;k++)if(col[k]==col[i]&&sz[k]==1)f[i][j]=min(f[i][j],f[i+1][k-1]+f[k+1][j-1]);
}
printf("Case #%d: %d\n",t,f[1][n]);
}
return 0;
}
XI.[NOI2009]二叉查找树
首先该树的中序遍历是唯一可以确定的（直接按照数据值排序即可）。
然后，因为权值可以被修改成一切实数，故我们完全可以把权值离散化掉。
于是我们现在可以设置一个DP状态\(f[l,r,lim]\)表示：
区间\([l,r]\)中的所有东西构成了一棵子树，且树中最小权值不小于\(lim\)的最优方案。
然后就枚举根转移即可。转移的时候就可以看作是子树内所有东西被整体提高了一层，所以直接增加\(sum[l,r]\)（意为区间\([l,r]\)中的所有数据值之和）即可。同时，如果有当前枚举的根的权值不小于\(lim\)，显然就可以不修改，但是两边儿子的权值就必须比它大；否则则必须修改，两边儿子的权值下限还是\(lim\)（因为根的权值可以被修改成一个略大于\(lim\)的实数）。
则时间复杂度\(O(n^4)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,sum[110],f[110][110][110];
struct dat{
int val,key,lam;
}a[100];
int dfs(int l,int r,int lim){
if(l>r)return 0;
if(f[l][r][lim]!=-1)return f[l][r][lim];
int &now=f[l][r][lim];now=0x3f3f3f3f;
for(int i=l;i<=r;i++){//assume that i is the root in the section [l,r].
if(a[i].key>=lim)now=min(now,dfs(l,i-1,a[i].key)+dfs(i+1,r,a[i].key)+sum[r]-sum[l-1]);//do not modify, the height simply increased by one.
now=min(now,dfs(l,i-1,lim)+dfs(i+1,r,lim)+m+sum[r]-sum[l-1]);//modify i to any real number a little greater than lim.
}
return now;
}
int main(){
scanf("%d%d",&n,&m),memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)scanf("%d",&a[i].val);
for(int i=1;i<=n;i++)scanf("%d",&a[i].key);
for(int i=1;i<=n;i++)scanf("%d",&a[i].lam);
sort(a+1,a+n+1,[](dat u,dat v){return u.key<v.key;});
for(int i=1;i<=n;i++)a[i].key=i;
sort(a+1,a+n+1,[](dat u,dat v){return u.val<v.val;});
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].lam;
printf("%d\n",dfs(1,n,1));
return 0;
}
XII.[THUSC2016]成绩单
区间 DP。但是取出任意一段？这怎么设计？
考虑设 \(f(l,r,s,t)\) 表示初始是区间 \([l,r]\)，然后选了几次后区间中的最小值是 \(s\)、最大值是 \(t\) 时，到达这个状态时的最优代价。同时设 \(g(l,r)\) 表示消光 \([l,r]\) 区间时的最优代价。
显然，对于 \(f(l,r,s,t)\)，可以以 \(a+b(t-s)^2\) 的代价直接转移到 \(g(l,r)\)。
那么我们考虑 \(f(l,r,s,t)\) 可以被什么方式构造出。显然，可以枚举断点 \(k\)，则有三种可能：
- 断点左侧保留 \(s,t\)，右侧全部删光，即 \(f(l,k,s,t)+g(k+1,r)\)。
- 右侧保留、左侧删光，即 \(g(l,k)+f(k+1,r,s,t)\)。
- 全都保留，即 \(f(l,k,s,t)+f(k+1,r,s,t)\)。
时间复杂度 \(O(n^5)\)。
记得离散化。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,w[100],f[70][70][70][70],g[70][70];
vector<int>v;
int main(){
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++)scanf("%d",&w[i]),v.push_back(w[i]);
sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)w[i]=lower_bound(v.begin(),v.end(),w[i])-v.begin()+1;
memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g));
for(int i=1;i<=n;i++){
g[i][i]=a;
for(int s=1;s<=w[i];s++)for(int t=w[i];t<=m;t++)f[i][i][s][t]=0;
}
for(int l=n;l;l--)for(int r=l+1;r<=n;r++)for(int s=1;s<=m;s++)for(int t=s;t<=m;t++){
for(int k=l;k<r;k++){
f[l][r][s][t]=min(f[l][r][s][t],g[l][k]+f[k+1][r][s][t]);
f[l][r][s][t]=min(f[l][r][s][t],f[l][k][s][t]+g[k+1][r]);
f[l][r][s][t]=min(f[l][r][s][t],f[l][k][s][t]+f[k+1][r][s][t]);
}
g[l][r]=min(g[l][r],f[l][r][s][t]+a+b*(v[t-1]-v[s-1])*(v[t-1]-v[s-1]));
}
printf("%d\n",g[1][n]);
return 0;
}
XIII.[USACO04OPEN]Turning in Homework G
首先可以数轴上每个坐标上设一个 \(tim_x\) 表示其上最晚的一份作业。删去最后的数个为空的 \(tim\)。
这样之后，区间 \([0,H]\) 中所有坐标显然要被至少访问一次。
可以发现，任意时刻尚未提交的作业必然在一个区间中。为什么呢？因为你就算交了中间的作业，也必然要跑到两边各一次，也就是只要两边有剩的，中间的提交就无意义。
那么就随便 DP，\(f[l,r,0/1]\) 表示在左右端点时的最优答案即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,t,f[1010][1010][2],tim[1010],res=0x3f3f3f3f;
int main(){
scanf("%d%d%d",&n,&m,&t),memset(tim,-1,sizeof(tim));
for(int i=1,x,y;i<=n;i++)scanf("%d%d",&x,&y),tim[x]=max(tim[x],y);
while(tim[m]==-1)m--;
memset(f,0x3f,sizeof(f)),f[0][m][0]=0;
for(int l=0;l<=m;l++)for(int r=m;r>=0;r--){
f[l][r][0]=min(f[l][r][0],f[l][r][1]+r-l);
f[l][r][1]=min(f[l][r][1],f[l][r][0]+r-l);
f[l][r][0]=max(f[l][r][0],tim[l]);
f[l][r][1]=max(f[l][r][1],tim[r]);
if(l<r){
f[l+1][r][0]=min(f[l+1][r][0],f[l][r][0]+1);
f[l][r-1][1]=min(f[l][r-1][1],f[l][r][1]+1);
}else{
res=min(res,f[l][r][0]+abs(t-l));
res=min(res,f[l][r][1]+abs(t-r));
}
}
printf("%d\n",res);
return 0;
}
XIV.BZOJ#4350. 括号序列再战猪猪侠
首先对给出的信息跑个传递闭包，如果发现一个点能到达自己则肯定无解，直接判 0 即可。
然后考虑 DP。设 \(f(i,j)\) 表示第 \(i\) 个左括号内部是第 \(i+1\sim j\) 个括号时的方案数。设 \(g(i,j)\) 表示第 \(i\sim j\) 个左括号内部完美匹配的方案数。
\(f(i,j)\) 可以通过枚举其内部第一个完美匹配的子括号 \((i+1,k)\) 进行转移，即 \(\sum f(i+1,k)\times g(k+1,j)\)。
\(g(i,j)\) 可以枚举第一个 \(f\) 转移，即 \(\sum f(i,k)\times g(k+1,j)\)。
需要注意的是假如两个区间是并列关系的话，需要验证后面区间中的任何一个点是否都不能到达前面区间中的任何一个点，不然它们间就必须是包含关系。这个可以对传递闭包后的邻接矩阵作二维前缀和来简单得知。
时间复杂度 \(O(n^3)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int T,n,m,g[310][310],f[310][310];
int s[310][310];
void mian(){
scanf("%d%d",&n,&m);
memset(s,false,sizeof(s));
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),s[x][y]=1;
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s[i][j]|=(s[i][k]&&s[k][j]);
for(int i=1;i<=n;i++)if(s[i][i]){puts("0");return;}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
for(int i=1;i<=n;i++)f[i][i]=g[i][i]=1;
for(int l=n;l;l--)for(int r=l+1;r<=n;r++){
f[l][r]=g[l][r]=0;
if(!(s[l][r]-s[l][l]-s[l-1][r]+s[l-1][l])){
for(int k=l+1;k<r;k++)if(!(s[r][k]-s[r][l]-s[k][k]+s[k][l]))f[l][r]=(1ll*f[l+1][k]*g[k+1][r]+f[l][r])%mod;
(f[l][r]+=f[l+1][r])%=mod;
}
g[l][r]=f[l][r];
for(int k=l;k<r;k++)if(!(s[r][k]-s[r][l-1]-s[k][k]+s[k][l-1]))g[l][r]=(1ll*f[l][k]*g[k+1][r]+g[l][r])%mod;
}
printf("%d\n",g[1][n]);
}
int main(){
scanf("%d",&T);
while(T--)mian();
return 0;
}
XV.[POI2015]MYJ
觉得一个类笛卡尔树的结构会非常棒。于是我们离散化后设 \(f(l,r,k)\) 表示区间 \([l,r]\) 中最小值是 \(k\) 时的答案，枚举最小值的位置然后后缀和优化一下即可。
时间复杂度 \(O(n^3m)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,f[60][60][4010],s[60][60][4010],g[60][60][4010],a[60];
vector<int>v[60][60],u;
void getans(int l,int r,int p){
if(l>r)return;
for(int k=p;k<=u.size();k++)if(f[l][r][k]==g[l][r][p]){p=k;break;}
for(int k=l;k<=r;k++){
int sum=0;
for(int i=l;i<=k;i++)for(int j=k;j<=r;j++)sum+=s[i][j][p]*u[p-1];
if(f[l][r][p]==sum+g[l][k-1][p]+g[k+1][r][p]){
a[k]=u[p-1],getans(l,k-1,p),getans(k+1,r,p);
return;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%d",&x,&y,&z),v[x][y].push_back(z),u.push_back(z);
sort(u.begin(),u.end()),u.resize(unique(u.begin(),u.end())-u.begin());
for(int l=n;l;l--)for(int r=l;r<=n;r++){
for(auto x:v[l][r])s[l][r][lower_bound(u.begin(),u.end(),x)-u.begin()+1]++;
for(int k=u.size();k;k--)s[l][r][k]+=s[l][r][k+1];
for(int p=u.size();p;p--){
for(int k=l;k<=r;k++){
int sum=0;
for(int i=l;i<=k;i++)for(int j=k;j<=r;j++)sum+=s[i][j][p]*u[p-1];
f[l][r][p]=max(f[l][r][p],sum+g[l][k-1][p]+g[k+1][r][p]);
}
g[l][r][p]=max(g[l][r][p+1],f[l][r][p]);
}
}
printf("%d\n",g[1][n][1]);
getans(1,n,1);
for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
return 0;
}
XVI.[WF2013][GYM101208H]Matryoshka
用区间 DP 模拟合并的过程即可。判定一个套娃合不合法直接遍历每种大小 check 即可。时间复杂度 \(O(n^3)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[510],c[510][510][510],f[510][510],mn[510][510],g[510];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int l=n;l;l--)for(int r=l;r<=n;r++){
mn[l][r]=0x3f3f3f3f;
for(int k=l;k<=r;k++)c[l][r][a[k]]++,mn[l][r]=min(mn[l][r],a[k]);
for(int k=1;k<=n;k++)c[l][r][k]+=c[l][r][k-1];
f[l][r]=0x3f3f3f3f;
for(int k=l;k<r;k++){
int mx=max(mn[l][k],mn[k+1][r]);
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+r-l+2-c[l][k][mx]-c[k+1][r][mx]);
}
if(l==r)f[l][r]=0;
// printf("[%d,%d]:%d\n",l,r,f[l][r]);
}
memset(g,0x3f,sizeof(g)),g[0]=0;
for(int i=1;i<=n;i++)for(int j=i;j;j--){
bool ok=true;
for(int k=1;k<=i-j+1;k++)ok&=(c[j][i][k]==c[j][i][k-1]+1);
// if(ok)printf("[%d,%d]\n",j,i);
if(ok)g[i]=min(g[i],g[j-1]+f[j][i]);
}
if(g[n]==0x3f3f3f3f)puts("impossible");else printf("%d\n",g[n]);
return 0;
}
XVII.[AGC028D] Chords
对于每个区间统计其中所有方案的连通块个数之和是没有出路的——因为无法处理确定的边。真正可行的方案是对于每个连通块求出包含其的方案个数。
首先先断环成链。在 \(1\) 与 \(2n\) 间切断即可，这样两条线段有交当且仅当其对应区间有交且不包含。
设 \(f(l,r)\) 表示 \(l,r\) 分别是某个连通块中最左和最右点时，仅考虑区间中的点，连边方案数。设 \(g(x)\) 表示 \(x\) 个点无任何限制的连边数，则其在 \(x\) 为偶数时等于 \(x-1\) 的双阶乘，为奇数时等于 \(0\)。
令 \(c(l,r)\) 表示区间 \(l,r\)（包含 \(l,r\)）中未匹配的点数。则用全部方案数减去 \(i\) 与某点匹配的方案数，得到
\[f(l,r)=g\big(c(l,r)\big)-\sum\limits_{i=l+1}^{r-1}f(l,i)g\big(c(i+1,r)\big) \]DP 即可。复杂度 \(O(n^3)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,mat[610],f[610][610],c[610][610],g[610],res;
int main(){
scanf("%d%d",&n,&m),n<<=1;
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),mat[x]=y,mat[y]=x;
g[0]=1;for(int i=2;i<=n;i+=2)g[i]=1ll*g[i-2]*(i-1)%mod;
memset(c,-1,sizeof(c));
for(int l=1;l<=n;l++)for(int r=l+1;r<=n;r++){
c[l][r]=0;
for(int i=l;i<=r;i++)if(!mat[i])c[l][r]++;else if(mat[i]<l||mat[i]>r){c[l][r]=-1;break;}
}
for(int l=n;l;l--)for(int r=l+1;r<=n;r+=2){
if(c[l][r]==-1)continue;
// printf("[%d,%d]\n",l,r);
f[l][r]=g[c[l][r]];
for(int i=l+1;i<r;i++)if(c[i+1][r]!=-1)(f[l][r]+=mod-1ll*f[l][i]*g[c[i+1][r]]%mod)%=mod;
// printf("%d\n",f[l][r]);
res=(1ll*f[l][r]*g[n-2*m-c[l][r]]+res)%mod;
}
printf("%d\n",res);
return 0;
}
XVIII.[AGC039E] Pairing Points
考虑分析该问题的结构。
考虑从 \(1\) 号点出发连一条边，终点是 \(x\)。
接着连若干条边与该边相交。即，在 \(1\to x\) 边的两侧各选择相等数量的点，然后连接序号相同的点。这样之后，两端分别进入子问题。
考虑子问题，即一段区间中有若干特殊点，将该区间划分成若干段。在相邻的两段区间中，我们可以如上选择若干相等数量的点，匹配后进入子问题。
我们设 \(f_{l,r,p}\) 表示 \([l,r]\) 中特殊点为 \(p\) 的方案数。转移系数可以用一个 \(g\) 来辅助处理，进而有一个八方的做法。倒着处理 \(g\) 存在一个七方做法。但是八方已经可以通过。
八方做法代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll f[50][50][50],g[50][50],res;
char s[50][50];
int main(){
scanf("%d",&n),n<<=1;
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=2;i<=n;i++)f[i][i][i]=1;
for(int l=n;l>=2;l--)for(int r=l+1;r<=n;r++){
memset(g,0,sizeof(g));
g[l][r]=1;
for(int _l=l;_l<=r;_l++)for(int _r=r;_r>=_l;_r--)
for(int L=_l+1;L<=_r;L++)for(int R=_r-1;R>=L;R--)for(int p=_l;p<L;p++)for(int q=_r;q>R;q--)
if(s[p][q]=='1')
g[L][R]+=g[_l][_r]*f[_l][L-1][p]*f[R+1][_r][q];
for(int i=l;i<=r;i++)f[l][r][i]=g[i][i];
}
for(int i=2;i<=n;i++)if(s[1][i]=='1')res+=f[2][n][i];
printf("%lld\n",res);
return 0;
}
七方做法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll f[50][50][50],res;
char s[50][50];
int main(){
scanf("%d",&n),n<<=1;
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=2;i<=n;i++)f[i][i][i]=1;
for(int l=n;l>=2;l--)for(int r=l+1;r<=n;r++)for(int i=l;i<=r;i++)
for(int L=l+1;L<=i;L++)for(int R=r-1;R>=i;R--)for(int p=l;p<L;p++)for(int q=r;q>R;q--)
if(s[p][q]=='1')
f[l][r][i]+=f[L][R][i]*f[l][L-1][p]*f[R+1][r][q];
for(int i=2;i<=n;i++)if(s[1][i]=='1')res+=f[2][n][i];
printf("%lld\n",res);
return 0;
}
XIX.[JXOI2018]守卫
首先分析一下流程。对于 \(a<b<c<d\)，若 \(d\) 能看到 \(c,b\)，\(c\) 能看到 \(a\)，那么画出图来就能发现 \(d\) 定能看到 \(a\)。
这意味着设 \(d\) 能看到的位置集合是 \(x_1,x_2,x_3,\dots\)，则位于 \(x_i\) 和 \(x_{i+1}\) 间的间谍不可能是能看到小于 \(x_i\) 的唯一人。
记 \(f_{l,r}\) 为区间 \([l,r]\) 中的位置需要几个间谍。
于是对于一段 \([x_i,x_{i+1}]\)，其贡献就会是 \(\min(f_{x_i,x_{i+1}},f_{x_i,x_{i+1}-1})\)。最后一小段 \([l,x_i]\) 特别处理一下即可。
复杂度平方。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,f[5010][5010],mp[5010][5010],res;
int a[5010];
vector<int>v;
int main(){
// freopen("guard.in","r",stdin);
// freopen("guard.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
memset(mp,-1,sizeof(mp));
f[1][1]=1;
for(int r=2;r<=n;r++){
f[r][r]=f[r-1][r]=1;
int sum=1;
for(int j=r-2,k=r-1;j;j--){
if(1ll*(a[j]-a[r])*(r-k)>1ll*(a[k]-a[r])*(r-j))
sum+=min(f[j+1][k-1],f[j+1][k]),k=j,f[j][r]=f[j+1][r];
else f[j][r]=sum+min(f[j][k-1],f[j][k]);
}
}
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)res^=f[i][j];
printf("%d\n",res);
return 0;
}
IV.背包
所有的背包。
I.[HAOI2010]软件安装
不知道大家有没有做过这道题[CTSC1997]选课啊，反正我一看到这道题，就想起了它——都是树上背包。所以我便高高兴兴的敲了一发背包交上去。
然后呢？光荣的WA掉了。
为什么呢？
因为这道题和选课不一样；选课是你没有修完前一节课就不能修这节；但是本题是你装软件是可以随便装，想咋装就咋装的——只不过会不会起效就不知道了。因此，如果成环的话，只要整个环全装上就行了。
那么我们就SCC缩个点，在缩出来的树上背包一下就行了（实际上数据还可以加强成DAG的……）
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,w[110],v[110],f[110][510],g[510],res,col[110],val[110],sz[110],in[110],c;
namespace SCC{
int tot,dfn[310],low[310],head[310],cnt;
struct node{
int to,next;
}edge[200100];
void ae(int u,int v){
// cout<<u<<" "<<v<<endl;
edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
}
stack<int>stk;
void Tarjan(int x){
dfn[x]=low[x]=++tot,stk.push(x);
for(int i=head[x];i!=-1;i=edge[i].next){
if(!dfn[edge[i].to])Tarjan(edge[i].to),low[x]=min(low[x],low[edge[i].to]);
if(!col[edge[i].to])low[x]=min(low[x],dfn[edge[i].to]);
}
if(low[x]<dfn[x])return;
c++;
while(stk.top()!=x)col[stk.top()]=c,val[c]+=v[stk.top()],sz[c]+=w[stk.top()],stk.pop();
col[stk.top()]=c,val[c]+=v[stk.top()],sz[c]+=w[stk.top()],stk.pop();
}
}
namespace DP{
int head[110],cnt;
struct node{
int to,next;
}edge[110];
void ae(int u,int v){
// printf("%d %d\n",u,v);
edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
}
void dfs(int x){
if(sz[x]<=m)f[x][sz[x]]=val[x];
for(int i=head[x];i!=-1;i=edge[i].next){
dfs(edge[i].to);
for(int j=0;j<=m;j++)g[j]=f[x][j];
for(int j=0;j<=m;j++)for(int k=0;j+k<=m;k++)if(f[x][j]!=-1&&f[edge[i].to][k]!=-1)g[j+k]=max(g[j+k],f[x][j]+f[edge[i].to][k]);
for(int j=0;j<=m;j++)f[x][j]=g[j];
}
}
}
int main(){
scanf("%d%d",&n,&m),memset(f,-1,sizeof(f)),memset(SCC::head,-1,sizeof(SCC::head)),memset(DP::head,-1,sizeof(DP::head));
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
if(x)SCC::ae(x,i);
}
for(int i=1;i<=n;i++)if(!SCC::dfn[i])SCC::Tarjan(i);
// for(int i=1;i<=c;i++)printf("%d %d\n",val[i],sz[i]);
for(int i=1;i<=n;i++)for(int j=SCC::head[i];j!=-1;j=SCC::edge[j].next)if(col[i]!=col[SCC::edge[j].to])DP::ae(col[i],col[SCC::edge[j].to]),in[col[SCC::edge[j].to]]++;
for(int i=1;i<=c;i++)if(!in[i])DP::ae(0,i);
DP::dfs(0);
for(int i=0;i<=m;i++)res=max(res,f[0][i]);
printf("%d\n",res);
return 0;
}
II.[十二省联考 2019]皮配
题解里”豌豆“的比喻实在太精妙了。
先重新描述一遍题意：有 \(n\) 个豆子，每个豆子有其重量，并位于某个豆荚内。每粒豆子颜色可以为黄色/绿色，表皮可以为皱皮/圆皮。每个豆荚里所有豆子的颜色必须相同。对于所有黄色/绿色/皱皮/圆皮的豆子，其重量和有一上界。有些豆子不能同时具有某两种性状，称其为”特殊的“。求总方案数。
首先，”重量和有上界“，想到背包问题。于是我们设计一种DP，\(f_{i,j}\) 表示黄色/皱皮的豆子分别的质量和，则绿色/圆皮的豆子可以用总质量减去得到。枚举每颗豆子是哪种具体性状，转移即可。
然后，我们发现，大部分时候，\(i,j\) 两维都是独立的——更准确地来说，对于那些不存在特殊豆子的豆荚来说，\(i\) 一维其就是在关于豆荚颜色背包；对于那些非特殊豆子来说，\(j\) 一维就是在关于豆子表皮背包。
于是我们设 \(f_i\) 表示黄色豆荚的总质量为 \(i\) 的方案数，\(g_i\) 表示皱皮豆子的总质量为 \(i\) 的方案数。显然复杂度皆为 \(O(nM)\)。
因为 \(k\) 很小，所以特殊的豆子和豆荚数也很小，我们就把初始的状态搬过来，设 \(h_{i,j}\) 表示初始状态的意义，用它来处理特殊的东西即可。这部分时间复杂度 \(O\Big(k\times(ks)\times M\Big)=k^2sM\)，其中 \(k\) 是特殊豆子数，\(s\) 是豆子的最大质量。
最后就拼接 \(f,g,h\) 即可计算答案。（对于某个 \(h_{i,j}\)，能与其构成合法方案的 \(f\) 与 \(g\) 各是一段区间，故对其做前缀和即可简单维护）
需要注意存在空豆荚。
代码：
/*
Mendel's peas are Awesome!
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int T,n,m,q,yel,gre,rou,smo,id[1010],wei[1010],fob[1010],WEI[1010],f[2510],g[2510],h[2510][310],hh[2510][310],all,res;//yellow,green,rough,smooth
vector<int>v[1010];
bool FOB[1010];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m),memset(fob,-1,sizeof(fob));
scanf("%d%d%d%d",&yel,&gre,&rou,&smo);
for(int i=1;i<=n;i++)scanf("%d%d",&id[i],&wei[i]),WEI[id[i]]+=wei[i],v[id[i]].push_back(i),all+=wei[i];
scanf("%d",&q);
for(int i=1,x,y;i<=q;i++){
scanf("%d%d",&x,&y);
fob[x]=y,FOB[id[x]]=true;
}
f[0]=1;
for(int i=1;i<=m;i++){
if(FOB[i]||v[i].empty())continue;
for(int j=yel-WEI[i];j>=0;j--)(f[j+WEI[i]]+=f[j])%=mod;
}
g[0]=1;
for(int i=1;i<=n;i++){
if(fob[i]!=-1)continue;
for(int j=rou-wei[i];j>=0;j--)(g[j+wei[i]]+=g[j])%=mod;
}
for(int i=1;i<=yel;i++)(f[i]+=f[i-1])%=mod;
for(int i=1;i<=rou;i++)(g[i]+=g[i-1])%=mod;
h[0][0]=1;
for(int i=1;i<=m;i++){
if(!FOB[i]||v[i].empty())continue;
memcpy(hh,h,sizeof(h));
for(auto x:v[i]){
if(fob[x]==-1)continue;
if(fob[x]>1)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=wei[x];k--)(hh[j][k]+=hh[j][k-wei[x]])%=mod;
else if(fob[x]==1)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=0;k--)hh[j][k]=(k>=wei[x]?hh[j][k-wei[x]]:0);
if(fob[x]<=1)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=wei[x];k--)(h[j][k]+=h[j][k-wei[x]])%=mod;
else if(fob[x]==3)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=0;k--)h[j][k]=(k>=wei[x]?h[j][k-wei[x]]:0);
}
for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=0;k--)if(j>=WEI[i])(h[j][k]+=hh[j-WEI[i]][k])%=mod;
}
gre=all-gre,smo=all-smo;
for(int i=0;i<=yel;i++)for(int j=0;j<=min(rou,300);j++){
int F=f[yel-i];
if(i<gre)(F+=mod-f[gre-i-1])%=mod;
int G=g[rou-j];
if(j<smo)(G+=mod-g[smo-j-1])%=mod;
(res+=1ll*h[i][j]*F%mod*G%mod)%=mod;
}
printf("%d\n",res);
memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(h,0,sizeof(h));
for(int i=1;i<=m;i++)WEI[i]=0,FOB[i]=false,v[i].clear();
all=res=0;
}
return 0;
}
III.[NOI2020] 制作菜品
本题有三个难点：留意到题面中的 \(n-2\leq m\)；证明；想到 bitset 优化。
首先，在很隐蔽的角落，有一句话 \(n-2\leq m\leq 5000\)。假如没看到这句话，就乖乖爆零罢。
结论1. \(m\geq n-1\) 时一定有解。
要证明这个结论，我们要分成三部分。
结论1.1. \(m=n-1\) 时一定有解。
不妨将 \(a\) 数组递增排序。则，\(a_1\) 必定 \(<k\)，因为所有数的平均值为 \(\dfrac{mk}{n}=\dfrac{(n-1)k}{n}<k\)，则必有至少一个数满足 \(<k\) 的条件。
同时，我们也能发现，\(a_1+a_n>k\)。因为，若 \(a_1+a_n\leq k\)，则 \(mk=\sum\limits_{i=1}^na_i\leq d_1+\sum\limits_{i=2}^na_n\leq a_1+(n-1)(k-a_1)=(n-1)k-(n-2)a_1=mk-(n-2)a_1\)。显然，当 \(n>2\) 时，因为 \(a_1>0\)，所以 \((n-2)a_1>0\)，故可以一次填完所有 \(a_1\)，然后不足的部分就用 \(a_n\) 补，这样便同时少了一种原料和一道菜，转移到了 \(n-1\) 的情形；而当 \(n=2\) 时，因为只要做一道菜，所以直接把剩余的两种原料怼一块即可。
结论1.2. \(m=n\) 时一定有解。
不妨仍将 \(a\) 数组递增排序。则，\(a_n\) 必定 \(\geq k\)，因为所有数的平均值为 \(k\)，则必有至少一个数满足 \(\geq k\) 的条件。
若 \(a_n=k\)，则可以用 \(a_n\) 单独做一道菜，转移到 \(n,m\) 均减少 \(1\) 的情形，这样不断递归下去，直到 \(n,m\) 均为 \(0\)（此时已经构造出一组解）或是 \(a_n>k\)。当 \(a_n>k\) 时，仍可以用 \(a_n\) 单独做一道菜，转移到 \(m=n-1\) 的情形。
结论1.3. \(m>n\) 时一定有解。
递增排序后，\(a_n\) 必定 \(>k\)，因为所有数的平均值 \(>k\)，则必有至少一个数 \(>k\)。于是可以用 \(a_n\) 单独做一道菜，转移到 \(m\) 减一的情形。不断执行，直到到达 1.2 的场景。
结论2. \(m=n-2\) 时，当且仅当其能被分成两个非空集合 \(\mathbb{U,V}\) 使得 \(\sum\limits_{u\in\mathbb U}a_u=\Big(|\mathbb U|-1\Big)k\) 时，有解。
首先，其是充分的，因为对于 \(\mathbb{U,V}\) 我们可以分别应用 1.1 中的结论直接构造出一组解来。
其次，其是必要的，因为 \(n-2\) 条边连不出一张连通图，必定可以将所有原料分作两个集合使得不存在任何同时包含来自两个集合的原料的菜。
这样，我们就可以背包出一组解来了。具体而言，有经典套路是在上式中把 \(k\) 移到左侧，得到 \(\sum\limits_{u\in\mathbb U}(a_u-k)=-k\)。暴力背包复杂度是 \(O(n^3k)\) 的。但是，因为01背包的数组是 bool 数组，所以可以使用 bitset 优化至 \(\dfrac{n^3k}{\omega}\)。
（可能因为 bitset 开太大的缘故，本代码在 Windows 下会 RE，可以使用 CF 的 Custom Test 编译）
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,m,p,a[510],ord[510];
vector<vector<int> >v;
bool cmp(int u,int v){return a[u]<a[v];}
bitset<5000010>bs[502];
const int half=2500002;
bool sd[510];
void SOLVE(int M,int N,int *dro){
while(M){
sort(dro+1,dro+N+1,cmp);
v.push_back({dro[1],a[dro[1]],dro[N],p-a[dro[1]]});
a[dro[N]]-=p-a[dro[1]];
dro[1]=dro[N--],M--;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&p),v.clear();
for(int i=1;i<=n;i++)scanf("%d",&a[i]),ord[i]=i;
while(m>n){
sort(ord+1,ord+n+1,cmp);
v.push_back({ord[n],p}),a[ord[n]]-=p;
m--;
}
while(n&&m==n){
sort(ord+1,ord+n+1,cmp);
v.push_back({ord[n],p}),a[ord[n]]-=p;
m--;
if(!a[ord[n]])n--;
}
if(m==n-1)SOLVE(m,n,ord);else if(n){
bs[0].reset(),bs[0].set(half);
for(int i=1;i<=n;i++){
// printf("%d\n",i);
if(a[i]==p)bs[i]=bs[i-1];
if(a[i]>p)bs[i]=bs[i-1]|(bs[i-1]<<(a[i]-p));
if(a[i]<p)bs[i]=bs[i-1]|(bs[i-1]>>(p-a[i]));
}
if(!bs[n].test(half-p)){puts("-1");continue;}
for(int i=n,now=half-p;i;i--){
if(bs[i-1].test(now-a[i]+p))sd[i]=true,now=now-a[i]+p;
else sd[i]=false;
}
// for(int i=1;i<=n;i++)printf("%d ",sd[i]);puts("");
sort(ord+1,ord+n+1,[](int x,int y){return sd[x]<sd[y];});
for(int i=1;i<n;i++)if(!sd[ord[i]]&&sd[ord[i+1]])SOLVE(i-1,i,ord),SOLVE(n-i-1,n-i,ord+i);
}
for(auto i:v){for(auto j:i)printf("%d ",j);puts("");}
}
return 0;
}
IV.[CodeChef]Scrupulous Robbery Plan
对于一组物品，设其大小为 \(a\)，则若 \(a\) 是偶数，我们将总是可以把它分成两个大小为 \(\dfrac a2\) 的集合，满足两个集合中元素重量差至多是 \(n\)。
我们考虑自初态 \((k,w)\) 出发，每次尝试将状态折半。
设当前我们需要知道大小为 \(a\)，重量在区间 \([l,r]\) 中的最优方案，记作 \(f(a,[l,r])\)。若 \(a\) 是偶数，就要尝试处理 \(f(a/2,[(l-n)/2,(y+n)/2])\)，然后平方背包合并一下即可。若 \(a\) 是奇数，则求出 \(f(a-1,[l-n,r])\) 后再手动背包一位即可。
复杂度平方 \(\log\)。
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll fni=0xc0c0c0c0c0c0c0c0;
int n,m,w,a[1010];
ll f[1001000],g[1001000];
void solve(int k,int l,int r){
if(!k){for(int i=l;i<=r;i++)f[i-l]=fni;if(l==0)f[0]=0;return;}
if(k&1){
int L=max(l-n,0),R=r;
solve(k-1,L,R);
for(int i=l;i<=r;i++)g[i-l]=fni;
for(int i=L;i<=R;i++)for(int j=1;j<=n;j++)if(i+j>=l&&i+j<=r)g[i+j-l]=max(g[i+j-l],f[i-L]+a[j]);
for(int i=l;i<=r;i++)f[i-l]=g[i-l];
// printf("%d:[%d,%d]\n",k,l,r);
// for(int i=l;i<=r;i++)printf("%lld ",f[i-l]);puts("");
return;
}
int L=max((l-n)/2,0),R=min((r+n+1)/2,w);
solve(k>>1,L,R);
for(int i=l;i<=r;i++)g[i-l]=fni;
for(int i=L;i<=R;i++)for(int j=L;j<=R;j++)if(i+j>=l&&i+j<=r)g[i+j-l]=max(g[i+j-l],f[i-L]+f[j-L]);
for(int i=l;i<=r;i++)f[i-l]=g[i-l];
// printf("%d:[%d,%d]\n",k,l,r);
// for(int i=l;i<=r;i++)printf("%lld ",f[i-l]);puts("");
}
int main(){
scanf("%d%d%d",&n,&m,&w);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
solve(m,w,w);
printf("%lld\n",f[0]);
return 0;
}
V.CF756E Byteland coins
这种题的套路是从高位往低位转移，维护当前状态中，目前总和与目标差多少个 \(\prod\limits_{j=1}^ia_i\)。
但是粗略一想就会发现，值域可能需要开到 \(\sum b\)，进而复杂度就是平方级别的，看上去不太妙。
但是考虑一个 \(b_i\)，其对 \(f_j(j>i)\) 的值域贡献是 \(\dfrac{b_i}{\prod\limits_{k=i+1}^ja_k}\)，而这个东西会在 \(20\log\) 步内衰减到零，且每次衰减至少减半。也就是说，值域上界总和事实上是 \(O(20n)\) 的。
那么大力 DP 就完事了。
注意到转移是一个多重背包计数。因为所有费用都为一，因此这种多重背包的转移可以用前缀和简单优化到线性。
但是这题问题反而在于，将 \(m\) 拆分到每一位上的过程需要一个好的高精板子。\(\log^2m\) 暴力搞复杂度会比较危险，要仔细优化常数。可以尝试使用压位高精度。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
namespace Bignum{
const int lim=1e9;
const int LG=9;
char s[10100];
int d[10100],m;
void getarr(){
scanf("%s",s);
int S=strlen(s);
reverse(s,s+S);
for(int i=0;i<S;i++)s[i]-='0';
for(int i=0;i<S;i+=LG,m++)for(int j=i+LG-1;j>=i;j--)d[m]=10*d[m]+s[j];
// for(int i=m-1;i>=0;i--)printf("%09d",d[i]);puts("");
}
int divide(int a){
ll rem=0;
for(int i=m-1;i>=0;i--)rem=lim*rem+d[i],d[i]=rem/a,rem%=a;
while(m&&!d[m-1])m--;
// printf("%d|",a);for(int i=m-1;i>=0;i--)printf("%09d",d[i]);printf(":%d\n",rem);
return rem;
}
int get(int a){
ll val=0;
for(int i=m-1;i>=0;i--){
val=lim*val+d[i];
if(val>a)return -1;
}
return val;
}
}
int n,a[300100],b[300100],c[300100],f[300100],g[300100];
double sz[300100];int lim[300100];
int main(){
scanf("%d",&n);
a[1]=1;for(int i=2;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]),sz[i]=sz[i-1]/a[i]+b[i],lim[i]=sz[i]+1;
Bignum::getarr();
for(int i=1;i<=n;i++)if(a[i]==1)c[i]=0;else c[i]=Bignum::divide(a[i]);
// for(int i=1;i<=n;i++)printf("%d ",c[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",lim[i]);puts("");
int tmp=Bignum::get(lim[n]);
if(tmp==-1){puts("0");return 0;}
f[tmp]=1;
for(int i=n;i;i--){
for(int j=lim[i];j;j--)(f[j-1]+=f[j])%=mod;
for(int j=0;j+b[i]+1<=lim[i];j++)(f[j]+=mod-f[j+b[i]+1])%=mod;
for(int j=0;j<=lim[i]&&1ll*j*a[i]+c[i]<=lim[i-1];j++)g[j*a[i]+c[i]]=f[j];
for(int j=0;j<=lim[i-1];j++)f[j]=g[j],g[j]=0;
// for(int j=0;j<=lim[i-1];j++)if(f[j])printf("[%d,%d]",j,f[j]);puts("");
}
printf("%d\n",f[0]);
return 0;
}
VI.黄金矿工
题意：有 \(n\) 个物品，第 \(i\) 个物品的坐标是 \(x_i\)，价值是 \(v_i\)，取走这个物品需要的代价是 \(x_iv_i\)。保证 \(x\) 序列严格递增。
有 \(m\) 次操作，每次操作或者删去某个物品，或者询问总代价不超过 \(V\) 时能获得的最大代价。
\(V\) 的上界 \(K\) 会给出。
数据范围：\(n,K\leq2\times10^6,1\leq x_iv_i\leq K,m\leq5000\)。
首先删去物品时光倒流一下就变成添加物品。
假如没有添加物品操作，那这个问题是经典的：我们倒序 DP，仅考虑坐标 \(\geq i\) 的所有物品时，总收益不超过 \(\dfrac Vi\)。于是我们设 \(f_i\) 表示收益不小于 \(i\) 时需要的最小代价，总复杂度就是调和级数的。
现在有添加物品操作。注意到 \(x_iv_i\) 这一项中有乘积的形式，那么我们自然想到根号分治。我们在 \(B\) 处分块，则 \(>B\) 的物品带来的收益不超过 \(\dfrac KB\)，\(<B\) 的物品不超过 \(B\) 个。那么插入的总复杂度就可以做到 \(BK+\dfrac{mK}B\geq K\sqrt m\)。
现在要合并两个背包。因为较大一半的值域只到 \(\dfrac KB\)，所以我们暴力枚举在其中用掉多少代价，然后在另一半中用指针处理，复杂度就是 \(\dfrac KB\times m=K\sqrt m\) 的。
总复杂度 \(K\sqrt m\)。
（做题时分块一直在往 \(\sqrt n\) 分，然后复杂度就一直不太对，就很难受）
代码：
#include<bits/stdc++.h>
using namespace std;
const int BBB=100;
void read(int&x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int n,m,W,pos[2001000],val[2001000],tp[5010],P[5010],res[5010];
int f[4001000],F;//F: DP of the upper half
int g[4001000],G;//G: DP of the lower half
void Finsert(int i){
for(int j=F;j>=0;j--){
f[j+val[i]]=min(f[j+val[i]],f[j]+pos[i]*val[i]);
if(f[j+val[i]]<=W)F=max(F,j+val[i]);
}
for(int j=F;j;j--)f[j-1]=min(f[j-1],f[j]);
}
void Ginsert(int i){
for(int j=G;j>=0;j--){
g[j+val[i]]=min(g[j+val[i]],g[j]+pos[i]*val[i]);
if(g[j+val[i]]<=W)G=max(G,j+val[i]);
}
for(int j=G;j;j--)g[j-1]=min(g[j-1],g[j]);
}
bool ban[2001000];
int main(){
freopen("miner.in","r",stdin);
freopen("miner.out","w",stdout);
read(n),read(m),read(W);
for(int i=1,x,y;i<=n;i++)read(pos[i]),read(val[i]);
memset(f,0x3f,sizeof(f)),f[0]=0;
memset(g,0x3f,sizeof(g)),g[0]=0;
for(int i=1;i<=m;i++){read(tp[i]),read(P[i]);if(tp[i]==1)ban[P[i]]=true;}
for(int i=n;i;i--)if(!ban[i])(pos[i]>BBB?Finsert:Ginsert)(i);
for(int i=m;i;i--)
if(tp[i]==1)(pos[P[i]]>BBB?Finsert:Ginsert)(P[i]);
else for(int j=0,k=upper_bound(g,g+G+1,P[i])-g-1;j<=F;j++){
while(k&&j+k>res[i]&&f[j]+g[k]>P[i])k--;
if(f[j]+g[k]<=P[i])res[i]=max(res[i],j+k);
}
for(int i=1;i<=m;i++)if(tp[i]==2)printf("%d\n",res[i]);
return 0;
}
VII.枝江往事
有变量 \(x\)，初始为 \(1\)。给定 \(n\) 次操作，第 \(i\) 次操作为两类之一：
- 将 \(x\) 乘以 \(y_i\)，对 \(p\) 取模。
- 将 \(x\) 赋为 \(y_i\)。
你可以任意重排给定的 \(n\) 次操作。在一切可能的 \(n!\) 种重排方案中，\(x\) 有若干终值；求 \([0,p)\) 中有多少终值无法被任何重排表出。
数据范围：\(n,p\leq10^6\)。保证 \(p\) 为质数，\(0\leq y_i<p\)。
首先若一次赋值都没有，显然结果唯一。否则，终值是从最后一次赋值开始的所有乘法之积。
乘法不好搞，我们取离散对数变成加法与对 \(\varphi(p)\) 取模。特别考虑 \(0\) 的场合。
那么乘法操作就是 01 背包，显然可以 bitset 优化……但是 \(10^6\) 过不去。
考虑一次更新是对所有 \(i\) 用 \(i\) 更新 \(i+y\)。假如让每个位置都仅被更新一次那么复杂度是均摊正确的。
考虑分治更新。当前分治区间若是 \([l,r]\)，则用哈希判 \([l,r]\) 和 \([l+y,r+y]\) 是否完全相同，如果否则递归更新
这个算法有一个问题，就是当左侧是 \(0\) 但右侧是 \(1\) 时，也会递归下去。
考虑将 \(i\to i+y\) 连边，则每有一个 \(0\to 1\) 也会有一个 \(1\to0\)，换句话说就是所有被更新的 \(1\to 0\) 数量等于被访问的 \(0\to 1\) 数量，也即方法是正确的。
时间复杂度对数平方。
代码：
#include<bits/stdc++.h>
using namespace std;
int p,phi,n,rt,LG[1001000],res;
int ksm(int x,int y=p-2){int z=1;for(;y;y>>=1,x=1ll*x*x%p)if(y&1)z=1ll*z*x%p;return z;}
vector<int>fv,v;
bool f[1001000];
int ksm(int x,int y,int mod){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int _;
struct Hash{
int p,b,m;
int pov[1001000],inv[1001000];
int bit[1001000],tms[1001000],rtt[1001000];
void ADD(int&x,int y){if((x+=y)>=m)x-=m;}
void init(int B,int M){
b=B,m=M,p=ksm(b,m-2,m);
pov[0]=inv[0]=1;
for(int i=1;i<=1000000;i++)pov[i]=1ll*pov[i-1]*b%m,inv[i]=1ll*inv[i-1]*p%m;
}
void turnon(int x){x++;for(int i=x;i<=phi;i+=i&-i)ADD(bit[i],pov[x]);}
int ask(int x){
if(tms[++x]==_)return rtt[x];tms[x]=_;
int ret=0;for(int i=x;i;i-=i&-i)ADD(ret,bit[i]);return rtt[x]=ret;
}
int query(int l,int r){
if(l<=r)return 1ll*(ask(r)+m-ask(l-1))*inv[l]%m;
return(1ll*(ask(phi-1)+m-ask(l-1))*inv[l]+1ll*ask(r)*pov[phi-l])%m;
}
void reset(){for(int i=1;i<=phi;i++)bit[i]=0;}
}h1,h2;
vector<int>u;
#define mid ((l+r)>>1)
void solve(int l,int r,int x){
if(h1.query(l,r)==h1.query((l+x)%phi,(r+x)%phi)/*&&h2.query(l,r)==h2.query((l+x)%phi,(r+x)%phi)*/)
return;
if(l==r){
if(f[l]&&!f[(l+x)%phi])u.push_back((l+x)%phi);
return;
}
solve(l,mid,x),solve(mid+1,r,x);
}
void read(int&x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
void mina(){
read(p),read(n);
phi=p-1,fv.clear(),res=0;
for(int i=2,x=phi;i<=x;i++)if(!(x%i)){
fv.push_back(i);
while(!(x%i))x/=i;
}
for(rt=1;;rt++){
bool ok=true;
for(auto i:fv)if(ksm(rt,phi/i)==1){ok=false;break;}
if(ok)break;
}
for(int i=0,j=1;i<phi;i++,j=1ll*j*rt%p)LG[j]=i,f[j]=false;
h1.reset(),h2.reset(),v.clear();
bool ok0=false,oks=false;
int qwq=0;
for(int i=1,x,y;i<=n;i++){
read(x),read(y);
if(!y){ok0=true;continue;}
if(!x)oks=true;
y=LG[y];
if(x==0){if(!f[y])f[y]=true,h1.turnon(y)/*,h2.turnon(y)*/,qwq++;}
else v.push_back(y);
}
if(!oks){printf("%d\n",p-1);return;}
res+=!ok0;
for(auto x:v){
_++;
solve(0,phi-1,x);
for(auto y:u)f[y]=true,h1.turnon(y)/*,h2.turnon(y)*/;
u.clear();
}
for(int i=0;i<phi;i++)res+=!f[i];
printf("%d\n",res);
}
int T;
int main(){
freopen("zjiang.in","r",stdin);
freopen("zjiang.out","w",stdout);
h1.init(3,1004535809)/*,h2.init(5,1e9+9)*/;
read(T);while(T--)mina();
return 0;
}