A Boring Problem UVALive

题目链接：

I - A Boring Problem

UVALive - 7676

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

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

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

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn = 2e5+100;
 6 const int mod = 1e9+7;
 7 ll c[100+10][100+10];
 8 char str[maxn];
 9 ll s1[100+10][maxn],s2[100+10][maxn];
10 ll ind(int t1,int t2)
11 {
12     if(t2&1)
13         return -1ll;
14     return 1ll;
15 }
16 void init()
17 {
18     c[0][0]=1ll;
19     for(int i=1; i<=100; i++)
20     {
21         c[i][0]=1ll;
22         for(int j=1; j<=i; j++)
23         {
24             c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
25         }
26     }
27 }
28 int  main()
29 {
30     init();
31     int T;
32     scanf("%d",&T);
33     while(T--)
34     {
35         int n,k;
36         scanf("%d %d",&n,&k);
37         scanf("%s",str);
38         for(int i=0; i<=n; i++)
39         {
40             s1[0][i]=1ll;
41         }
42         for(int i=1; i<=n; i++)
43         {
44             s1[1][i]=(s1[1][i-1]+(ll)(str[i-1]-'0'));
45         }
46         for(int i=2; i<=k; i++)
47         {
48             for(int j=1; j<=n; j++)
49             {
50                 s1[i][j]=s1[i-1][j]*s1[1][j]%mod;
51             }
52         }
53         s2[0][0]=1ll;
54         for(int i=1; i<=n; i++)
55         {
56             for(int j=0; j<=k; j++)
57             {
58                 s2[j][i]=(s2[j][i-1]+s1[j][i])%mod;
59             }
60         }
61         for(int i=1; i<=n; i++)
62         {
63             ll ans=0;
64             for(int j=0; j<=k; j++)
65             {
66                 ll tmp=c[k][j]*s1[j][i]%mod*s2[k-j][i-1]%mod;
67                 if(ind(-1,k-j)==1ll)
68                     ans=(ans+tmp)%mod;
69                 else
70                     ans=(ans-tmp+mod)%mod;
71             }
72             if(i!=1)
73                 printf(" ");
74             printf("%lld",ans);
75         }
76         printf("
");
77     }
78     return 0;
79 }