题解：P11681 [Algo Beat Contest 001 C] Creating a Queue

Besheep · 2025-02-05 19:59:33 · 题解

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

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

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

• 序列 A 中任意一项的个数大于 1。

不难发现，小于等于 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;
}