自动搬运

查看原文

来自洛谷，原作者为

	maojun 猫君

搬运于2025-08-24 22:56:48，当前版本为作者最后更新于2024-04-06 08:48:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不同于官方题解的维护方法。

---

首先 $f(S_{l\dots r})$ 给 $f_k(1,n)$ 的贡献为 ${l-1+k-1\choose k-1}{n-r+k-1\choose k-1}$，具体可以考虑这 $k$ 次是怎么从 $[1,n]$ 取子区间取到 $[l,r]$ 的。

记 $C_i={i+k-1\choose k-1}$，则 $C_0=1,C_i=\frac{i+k-1}iC_{i-1}$，可 $O(n)$ 递推出。

于是 $\mathrm{ans}=\sum\limits_{l=1}^n\sum\limits_{r=l}^nf(S_{l\dots r})C_{l-1}C_{n-r}=\sum\limits_{l=1}^nC_{l-1}\sum\limits_{r=l}^nf(S_{l\dots r})C_{n-r}$。

考虑对于每个左端点 $S_l=\texttt0$ 一遍 dp 求出 $\sum\limits_{r=l}^nf(S_{l\dots r})C_{n-r}$。

则对于一个 $S_r=\texttt1$，其方案数为所有 $S_i=\texttt1,S_{i+1}=\texttt0$ 的“合法点”$i$ 的方案数之和。

记一个 $dp$ 表示前缀合法点的方案数之和，$sum$ 表示所有 $S_r=\texttt1$ 点的方案数乘上系数之和。

则若 $S_r=\texttt1$，$sum\gets sum+dp\times C_{n-r}$，若还有 $S_{r+1}=\texttt0$，$dp\gets dp+dp$。

最后 $\mathrm{ans}\gets\mathrm{ans}+sum\times C_{l-1}$，这样得到了一个 $O(n^2)$ 的做法。

for(int i=1;i<=n;i++)if(s[i]=='0'){
  int dp=1,sum=0;
  for(int j=i+1;j<=n;j++)if(s[j]=='1'){
    sum=(sum+dp*C[n-j])%MOD;
    if(s[j+1]=='0')dp=dp*2%MOD;
  }
  res=(res+sum*C[i-1])%MOD;
}

注意到对于每个 $r$ 关于 $dp$ 和 $s$ 的转移是固定的，而且正好符合加乘矩阵的逻辑，考虑矩乘。

举个例子，若 $S_i=\texttt1$ 且 $S_{i+1}=\texttt0$，则有这样的转移。

$$\begin{bmatrix}s'\\dp'\end{bmatrix}=\begin{bmatrix}s\\dp\end{bmatrix}\begin{bmatrix}1&C_{n-i}\\0&2\end{bmatrix} $$

初始时 $\begin{bmatrix}s\\dp\end{bmatrix}=\begin{bmatrix}0\\1\end{bmatrix}$，维护一个转移矩阵的后缀和即可，复杂度 $O(n\omega^3)$，其中 $\omega=2$。

void solve(){
	scanf("%d%lld%s",&n,&k,s+1);k%=MOD;
	C[0]=1;for(int i=1;i<=n;i++)C[i]=C[i-1]*(i+k-1)%MOD*inv[i]%MOD;
	ll res=0;mtx A,M,T;
	A[0][1]=M[0][0]=M[1][1]=1;	// A 为初始矩阵，M 为后缀积，初始为单位矩阵
	for(int i=n;i;i--)
		if(s[i]=='0')res=(res+(A*M)[0][0]*C[i-1])%MOD;
		else{
			T[0][0]=1;T[1][0]=C[n-i];
			T[1][1]=1+(s[i+1]=='0');
			M=T*M;				// 注意顺序，先转移 i 的再转移 i 之后的
		}
	printf("%lld\n",res);
}