题目:签到题
来源:西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛
解题思路
在 1 ~ n 之间随机生成长度为 n 的整数序列,请问正好含有 n-1 个不同的整数的方案数,答案 mod 1e9+7。
排列组合:
首先从 n 个数中选出 n-1 个数,C(n, n-1) = n。
再从 n-1 个数中选出 1 个数,这个数是重复值,C(n-1, 1) = n-1。
从 n 个位置中选出两个位置放置 2 个重复值,C(n, 2) = n(n-1)/2。
对剩下的 n-2 个数进行排列,A(n-2, n-2) = (n-2)!。
将上述的值相乘,取模,即为所求。
C++代码
#include<iostream> using namespace std; const int mod = 1e9+7; const int N = 1e5+1; long long f[N]; int main(){ f[0] = 1; f[1] = 1; for(int i=2; i<N; ++i){ f[i] = f[i-1]*i % mod; } int n; while(cin >> n){ if(n == 1){ cout << 0 << endl; continue; } long long tmp = 1LL * n * (n-1) / 2; long long ans = tmp % mod; ans *= f[n]; ans %= mod; cout << ans << endl; } return 0; }