VJ193259 I - A Boring Problem

Problem

给定数字串 S，求如下表达式的值：

$$ \sum\limits_{j=1}^{i}( \sum\limits_{l=j}^{i} S(l) )^{k} (i \in [1, N]) $$

Solution

用前缀和转化该式。令 \( pre(i) = \sum\limits_{j=1}^{i}( S(j) ) \) , 则 \( (\sum\limits_{l=j}^{i} S(l) )^{k} = ( pre(i)-pre(j-1) )^{k} \) . 原式转化为：

$$ \sum\limits_{j=1}^{i}( pre(i)-pre(j-1) )^{k} $$

二项展开，得：

$$ \sum\limits_{j=1}^{i}( \sum\limits_{p=0}^{k}( C_{k}^{p} (pre(i)^{k-p}) (-pre(j-1))^{p} ) ) $$

将内外求和对调，使得可以预处理前缀和的和的p次方。式子化为：

$$ \sum\limits_{p=0}^{k}( C_{k}^{p} (pre(i)^{k-p}) \times ( \sum\limits_{j=1}^{i} (-pre(j-1))^{p} ) ) $$

预处理 \( \sum\limits_{j=1}^{i} (-pre(j-1))^{p} ; ( i\in[1, N], p\in[0, K] ) \), 复杂度 O(N*K). 对 \( i \in [1, N] \), 处理每个答案，复杂度也是 O(N*K).

坑点：
每个case末尾输出空格PE. 最后不输出换行会WA... 于是我从PE改到了WA...

Code

#include <cstdio>
#include <cstring>

typedef long long LL;
const LL MOD=1e9+7;

const int MAXN=5e4+10;
char S[MAXN];
LL pre[MAXN];
LL spre[MAXN][110];
LL ppre[MAXN][110];

LL C[110][110];
void init()
{
    C[0][0]=1;
    for (int i=1;i<=100;++i)
    {
        C[0][i]=C[i][i]=1;
        for (int j=1;j<i;++j)
        {
            C[j][i]=(C[j-1][i-1]+C[j][i-1])%MOD;
        }
    }

}

LL qp(LL v,LL e)
{
    LL sum=1;
    LL r=v;
    while (e)
    {
        if (e&1) sum=(sum*r)%MOD;
        r=(r*r)%MOD; e>>=1;
    }
    return sum;
}

int N,K;

int main()
{
    init();
    int _T;
    scanf("%d",&_T);
    while (_T--)
    {
        scanf("%d%d",&N,&K);
        scanf("%s",S);
        pre[0]=S[0]-'0';
        for (int i=1;i<N;++i) {
            pre[i]=(pre[i-1]+(S[i]-'0'))%MOD;
        }
        for (int i=0;i<N;++i) {
            ppre[i][0]=1;
            for (int k=1;k<=K;++k)
                ppre[i][k]=(ppre[i][k-1]*pre[i])%MOD;
        }
        for (int k=0;k<=K;++k) {
            spre[0][k]=(k==0)?1:0;
            for (int i=0;i<N;++i)
                spre[i+1][k]=(spre[i][k]+ppre[i][k])%MOD;
        }
        for (int i=0;i<N;++i) {
            LL ans=0;
            for (int k=0;k<=K;++k) {
                //printf("-%d %lld %lld %lld ",k,C[k][K],qp(pre[i],K-k),spre[i][k]);
                //printf("%lld\n",C[k][K]*qp(pre[i],K-k)*spre[i][k]*(k&1?-1:1));
                ans=(MOD+ans+C[k][K]*ppre[i][K-k]%MOD*spre[i][k]%MOD*(k&1?-1:1))%MOD;
            }
            printf("%lld%c",ans,i==N-1?'\n':' ');
        }
    }

    return 0;
}