A Boring Problem UVALive - 7676

16年北京现场赛的题，全场过的队30+。

初看只知道 O(N^2logK)的暴力，以为是什么变换。

仔细发现活用 二项式定理 就行。

 #include <bits/stdc++.h>

 using namespace std;

 #define fst first

 #define scd second

 #define pb(x) push_back((x))

 #define mkp(x,y) make_pair((x),(y))

 #define ist(x) insert((x))

 typedef long long ll;

 typedef pair<int ,int > pii;

 typedef pair<ll ,ll > pll;

 typedef vector< int > vi;

 ll gcd(ll a,ll b){ return b==?a:gcd(b,a%b);}

 ll qPow(ll a,ll b,ll mod){ ll ret=1ll;while(b){ if(b&) ret=ret*a%mod;a=a*a%mod;b>>=;} return ret; }

 const ll mod=1e9+;

 const int maxn=5e4+;

 ll P[maxn][]; // P[i][k] 代表 前i个数字之和的k次方

 ll Pre[maxn][];// Pre[i][k] 代表 前i个P[i][k]的和

 ll F[],INV[];

 char raw[maxn];

 int N,K;

 void init(){

     P[][]=;

     for(int i=;i<=N;++i){

         P[i][]=;

         P[i][]=(P[i-][]+raw[i-]-'')%mod;

         for(int j=;j<=K;++j)

             P[i][j]=P[i][j-]*P[i][]%mod;

     }

     Pre[][]=;// 0^0 =1

     for(int j=;j<=K;++j){

         for(int i=;i<=N;++i)

                 Pre[i][j]=(Pre[i-][j]+P[i][j])%mod;

     }

 }

 ll getC(int i,int j){

     if(j==) return 1ll;

     return F[i]*INV[i-j]%mod*INV[j]%mod;

 }

 int main(){

     F[]=1ll;

     for(ll i=;i<=;++i)

         F[i]=F[i-]*i%mod;

     INV[]=qPow(F[],mod-,mod);

     for(ll i=;i>=;i--)

         INV[i]=(i+)*INV[i+]%mod;

     int Tests;

     scanf("%d",&Tests);

     while(Tests--){

         scanf("%d%d",&N,&K);

         scanf("%s",raw);

         init();

         ll ans;

         for(int i=;i<=N;++i){

             ans=0ll;

             for(int j=;j<=K;++j){

                 if(j&)

                     ans=(ans-getC(K,j)*P[i][K-j]%mod*Pre[i-][j]%mod+mod)%mod;

                 else

                     ans=(ans+getC(K,j)*P[i][K-j]%mod*Pre[i-][j]%mod)%mod;

             }

             printf("%lld%c",ans,i==N?'\n':' ');

         }

     }

     return ;

 }

(代码写的常数有点大，应该是mod多了，，，