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