NOI Online 2021 Round 1 提高组愤怒的小 N

题目链接

P7468 [NOI Online 2021 提高组] 愤怒的小 N

题目大意

有一个无穷 (ab) 串 (S) 和一个二进制正整数 (n)，(S) 通过如下方式构造：

(S) 初始时为包含单个字符 (a) 的字符串
每次我们将 (S) 中的 (a) 换成 (b) ，(b) 换为 (a) ，然后将我们修改过后的串添加到原串后面

若 (S_i=b (0leq i<n))，则有贡献 (f(i)) ，其中 (f(x)=a_0+a_1x+a_2x^2+...+a_{k-1}x^{k-1}) 是一个固定的 (k-1) 次多项式。现在请求出贡献总和对 (10^9+7) 取模后的结果。

(log_2nleq5 imes10^5)， (kleq 500)

思路

这个二进制的提示很明显，我们仔细观察 (S_i=b) 的位置，可以发现都是 (i) 的二进制中 (1) 的个数为奇数的地方，根据这个性质，我们做一个数位 (dp)，设 (dp_{i,j,0/1}) 为二进制前 (i) 位中 “二进制中 (1) 的数量为偶数/奇数的数字” 的 (j) 次方之和，有这样的转移式：

(dp_{0,0,0}=1)
设 (T_{i,0/1}) 为前 (i) 位中 “ (1) 的数量为偶数/奇数的数字” 的集合
(dp_{i,j,p}=dp_{i-1,j,p}+sum_{xin T_{i-1,!p}}(x+2^{i-1})^j)

注意到 (k) 只有 (500) 的级别，我们可以直接对式子二项式展开：

[dp_{i,j,p}=dp_{i-1,j,p}+sum_{l=0}^j dp_{i-1,j-l,!p}cdot2^{(i-1)*l}cdotinom{j}{l} ]

可以发现 (i) 这一维可以滚动掉，空间压成 (O(k)) 的，我们得到了一个 (O(k^2log_2n)) 的 (dp)，计算答案时从前往后一位位贴着 (n) 同样用二项式即可。

这个做法可以获得 (60pts) 的好成绩，考虑继续优化，接下来就是暂时超出我的考场能力水平的操作了：

仔细观察递推式（实际考场上都是打表发现的），首先 (dp_{1,0,0}=dp_{1,0,1}=1)，而每次 (dp_{i,j,0}) 和 (dp_{i,j,1}) 都会受到 (dp_{i-1,j,0}+dp_{i-1,j,1}) 的贡献，而若在 (xleq j-1) 时都满足了 (dp_{i-1,x,0}=dp_{i-1,x,1})，那么这一轮将有 (dp_{i,j,0}=dp_{i,j,1})。

这么一轮轮滚下去，当 (igeq k) 时，所有的 (dp_{i,j,0}) 都和 (dp_{i,j,1}) 相等了，从而奇数的贡献便是总贡献的 (frac{1}{2})，根据这一点，我们先计算 (frac{1}{2}sum_{i=0}^{n-1}f(i)=frac{1}{2}sum_{l=0}^{k-1}(a_lsum_{i=0}^{n-1}i^l)) ，然后再去对答案进行调整，对于 (n) 的后 (k) 位用 (dp) 去贴近，加上 (frac{1}{2}(奇数-偶数)) 。

接下来我们考虑怎么计算 (sum_{i=0}^{n-1}i^l)，一般化地，(sum_{i=0}^n i^m)

关于第二类斯特林数，有这样一个式子：

[n^m=sum_{i=0}^negin{Bmatrix}m\iend{Bmatrix}i!inom{n}{i} ]

感性理解：有 (m) 个不同的球要放到 (n) 个不同的盒子里，(i) 为非空的盒子数量，

(egin{pmatrix}n\iend{pmatrix})：(n) 个盒子里选 (i) 个放，(egin{Bmatrix}m\iend{Bmatrix})：把 (m) 个球放进去，由于这里没有顺序，所以再乘上一个 (i!)

