A Boring Problem UVALive - 7676 （二项式定理+前缀和）

题目链接：

I - A Boring Problem

UVALive - 7676

题目大意：就是求给定的式子。

学习的网址：https://blog.****.net/weixin_37517391/article/details/83821752

思路：证明过程在上面的博客中说了，大体意思就是预处理出两个前缀和，然后通过二项式定理化简式子就好了。

AC代码：

 #include<bits/stdc++.h>
 using namespace std;
 # define ll long long
 # define inf 0x3f3f3f3f
 const int maxn = 2e5+;
 const int mod = 1e9+;
 ll c[+][+];
 char str[maxn];
 ll s1[+][maxn],s2[+][maxn];
 ll ind(int t1,int t2)
 {
     if(t2&)
         return -1ll;
     return 1ll;
 }
 void init()
 {
     c[][]=1ll;
     for(int i=; i<=; i++)
     {
         c[i][]=1ll;
         for(int j=; j<=i; j++)
         {
             c[i][j]=(c[i-][j]+c[i-][j-])%mod;
         }
     }
 }
 int  main()
 {
     init();
     int T;
     scanf("%d",&T);
     while(T--)
     {
         int n,k;
         scanf("%d %d",&n,&k);
         scanf("%s",str);
         for(int i=; i<=n; i++)
         {
             s1[][i]=1ll;
         }
         for(int i=; i<=n; i++)
         {
             s1[][i]=(s1[][i-]+(ll)(str[i-]-''));
         }
         for(int i=; i<=k; i++)
         {
             for(int j=; j<=n; j++)
             {
                 s1[i][j]=s1[i-][j]*s1[][j]%mod;
             }
         }
         s2[][]=1ll;
         for(int i=; i<=n; i++)
         {
             for(int j=; j<=k; j++)
             {
                 s2[j][i]=(s2[j][i-]+s1[j][i])%mod;
             }
         }
         for(int i=; i<=n; i++)
         {
             ll ans=;
             for(int j=; j<=k; j++)
             {
                 ll tmp=c[k][j]*s1[j][i]%mod*s2[k-j][i-]%mod;
                 if(ind(-,k-j)==1ll)
                     ans=(ans+tmp)%mod;
                 else
                     ans=(ans-tmp+mod)%mod;
             }
             if(i!=)
                 printf(" ");
             printf("%lld",ans);
         }
         printf("\n");
     }
     return ;
 }