ACM模版

描述

题解

先预处理出来组合数，然后递推就能解决。

虽然这个题 A <script type="math/tex" id="MathJax-Element-20">A</script> 的人最多，但是我感觉他并不是签到题，因为我推了好久才推出来，毕竟我的数论基础那么差，实在是恼人……

代码

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 2222;
const int MOD = 1e9 + 7;

int n, m;
int C[MAXN][MAXN];
ll p[MAXN];

ll QPow(ll x, ll n)
{
    ll ret = 1;
    ll tmp = x % MOD;

    while (n)
    {
        if (n & 1)
        {
            ret = (ret * tmp) % MOD;
        }
        tmp = tmp * tmp % MOD;
        n >>= 1;
    }

    return ret;
}

void init()
{
    C[0][0] = 1;
    for (int i = 1; i < MAXN; 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(int argc, const char * argv[])
{
    init();

    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            p[i] = QPow(i, n);
        }
        for (int i = 2; i <= m; i++)
        {
            for (int j = 1; j < i; j++)
            {
                p[i] = (p[i] - p[j] * C[i][j] % MOD + MOD) % MOD;
            }
        }

        ll ans = 0;
        for (int i = 1; i < m; i++)
        {
            for (int j = 1, k = m - i; j <= k; j++)
            {
                ans = (ans + p[i] * p[j] % MOD * C[m][i] % MOD * C[k][j] % MOD) % MOD;
            }
        }

        printf("%lld\n", ans);
    }

    return 0;
}