利用这个：

[egin{aligned} sum_{i=1}^{n}i^m&=sum_{i=1}^{n-1}sum_{j=0}^iegin{Bmatrix}m\jend{Bmatrix}j!inom{i}{j}\ &=sum_{j=0}^m j!egin{Bmatrix}m\jend{Bmatrix}sum_{i=1}^{n}inom{i}{j}\ &=sum_{j=0}^m j!egin{Bmatrix}m\jend{Bmatrix}inom{n+1}{j+1}\ &=sum_{j=0}^megin{Bmatrix}m\jend{Bmatrix}frac{(n-1)^underline{j+1}}{j+1} end{aligned} ]

通过 (O(k^2)) 预处理斯特林数，我们可以 (O(k)) 搞定这个求和，进而 (O(k^2)) 求上面那个式子。

最终，我们 (O(log_2n+k^3)) 地解决了本题。

实现细节

逼近 (n) 的后 (k) 位时，不要忘记时刻更新当前奇偶情况。
(500^3=1.25e8)，而本题时限 (1s)，所以尽量把 (inom{n}{m}) 、 (2^i) 和 “ (n) 前 (i) 位的 (j) 次方” 之类的东西全都预处理好。
如果预处理是带参数进去的，记住参数要写 max(2,k)，不然会在 (k=1) 的点上挂掉。

Code

#include<iostream>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define M 504
#define ll long long
#define mod 1000000007
using namespace std;
ll frac[M],C[M][M],S[M][M];
ll inv[M],pow[M*M],a[M],num;
ll dp[M][2],bef[M],p_bef[M][M];
string n;
int k,len;
void prework(int m){
    inv[1]=1,S[0][0]=1,C[0][0]=1,pow[0]=1;
    rep(i,2,m)inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;
    rep(i,1,m)rep(j,1,k)S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%mod;
    rep(i,1,m){
        C[i][0]=1;
        rep(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    rep(i,1,m*m)pow[i]=(pow[i-1]*2)%mod;
}
int main(){
    cin>>n>>k;
    rep(i,0,k-1)cin>>a[i];
    len=n.size();
    prework(max(2,k));
    int parity=0;
    rep(i,0,len-1){
        int t=len-i-1;
        if(t<=k){
            bef[t]=num*pow[t+1]%mod;
            ll mul=1;
            rep(j,0,k-1)p_bef[t][j]=mul,(mul*=bef[t])%=mod;
        }
        num=(num*2+(n[i]=='1'))%mod;
        parity^=(n[i]=='1');
    }
    ll minus[2]={0,0};
    dp[0][0]=1;
    rep(i,0,min(len-1,k)){
        if(i)per(j,k-1,0){
            ll val[2]={dp[j][0],dp[j][1]};
            rep(_,0,1) rep(l,0,j)
                (val[_]+=pow[(i-1)*l]*dp[j-l][1-_]%mod*C[j][l])%=mod;
            dp[j][0]=val[0],dp[j][1]=val[1];
        }
        if(n[len-i-1]=='1'){
            parity^=1;
            rep(_,0,1)rep(_k,0,k-1){
                ll tot=0;
                rep(j,0,_k)(tot+=p_bef[i][j]*dp[_k-j][_]%mod*C[_k][j]%mod)%=mod;
                (minus[parity^_]+=a[_k]*tot%mod)%=mod;
            }
        }
    }
    ll sum=0;
    rep(i,0,k-1){
        ll mul=1,tot=0;
        rep(j,0,i){
            (mul*=num-j)%=mod;
            (tot+=S[i][j]*mul%mod*inv[j+1]%mod)%=mod;
        }
        (sum+=a[i]*tot%mod)%=mod;
    }
    cout<<(sum+minus[1]-minus[0]+mod)*inv[2]%mod<<endl;
    return 0;
}