专栏文章

CF gym 105384 K. Knocker 题解

DDanielcdo
题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@minau853
此快照首次捕获于
2025/12/01 23:23
3 个月前
此快照最后确认于
2025/12/01 23:23
3 个月前
查看原文
Link

题目概述

给定一个序列 AA，每次操作可以选择一个正整数 xx，将每个元素 AiA_i 变为 Ai mod xA_i \bmod x。问执行任意次操作后，能变成的不同序列个数。

题目转化

一眼结论题，还不简单。
由于每次操作都是对整体进行操作，因此初始就相等的元素一定全程都相等，所以我们不妨先对 AA 去重。由于操作中大的数最容易受到影响，所以可以先对序列 AA 从大到小排序，即 A1>A2>⋯>AnA_1>A_2>\dots>A_n，方便之后的讨论。
假设序列的最终形态为序列 BB。如果我们直接从 AA 下手，考虑它能变成哪些 BB 会非常复杂，难处理算重的情况，也不好计数，因此我们反向考虑，BB 满足什么条件是合法的？可以怎么构造出？
感觉还是无从下手啊，我们可以先把 Ai≤20A_i\le20 的特殊性质打出来，输出所有合法的 BB 观察规律，一下是一些输入的其中一些输出：
输入 1：
CPP
10
1 2 3 4 5 6 7 8 9 10
输出 1：
CPP
1 2 3 4 5 6 0 1 2 3
1 2 3 4 0 1 2 3 4 0
1 2 3 0 1 2 3 0 1 2
输入 2：
CPP
8
1 3 5 7 9 11 13 15
输出 2：
CPP
1 3 5 7 9 1 3 5
1 3 5 7 0 0 2 4
1 3 5 0 2 1 3 5
从这几组例子中我们可以明显感受到，从序列 AA 到序列 BB，有很多组相邻位置的差是没有发生变化的。我们尝试研究每个元素变化减少的值：
A1−y1=B1A2−y2=B2…Ap−yp=Bp             Ap≥y1Ap+1−yp+1=Bp+1  Ap+1<y1…An−yn=BnA_1-y_1=B_1\\A_2-y_2=B_2\\ \dots \\A_p-y_p=B_p \space \space \space \space \space \space \space \space \space \space \space \space \space A_p\ge y_1\\A_{p+1}-y_{p+1}=B_{p+1} \space \space A_{p+1}< y_1 \\ \dots \\ A_n-y_n=B_n
根据刚才发现的规律，我们可以大胆的猜测：y1=y2=⋯=ypy_1=y_2=\dots =y_p ，由于这些 yiy_i 都相等，因此设 yy 为它们共同的值。但猜测毕竟只是猜测，需要严格的理论证明。
首先我们假设只进行了一步操作，设模数为 xx，则根据模运算的定义可知：
y1=x×⌊A1x⌋y1≤Ai<A1yi=x×⌊Aix⌋y_1=x \times \lfloor \frac{A_1}{x} \rfloor\\y_1\le A_i < A_1\\y_i=x \times \lfloor \frac{A_i}{x} \rfloor
联立以上式子可得 y1=yiy_1=y_i，由于每次操作都满足此性质，因此多次操作的最终结果也满足，得证。
也就是说，当我们知道 yy 的值后，就能依次确定:对于任意的 Ai≥yA_i\ge y，Bi=Ai−yB_i=A_i-y，由于这数都是减去相等的 yy，因此大小关系不变。
接着我们发现，虽然最终值已经确定，但中间的多次操作仍然复杂，因此考虑将多次操作简化为一次操作，即：选择一个 yy 满足 A1−y<A12A_1-y<\frac{A_1}{2}（因为一个有效的模运算至少使得原数减半），然后让前 pp 个位置同时减去一个 yy，这样我们就确定了 B1…pB_{1 \dots p} 的值。
然后就是确定第 p+1p+1 个位置到第 nn 个位置的值，我们发现这个问题与我们的初始问题相似，是初始问题的一个子问题，所以考虑使用记搜或者 DP 来解决。这里处理子问题时需要满足一个限制：选择的模数必须大于 B1B_1 的值，不然在处理子问题时，又会影响到我们前面已经确定的 B1B_1 的值。

算法流程

DP 具体实现部分，看懂了上面的解决这道题就很简单了，这里还是简单描述一下实现。
首先，将序列 AA 从小到大排序然后去重。定义 fi,jf_{i,j} 表示前 ii 个位置已确定，且使用模数的最小值为 jj 时的方案数。
接着，考虑对于位置 ii 进行转移。简单枚举 BiB_i 的值 kk，因此 y=Ai−ky=A_i-k，然后我们从当前位置往前找到第一个 Ap<yA_p<y，根据刚才的结论可知位置 p+1p+1 到 ii 都已确定，因此可以直接从位置 pp 转移到当前 ii。枚举前 pp 个位置的选择模数的最小值为 uu 从 k+1k+1 到 500500，转移：
fi,min(u,y)←fi,min(u,y)+fp,uf_{i,min(u,y)}\gets f_{i,min(u,y)}+f_{p,u}
Ai=BiA_i=B_i 的情况单独讨论就行了。此时已经可过此题了，用前缀和优化还能更快。
完结！？哦对，还有代码。

代码实现（变量名可能与上述有差异）

CPP
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL read()
{
	char c=getchar();
	LL f=1,x=0;
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
void print(LL x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
const LL N=505,mod=998244353;
LL n,a[N],f[N][N],ans;
/*
f[i][j]表示前i个位置已经确定，且选择x的最小值为j 
*/
int main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+1+n);
	n=unique(a+1,a+1+n)-(a+1);
	for(int i=1;i<=n;i++)
	{
		f[i][501]=1;
		for(int j=0;j<(a[i]+1)/2;j++)
		{
			int x=a[i]-j,pos=0;
			for(int k=i-1;k>=1;k--)
			{
				if(a[k]<x)
				{
					pos=k;
					break; 
				}
			}
			if(!pos) f[i][x]++;
			else
			{
				for(int k=j+1;k<=501;k++) f[i][min(k,x)]=(f[i][min(k,x)]+f[pos][k])%mod;
			}
		}
	}
	for(int i=1;i<=501;i++) ans=(ans+f[n][i])%mod;
	print(ans);
	return 0;
}

评论

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

正在加载评论...