CodeForces 232B

同时也是 LETTers 2015 Summer II round 01 - B

#include <cstdio>
#include <iostream>

#define lld I64d

using namespace std;

const int MOD = 1e9 + 7;
const int N = 100 + 5;

typedef long long LL;

LL C[N][N], dp[N][N*N], f[N][2];


LL pow(LL a,LL x)
{
    LL res = 1;
    for(; x; x>>=1, (a*=a)%=MOD)
    {
        if(x & 1)
        {
            (res*=a) %= MOD;
        }
    }
    return res;
}

int main()
{
    LL n, m, k, cnt, rem;

    //freopen("B.in", "r", stdin);
    scanf("%lld%lld%lld", &n, &m, &k);

    cnt = m / n;
    rem = m % n;
    C[0][0] = 1;
    for(int i = 1; i < N; 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;
        }
    }
    for(int i = 0; i <= n; i++)
    {
        f[i][0] = pow(C[n][i], cnt);
        f[i][1] = pow(C[n][i], cnt + 1);
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            dp[i][j] = 0;
            for(int r = 0; r <= n; r++)
            {
                if(r > j)
                {
                    break;
                }
                dp[i][j] += f[r][(i <= rem)] * dp[i - 1][j - r] % MOD;
                dp[i][j] %= MOD;
            }
        }

    }

    printf("%lld\n", dp[n][k]);


    return 0;
}