CS Academy #32 G

题意：

分析：

　　考虑如何求方案数

　　dp[i][j]表示i个数字的和为j的方案数，这是个经典问题，转移有两种，一个是填一个数字1，一个是整体加1

　　然后这个问题并不是求方案数，而是求对应的权值和

　　我们很容易想到dp[i][j]维护对应的m个下降幂Σx^i，最后再用斯特林数还原成m次幂

　　但这样时间复杂度是O(nmk)的，无法接受

　　题解给出了一个很妙的想法，我们去计算每个数字对答案的贡献，我们只关心这个数字出现的次数，不妨设我们现在考虑数字x

　　x出现总次数={x恰好出现一次的方案数}*1+{x恰好出现两次的方案数}*2+......

　　这样无法求解

　　但可以转换成这样：

　　x出现总次数={x至少出现一次的方案数}+{x至少出现两次的方案数}+.......

　　　　　　　　=dp[k-1][n-x]+dp[k-2][n-2x]+dp[k-3][n-3x]+.......

　　这样就可以O(nk)解决了

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=,mod=1e9+;

 int dp[maxn+][maxn+];

 int n,k,m;

 int ans=;

 void inc(int &a,int b)

 {

     a=(a+b)%mod;

 }

 int Pow(long long a,int b)

 {

     long long ans=;

     while(b)

     {

         if(b&) ans=ans*a%mod;

         a=a*a%mod;

         b>>=;

     }

     return ans;

 }

 int main()

 {    scanf("%d%d%d",&n,&k,&m);

     dp[][]=;

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

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

         {

             if(j>=)

             inc(dp[i][j],dp[i-][j-]);

             if(j>=i-)

             inc(dp[i][j],dp[i][j-i]);

         }

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

     {

         int s=;

         for(int j=;j<=k&&i*j<=n;++j)

             inc(s,dp[k-j][n-i*j]);

         inc(ans,1LL*s*Pow(1LL*i,m)%mod);

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

CS Academy #32 G

最新文章

热门文章