51nod 1829 函数 （斯特林数）

Description

想知道f:A->B这个函数（其中|A|=n, |B|=m）的所有映射关系要使B的每个元素都要被A的一个元素覆盖到。

数字可能很大你只要输出方案数模1,000,000,007即可。

Input

一共一行两个数，n和m。（1<=n,m<=1,000,000)

Output

一共一行包含一个方案数。

Input示例

2 2

Output示例

2

思路

原题相当于： n 个不同的球（定义域）放入 m 个不同的盒子（值域），盒子不可以为空，求总共的方案数。

答案： $M! \times S(N,M)$ ，其中 $S$ 表示第二类斯特林数。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
const int maxn = 1e6+10;
const int mod = 1e9+7;
LL mul[maxn];
LL inv[maxn];

void init()
{
    mul[0]=1;
    for(int i=1; i<maxn; i++)
        mul[i]=(mul[i-1]*i)%mod;

    inv[0]=inv[1]=1;
    for(int i=2; i<maxn; i++)
        inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1; i<maxn; i++)
        inv[i]=(inv[i-1]*inv[i])%mod;
}

LL C(int n,int m)
{
    return mul[n]*inv[m]%mod*inv[n-m]%mod;
}

LL mult(LL a,int n)
{
    a%=mod;
    LL ans = 1;
    while(n)
    {
        if(n&1) ans = (ans*a)%mod;
        a = (a*a)%mod;
        n>>=1;
    }
    return ans;
}

int main()
{
    init();
    int n,m;
    cin>>n>>m;
    LL ans = 0;
    for(int i = 0,e = 1; i <= m; i++,e*=-1)
        ans = (C(m,i) * mult(m-i,n) %mod * e + ans)%mod;
    cout<<(ans+mod)%mod<<endl;
    return 0;
}