多重集合的全排列

多重集合的定义：多重集合不要求元素不能重复。

多重集合表示：

(M=left {k_{1}cdot a_{1},k_{2}cdot a_{2},cdots ,k_{n}cdot a_{n} ight })(left ( 其中每个a_{i}代表是不同的元素，每个元素a_{i}有k_{i}个，k_{i}可以是有限数，也可以是∞。 ight ))

多重集的排列:

• (多重集合M=left {k_{1}cdot a_{1},k_{2}cdot a_{2},cdots ,k_{n}cdot a_{n} ight }的r排列数为k^{r})
• (多重集合M=left {k_{1}cdot a_{1},k_{2}cdot a_{2},cdots ,k_{n}cdot a_{n} ight }的全排列数为：frac{left ( k_{1}+k_{2}+cdots +k_{n} ight )!}{k_{1}!k_{2}!cdots k_{n}!})

 例题：here

 题解：

(n)个数，选择(n-1)种，那么有(C_{n}^{n-1}也就是n种)方案。对于每种方案，要从(n-1)个数里面，选择一个重复的数字，有(n-1)种方案。此时对于每种方案，长度都是为(n)的序列，考虑多重集合的全排列方案数。根据公式可知全排列数为(frac{n!}{2!})，所以题目答案就是：(nast left ( n-1 ight )ast frac{n!}{2!}把除以2的阶乘转换为乘以2的阶乘的逆元)

AC_Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const ll mod=1e9+7;

ll F[maxn];
ll n;

void init(){
    F[0]=F[1]=1;
    for(int i=2;i<=100000;i++) F[i]=1ll*F[i-1]*i%mod;
}

ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if( b&1 ) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}

int main()
{
    init();
    ll t2=qpow(2,mod-2);
    while( ~scanf("%lld",&n)){
        ll ans=n*(n-1)%mod*F[n]%mod*t2%mod;
        printf("%lld
",ans);
    }
    return 0;
}