ACM模版

描述

题解

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

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

S(n,m)=1m!∗∑i=0m(−1)i∗C(m,i)∗(m−i)n
然而第二类斯特林数是不关心元素的区别的，只关心不同盒子放不同个数的方案数，所以最后的结果是
ans=m!∗S(n,m)
化简得
ans=∑i=0m(−1)i∗C(m,i)∗(m−i)n
这样只需要预处理一下组合数，恰巧的是在预处理组合数时用到的快速幂在这个公式里可以再次使用。

代码

#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;
}