转载自https://blog.csdn.net/weixin_37517391/article/details/83821752

题解

其实这题不难,只要想到了前缀和差分就基本OK了. 我们要求的是第$i$项的式子: $F(i)=(a_1+a_2+...+a_i)^k+(a_2+...+a_i)^k+...+a_i^k$ 记$S_i = a_1 + a_2 +...+a_i,S_0=0$ $F(i) = (S_i-S_0)^k+(S_i-S_1)^k+...+(S_i-S_{i-1})^k$ 二项式定理展开： $F(i) = \sum_{t=0}^kC_k^tS_i^t(-S_0)^{k-t} +  \sum_{t=0}^kC_k^tS_i^t(-S_1)^{k-t} +...+ \sum_{t=0}^kC_k^tS_i^t(-S_{i-1})^{k-t}$ 整理得： $F(i) = \sum_{t=0}^k C_k^t S_i^t(-1)^{k-t} (S_0^{k-t}+S_1^{k-t}+...+S_{i-1}^{k-t})$ 再记： $SS[i][j] = S_0^i + S_1^i + ... + S_j^i$ 那么 $F(i) = \sum_{t=0}^k C_k^t S_i^t(-1)^{k-t} (SS[k-t][i-1])$ 注意到$SS$可以$O(nk)$预处理出来，$S$也可以$O(nk)$预处理出来，而$F(i)$就可以$O(k)$出来。

代码

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #define pr(x) std::cout << #x << ':' << x << std::endl
 5 #define rep(i,a,b) for(int i = a;i <= b;++i)
 6 
 7 typedef long long LL;
 8 const int N = 100010;
 9 const LL P = 1e9+7;
10 int T,n,k;
11 char s[N];
12 long long S[101][N],SS[101][N];
13 long long C[110][110];
14 void init() {
15     C[0][0] = 1;
16     for(int i = 1;i <= 100;++i) {
17         C[i][0] = 1;
18         for(int j = 1;j <= i;++j) {
19             C[i][j] = (C[i-1][j-1] + C[i-1][j]) % P;
20         }
21     }
22 }
23 int main() {
24     std::ios::sync_with_stdio(false);
25     init();
26     std::cin >> T;
27     while(T--) {
28         std::cin >> n >> k;
29         std::cin >> s;
30         for(int i = 0;i <= n;++i) S[0][i] = 1;
31         for(int i = 1;i <= n;++i) S[1][i] = (s[i-1]-'0') + S[1][i-1] ;
32         for(int i = 2;i <= k;++i) 
33             for(int j = 1;j <= n;++j)
34                 S[i][j] = S[1][j] * S[i-1][j] % P;
35         
36         SS[0][0] = 1;   //特殊化处理，0^0=1
37 
38         for(int i = 0;i <= k;++i) {
39             for(int j = 1;j <= n;++j) 
40                 SS[i][j] = (SS[i][j-1] + S[i][j])% P;
41         }
42         
43         for(int i = 1;i <= n;++i) {
44             long long ans = 0;
45             for(int j = 0;j <= k;++j) {
46                 long long res = C[k][j]*S[j][i]%P*SS[k-j][i-1]%P;
47                 if((k-j)%2==0) ans = (ans + res) % P;
48                 else ans = (ans - res + P) % P;
49             }
50             if(i != 1) std::cout << " ";
51             std::cout << ans;
52         }
53         std::cout << std::endl;
54     }
55     return 0;
56 }