[ABC066D] 11

Cloud_Umbrella · 2023-08-14 10:33:57 · 题解

乍一看，是道数学题。细一想，是道排列组合。

分析

题目明确地说了，[1,n] 中每个数至少出现一次，而一共有 n+1 个数，说明只有一个数字重复。如若没有重复，答案显然是 \large{C^{k}_{n+1}}。而现在有重复的数字，利用容斥思想，用总的减去重复的，不就是正确答案了吗？

我们用 start 表示重复数字第一次出现的位置，用 last 表示重复数字第二次出现的位置（也可以说是最后一次），那么重复计算的子序列个数就是 \large{C^{k-1}_{start+n-last-1}}，相减可得答案。

在写排列组合函数的时候，是要取模的，所以相减可能会得到负数，但答案不可能是负数，所以应该先加上模数再模。

因为数据范围的原因，肯定要用快速幂。代码细节还挺多的。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=1e9+7;
int n,f[N],fact[N];//fact数组用于存阶乘

int Fpower(int x,int y){//快速幂
    int k=x,ans=1;
    while(y){
        if(y&1) ans=ans*k%M;
        k=k*k%M;
        y>>=1;
    }
    return ans;
}

int C(int x,int y){
    if(x<=0 || y<=0 || x<y) return 0;//不特判会出错
    return fact[x]*Fpower(fact[x-y]*fact[y]%M,M-2)%M;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n;
    n++;
    int start,last;//分别表示重复数字第一和第二次出现的位置
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(f[x]){//注意，要先判断
            start=f[x];//f[x]存的是x第一次出现的位置
            last=i;
        }
        f[x]=i;//用于存位置
    }
    fact[0]=1;
    cout<<n-1<<"\n";//要先输出，否则会错！
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%M;//存下阶乘
    for(int i=2;i<=n;i++){
        int ans=C(n,i)-C(start+n-last-1,i-1);
        ans=(ans+M)%M;//避免出现负数
        cout<<ans<<"\n";
    }
    return 0;//好习惯伴终生
}