CF1093F Vasya and Array

CF1093F 加强版。

Niko 有一个长度为 $n$ 的整数序列 $a$ 以及两个整数 $k,\text{m}$，保证 $a_i\in[1,k]\cup\{-1\}$。

求有多少种将 $a$ 中的 $-1$ 替换为 $[1,k]$ 中的整数的方式，使得 $a$ 中不存在长度为 $\text{m}$ 的连续相同区间。答案对 $10^9+7$ 取模。

$n,k,m\le 2\times 10^6$。

原版支持 $\mathcal{O}(nk)$，加强版只能 $\mathcal{O}(n)$。

先看简单版（虽然没有什么用处）：

定义 $f_{i,j}$ 表示前 $i$ 个以 $j$ 结尾的方案数，那么我们只需要枚举连续的 $j$ 的个数就行：

$$f_{i,j}=\sum_k(\sum_p f_{k,p})-f_{k,j}$$

没了。

令 $f_i$ 表示前 $i$ 个的方案数，$b_i$ 表示 $i$ 之前第一个 $a_i\ne -1$ 的位置，$l_i$ 表示 $i$ 之前第一个 $\ne -1$ 且 $\ne a_{b_i}$ 的位置。$W(i,j)$ 表示在 $i$ 到 $j$ 之间填充同一个数的方案数，$F_i$ 表示 $i$ 的容斥系数，则：

$$W(i,j)=\begin{cases}k&i>b_i\\ 1&b_i\ge i>l_i\\ 0&l_i\ge i \end{cases}$$

且：

$$f_i=\sum_j f_jW(j,i)F_{i-j+1}$$

$W(i,j)$ 通过 $b_i,l_i$ 和合适的分类讨论可以轻松解决，所以我们的主要问题就是如何处理或求出 $F_j$。

令 $F(x)$ 表示 $F$ 的生成函数，则由于我们知道，若干个颜色相同的连续段拼在一起后，他们的必须为 $<m$ 是 $1$，$\ge m$ 是 $0$。因此有：

$$\frac{1}{1-F(x)}=\frac{1-x^m}{1-x}$$

解得：对于 $L\equiv 1\pmod m$，$F_L=1$；$L\equiv0\pmod m$，$F_L=-1$；其余为 $0$。

因此就很简单了，只需要令 $g$ 表示同余意义下的前缀和，就可以十分简单的写出了。复杂度 $\mathcal{O}(n)$。

#include <bits/stdc++.h>
using namespace std;
const int N=2000010,P=1000000007;
int n,K,m,a[N],f[N],g[N],b[N],l[N];
int main(){
    scanf("%d%d%d",&n,&K,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=n;i++){
        b[i]=(a[i]<0?b[i-1]:i);
        l[i]=(a[i]<0||a[i]==a[b[i-1]]?l[i-1]:b[i-1]);
    }
    auto L=[&](int x,int y){return x-(x-y%m+m)%m;};
    f[0]=g[0]=1;
    for(int i=1;i<=n;i++){
        auto calc=[&](int t,int c){
            int x1=L(i-1,t),x2=L(b[i]-1,t),x3=L(l[i]-1,t);
            int A=(x1<0?0:g[x1]),B=(x2<0?0:g[x2]),C=(x3<0?0:g[x3]);
            int t1=1ll*K*(A-B+P)%P,t2=(B-C+P)%P,t3=(t1+t2)%P;
            (f[i]+=(c==-1?P-t3:t3))%=P;
        };
        calc(i-1,1),calc(i,-1);
        g[i]=(f[i]+(i>=m?g[i-m]:0))%P;
    }
    printf("%d",f[n]);
    return 0;
}