P11681 题解

· · 题解

题目传送门

思路

先由小推，若序列 A 长度为 2，那么这 2 个数必定不同。再想若 A 的长度为 3，那么这 3 个数必定不相同。若 A 长度为 4，可以将其划分为 4 个不同的数或者 2 组各 2 个数，但显然这不可以，因为 A 的子序列的众数会只出现 1 个。所以得出了该序列的一个性质：序列中每个数互不相同。

于是先判断无解的情况：序列中有重复的数。

得到了这个性质，接着统计出 A_i\ne0 的个数，记为 X。然后推导答案，第 1 次可选 M-X 个，第 2 次可选 M-X-1 个，第 3 次可选 M-X-2 个，第 k 次可选 M-X-k+1 个。最终将每一次可选个数想乘，所以 \prod\limits_{i=X}^{N-1}(M-i) 为最终答案。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6+10,MOD=1145141923;
int a[N];
unordered_map<int,bool>mp;
signed main(){
    int n=read(),m=read();
    if(n>m)
        return printf("0\n"),0;
    for(int i=1;i<=n;++i)
        a[i]=read();
    int cnt=0;
    for(int i=1;i<=n;++i){
        if(mp[a[i]]&&a[i])
            return printf("0\n"),0;
        mp[a[i]]=true;
        if(a[i])
            ++cnt;
    }
    int ans=1;
    for(int i=cnt;i<n;++i)
        ans=ans*(m-i)%MOD;
    printf("%lld\n",ans);
    return 0;
}