VJ193259 I - A Boring Problem

# VJ193259 I - A Boring Problem

Donny
October 23, 2017
875
-

Tags in blue are handcrafted tags; Tags in green are generated using AutoTag.

## Problem

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

## Solution

$$\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} ) )$$

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

## 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;
}