51nod 1829 函数 （斯特林数）

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!×S(N,M) ，其中 S$S$ 表示第二类斯特林数。

AC 代码

#include 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>=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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。