自动搬运

查看原文

来自洛谷，原作者为

	Besheep 2025 CSP RP++

搬运于2025-08-24 23:09:28，当前版本为作者最后更新于2025-02-05 19:59:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们计序列 $A$ 中 $0$ 的个数为 $cnt$。

保证子数组不能存在唯一众数，不就是序列中的元素互不相等？

惊人的注意力。所以注意到有以下两种情况是无法构造成合法序列的：

• 序列 $A$ 中任意一项的个数大于 $1$。
• $m<cnt$，此时序列 $A$ 中至少有两项相同的数，不满足上一条。

不难发现，小于等于 $m$ 且未在序列 $A$ 中出现数字的个数为 $m-n+cnt$，我们要在剩余的 $cnt$ 个位置里去摆放这些数，于是问题便转化为求：

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+10,mod=1145141923;
ll n,m,a[N],cnt,ans=1;
map<ll,bool>mp;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
		if(a[i]==0){
			cnt++;
			continue;
		}
		if(mp[a[i]]){
			cout<<0;
			return 0;
		}
		mp[a[i]]=1;
	}
    m-=n-cnt;
    for(int i=0;i<cnt;i++) ans=ans*(m-i)%mod;
    cout<<ans;
	return 0;
}