51Nod-1829-函数

ACM模版

描述

题解

典型的第二类斯特林数，很容易想到递推式 S(i,j)=j∗S(i−1,j)+S(i−1,j−1) ，可是这种写法肯定超时，因为数据太大，复杂度 O(nm) ，所以需要利用容斥来寻求更快的方案。

像这种公式，我只能记得一个大概，只好借助百度找到了

代码

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

int n, m;
ll fac[MAXN];       // 阶乘
ll inv[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()
{
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv[MAXN - 1] = QPow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
}

ll C(ll a, ll b)
{
    if (b > a)
    {
        return 0;
    }
    if (b == 0)
    {
        return 1;
    }
    return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}

int main()
{
    init();

    cin >> n >> m;

    ll ans = 0;
    for (int i = 0, e = 1; i <= m; i++, e *= -1)
    {
        ans += C(m, i) * QPow(m - i, n) % MOD * e;
        ans %= MOD;
    }
    cout << (ans + MOD) % MOD << endl;

    return 0;
}