//第i列和第i+n的涂色个数是相同的，所以只需要处理前n列
//dp[i][j]表示前i列有j个涂色的方法数
//dp[i][j] += dp[i-1][s]*pow(c[n][s] , m/n)
//c[n][s] 表示从n个数中取s的组合数
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 110 ;
const __int64 mod = 1000000007;
__int64 dp[maxn][maxn*maxn];
__int64 c[maxn][maxn] ;
__int64 po[maxn][maxn*maxn][2] ;
__int64 pow(__int64 a ,__int64 b)
{
__int64 c = 1;
while(b)
{
if((b&1)) c=((c%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod ;
b = b>>1;
}
return c;
}
void init()
{
memset(dp , 0 , sizeof(dp)) ;
for(int i = 0;i <= 100;i++)
{
c[i][0] = 1;
for(int j = 1; j <= i;j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod ;
}
}
int main()
{
__int64 m ;
int n , k;
while(~scanf("%d%I64d%d",&n ,&m ,&k))
{
init();
int res = m%n ;
for(int i =0;i <= n ;i++)
dp[i][0] = 1 ;
for(int i = 1;i <= n;i++)
for(int s = 0;s <= k;s++)
{
if(i <= res)
po[i][s][0] = pow(c[n][s] , m/n+1);
else
po[i][s][1] = pow(c[n][s] ,m/n);
}
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= k;j++)
{
for(int s = 0;s <= min(j ,n); s++)
{
if(i <= res)
dp[i][j] = (dp[i][j] + dp[i-1][j-s]*po[i][s][0])%mod ;
else
dp[i][j] = (dp[i][j] + dp[i-1][j-s]*po[i][s][1])%mod ;
}
}
}
printf("%I64d\n" ,dp[n][k]) ;
}
return 0;
}
Codeforces Round #144 (Div. 1) B dp
原文：http://blog.csdn.net/cq_pf/article/details/45156553
