P10310 题解

· · 题解

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

首先 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);
}