西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛——B

题目：
https://ac.nowcoder.com/acm/contest/6037/B

这题很有高考题的味道，慢慢来分析其实是很简单的。有1~n，n个数，要求正好包含n-1个不同的数，那我们可以让n个数轮流当那相同的数。既然会有两个相同的数，那我们就让这个数轮流替换剩下的n-1个数，例如1 2 3，我们选2做相同的数，可以让它变成2 2 3和1 2 2。根据乘法原理，这已经有n（n-1）种可能了。然而我们是求满足要求的序列方案数，那么我们对得出来的序列进行全排列，可重集的全排列是 (pi为第i个数有多少个一样的数），所以最终的答案就是n(n-1)*(n!/2)。因为是mod意义运算，除2要算逆元。记得要特判一些特殊情况。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#define int long long
using namespace std;
int t,n,f[100005];
const int mod=1e9+7;
int kuai(int a,int b,int c)
{
    int anss=1;
    while(b)
    {
        if(b&1)
        {
            anss=anss*a%c;
        }
        a=a*a%c;
        b>>=1;
    }
    return anss;
}
signed main()
{
    f[0]=1;
    for(int i=1;i<=100001;i++)
    {
        f[i]=(f[i-1]*i)%mod;
    }
    while(scanf("%lld",&n)!=EOF)
    {
        //scanf("%lld",&n);
        if(n==1)
        {
            printf("0\n");
        }
        else if(n==2)
        {
            printf("2\n");
        }
        else
        {
            int xia=kuai(2,mod-2,mod),shang=f[n];
            printf("%lld\n",(((n*(n-1))%mod*(shang%mod))%mod*(xia%mod))%mod);
        }
    }
}