A Boring Problem

題解

其實這題不難,只要想到了前綴和差分就基本OK了.

我們要求的是第$i$項的式子:

$F(i)=(a_1+a_2+...+a_i{)}^k+(a2+...+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}^k{C}_k^t{S}_i^t(?S_0{)}^{k?t}+{\sum }_{t=0}^k{C}_k^t{S}_i^t(?S_1{)}^{k?t}+...+{\sum }_{t=0}^k{C}_k^t{S}_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?1}^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(n)$預處理出來,而$F(i)$就可以$O(k)$得到.

注意!$S_0^0=1$

代碼

#include <iostream> #include <algorithm> #include <cstring> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i)typedef long long LL; const int N = 100010; const LL P = 1e9+7; int T,n,k; char s[N]; long long S[101][N],SS[101][N]; long long C[110][110]; void init() {C[0][0] = 1;for(int i = 1;i <= 100;++i) {C[i][0] = 1;for(int j = 1;j <= i;++j) {C[i][j] = (C[i-1][j-1] + C[i-1][j]) % P;}} } int main() {std::ios::sync_with_stdio(false);init();std::cin >> T;while(T--) {std::cin >> n >> k;std::cin >> s;for(int i = 0;i <= n;++i) S[0][i] = 1;for(int i = 1;i <= n;++i) S[1][i] = (s[i-1]-'0') + S[1][i-1] ;for(int i = 2;i <= k;++i) for(int j = 1;j <= n;++j)S[i][j] = S[1][j] * S[i-1][j] % P;SS[0][0] = 1;for(int i = 0;i <= k;++i) {for(int j = 1;j <= n;++j) SS[i][j] = (SS[i][j-1] + S[i][j])% P;}for(int i = 1;i <= n;++i) {long long ans = 0;for(int j = 0;j <= k;++j) {long long res = C[k][j]*S[j][i]%P*SS[k-j][i-1]%P;if((k-j)%2==0) ans = (ans + res) % P;else ans = (ans - res + P) % P;}if(i != 1) std::cout << " ";std::cout << ans;}std::cout << std::endl;}return 0; }

總結

以上是生活随笔為你收集整理的北京区域赛I题,Uva7676,A Boring Problem,前缀和差分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。