「KDOI-03」构造数组

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 表示给前面所需的第二类操作顺序,不重不漏。