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

· · 题解

于2025/2/5进行修正，望审核大大通过~~~

一道带点思维量的数学题

题意梗概：给定一个长为 n 的序列，序列中的数均为不大于 m 的正整数，已知的数均给出，未知的数用 0 表示，现要求将序列填充完整，问多少个方案满足序列中不存在长度不为 1 且存在唯一众数的连续子段，答案对一个很臭的数取模。

乍一看这个限制很吓人，实则非常简单，可以将其翻译为序列中不存在相同的数，证明如下：

1、对于任意长为二的连续子段，容易知道“不存在唯一众数”与“不存在相同数字”等效。

2、对于任意长为三的连续子段，此处不妨设三个数从左到右分别为 i,j,k 。已知 i 与 j 不同，倘若 i 与 k 相同，便存在唯一众数，不合法，因而 i 与 k 应不同。即“不存在唯一众数”与“不存在相同数字”仍然等效。
举例：对于 [1,2,0] 的填充， [1,2,1]显然不合法，而 [1,2,3]是合法的。

3、使用数学归纳法容易证明，若一个方案满足限制，则这个方案所得序列中不存在相同的数。

然后这题基本就做完了，只需要再注意一些细节即可：

1、数据中 m 可能会小于 n ，出现这种情况时显然不可能有解，方案数为 0 ；

2、使用 map 或 set 记录数是否已经出现，当序列中已经存在重复的数时，方案数为 0 ；

3、记序列中 0 的个数为 a ，值域内没有出现过的数有 b 个，容易知道方案数即排列数为 \frac{b!}{(b-a)!} ,然而考虑到数据范围大到 1\times10^9 ，因此直接算阶乘并不现实。

考虑到 b 可能很大而 a 往往较小，因此采用下述方法：

考虑先从 b 个数中取走 1 个数作为第一个数，此时取走的数有 b 种可能；随后再从 b-1 个数中取走 1 个数作为第二个数，此时取走的数有 b-1 种可能。反复取数，直到取完第 a 个数并结束。

此时，根据乘法原理，方案数应当为取走的每个数的可能种类数的积，遂有下述做法。

代码很短，码风很丑QwQ

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1145141923;
int n,m,a,b,ans=1;
unordered_map<int,int> f;
signed main()
{
    cin>>n>>m;
    if(m<n) return cout<<0,0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(!x) a++;
        else if(f[x]) return cout<<0,0;
        else f[x]=1;
    }
    b=m-f.size();
    while(a)
    {
        ans=ans*b%mod;
        a--;b--;
    }
    cout<<ans;
}