自动搬运

查看原文

来自洛谷，原作者为

	ddh123 虚拟正是人类的本质，人们什么时候能看到最澄澈的空与海呢

搬运于2025-08-24 23:05:22，当前版本为作者最后更新于2025-01-11 01:18:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是本蒟蒻的第一篇正式题解。

本题重点在于找到无解序列的充要条件，首先记 $a_i$ 为游戏结束时第 $i$ 个数取 $2$ 的对数，$t_i$ 为第 $i$ 个数出现时间离散化后的值，显然 $a$ 相邻两项不同，$t$ 是一个排列，如果一个位置比它相邻位置大且出现时间小，直接按照顺序合成即可，如果一个元素比它相邻位置小且出现时间小呢？我们可以先合成较大数的一半再合成较小数，最后合成较大数，具体参考样例解释中 $[2,8,4,2]$ 的第四种情况。

一些性质

1. $a$ 是单峰的，$t$ 是单谷的，归纳易证。

2. $a_i+t_i-1 \le n$，这是因为已经有 $t_i-1$ 个位置被占，且第$i$个数至少需要 $a_i$ 个位置才能合成。

3. 若 $t_i<t_{i+1}$，那么 $a_i+1\ne a_{i+1}$，这是因为如果 $a_i+1=a_{i+1}$，那么 $a_{i+1}$ 的合成会影响到 $a_i$ 的合成。同理，若 $t_i<t_{i-1}$，那么 $a_i+1\ne a_{i-1}$。

4. 若 $t_{i-1}<t_i<t_{i+1}$，那么不可能会有 $a_{i-1}<a_i<a_{i+1}$，这是因为如果 $a_{i-1}<a_i<a_{i+1}$，那么首先要合成 $a_{i+1}-1$，然后合成 $a_i-1$，最后合成 $a_{i-1}$，这会使 $a_i-1$ 无法进一步合成出 $a_i$。同理，若 $t_{i-1}>t_i>t_{i+1}$，那么不可能会有 $a_{i-1}>a_i>a_{i+1}$。

我们容易发现，这些性质已经充要，我们来考虑如何 dp。

DP

考虑到性质 1 和性质 4，可以发现出现时间最小的位置只能是 $a$ 中最大的位置或这个位置的相邻两个位置，也就是下图中红框框住的点。也就是说出现时间最小的位置的两边元素大小分别是单增和单减，因此我们可以按照出现时间从大到小进行转移。

设 $F_{i,L,R}$ 表示已经有 $i$ 个数确定，其中左块最右边的数是 $L$，右块最左边的数是 $R$，首先考虑 $L$ 与 $R$ 的范围。假设格子总数是 $m$，第 $j$ 个转移的数大小为 $x$，根据性质 2 有：$x+m-j\le m$，也就是 $x\le j$，因此有 $L\le i$，$R\le i$。转移方程为：$F_{i,L,R}=(\sum_{[tl\lt L]}F_{i-1,tl,R} )+(\sum_{[tr\lt R]}F_{i-1,L,tr} )$，这个东西可以用前缀和优化，贡献答案时差分即可，时间复杂度 $O(300^3+T)$。

AC Code

#include<bits/stdc++.h>
using namespace std;
int T,mod,n,x,dp[305][305][305],f[305][305][305],g[305][305][305],sum[305][305];
void add(int &x,int y){
	(x+=y)%=mod;
}
void fun(int n,int lx,int rx,int res){//计算贡献
	add(sum[n][lx],res),add(sum[n][rx+1],mod-res);
}
int main(){
	scanf("%d%d",&T,&mod);
	dp[0][0][0]=g[0][0][0]=f[0][0][0]=1,fun(1,1,1,1);
	for(int i=1;i<300;i++)
		for(int j=0;j<=i;j++)
			for(int k=0;k<=i;k++)if(j+k){
				if(j)add(dp[i][j][k],f[i-1][j-1][k]);
				if(k)add(dp[i][j][k],g[i-1][j][k-1]);
				f[i][j][k]=g[i][j][k]=dp[i][j][k],fun(i+1,max(j,k)+1,i+1,dp[i][j][k]);
				if(j+1<=k-2)fun(i+1,k,k,dp[i][j][k]*2LL*((k-2)-(j+1)+1)%mod);   //考虑到对称性直接*2即可
				if(j)add(f[i][j][k],f[i][j-1][k]);
				if(k)add(g[i][j][k],g[i][j][k-1]);
			}
	for(int i=1;i<=300;i++)for(int j=1;j<=300;j++)add(sum[i][j],sum[i][j-1]);
	for(int i=1;i<=300;i++)for(int j=1;j<=300;j++)add(sum[i][j],sum[i][j-1]);
	while(T--)scanf("%d%d",&n,&x),printf("%d\n",sum[n][x-1]);
	return 0;
}

如有表达不清可以在评论区里交流讨论。