题目:
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); } } }