题目:签到题
来源:西南科技大学第十六届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;
}