专栏文章

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

bbelif__kibo
P11681题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqcfirf
此快照首次捕获于
2025/12/04 02:31
3 个月前
此快照最后确认于
2025/12/04 02:31
3 个月前
查看原文

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

一道带点思维量的数学题

题意梗概：给定一个长为 nn 的序列，序列中的数均为不大于 mm 的正整数，已知的数均给出，未知的数用 00 表示，现要求将序列填充完整，问多少个方案满足序列中不存在长度不为 11 且存在唯一众数的连续子段，答案对一个很臭的数取模。
乍一看这个限制很吓人，实则非常简单，可以将其翻译为序列中不存在相同的数，证明如下：
1、对于任意长为二的连续子段，容易知道“不存在唯一众数”与“不存在相同数字”等效。
2、对于任意长为三的连续子段，此处不妨设三个数从左到右分别为 i,j,ki,j,k 。已知 ii 与 jj 不同，倘若 ii 与 kk 相同，便存在唯一众数，不合法，因而 ii 与 kk 应不同。即“不存在唯一众数”与“不存在相同数字”仍然等效。
举例：对于 [1,2,0][1,2,0] 的填充， [1,2,1][1,2,1]显然不合法，而 [1,2,3][1,2,3]是合法的。
3、使用数学归纳法容易证明，若一个方案满足限制，则这个方案所得序列中不存在相同的数。
然后这题基本就做完了，只需要再注意一些细节即可：
1、数据中 mm 可能会小于 nn ，出现这种情况时显然不可能有解，方案数为 00 ；
2、使用 map 或 set 记录数是否已经出现，当序列中已经存在重复的数时，方案数为 00 ；
3、记序列中 00 的个数为 aa ，值域内没有出现过的数有 bb 个，容易知道方案数即排列数为 b!(b−a)!\frac{b!}{(b-a)!} ,然而考虑到数据范围大到 1×1091\times10^9 ，因此直接算阶乘并不现实。
考虑到 bb 可能很大而 aa 往往较小，因此采用下述方法：
考虑先从 bb 个数中取走 11 个数作为第一个数，此时取走的数有 bb 种可能；随后再从 b−1b-1 个数中取走 11 个数作为第二个数，此时取走的数有 b−1b-1 种可能。反复取数，直到取完第 aa 个数并结束。
此时，根据乘法原理，方案数应当为取走的每个数的可能种类数的积，遂有下述做法。
代码很短，码风很丑QwQ
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...