Saintex 1分钟就切啦,有什么好说哒!
首先可能想到设 \(c_{i,j}\) 表示(i,j)被操作的次数,那么答案很好求。
但是这个数量并不好记录。
如果仅仅钦定(i,j)从小到大之类的东西也不好搞。
所以考虑钦定其他的东西。
设 \(dp_{i,j,k}\) 表示前 i 位,有 j 个操作(x,y)满足\(x<y\leq i\),k 个操作满足\(i\leq x<y\)。
我们分别称为第一类和第二类操作。
然后 \(j\times 2+k=sum_i\) 所以省去第三维。
先给转移式
for(int i=0;i<n;i++){
int oo=i&1,op=oo^1,o1=s[i]>>1;
for(int j=0;j<=up;j++) dp[op][j]=0;
for(int j=0;j<=o1;j++){
int pp=s[i]-(j<<1),o2=min(pp,b[i+1]);
for(int k=0;k<=o2;k++){
int jj=b[i+1]-k;
dp[op][j+k]=(dp[op][j+k]+dp[oo][j]*C(pp,k)%Mod*C(j+pp+jj,jj)%Mod)%Mod;
}
}
}
后面一个 C 表示给需要的第二类操作的位置,前一个 C 表示给前面所需的第二类操作顺序,不重不漏。