【2024NOIP模拟赛44】跳棋 做题记录

对于一个 $01$ 串，每次操作可以选择一个 $110$ 变为 $011$ 或者选择一个 $011$ 变为 $110$。

对于一个 $01$ 串 $a$，设 $h(a)$ 表示可以从 $a$ 经过若干次操作到达的不同 $01$ 串个数。

给定一个 $01?$ 串 $s$，对于所有把 $?$ 替换成 $0/1$ 得到的串 $t$，求 $h(t)$ 的和，对 $10^9+7$ 取模。

$1\le n\le 5\times 10^3$。

出题人真菜，$O(n^2)$ 都不会。

由于操作可逆，考虑对于局面 $x$ 设 $f(x)$ 表示不断将棋子往后跳直到不能跳的局面。则两个局面 $x,y$ 能互相到达当且仅当 $f(x)=f(y)$。

答案相当于枚举每一个初始状态，将其的联通块大小加起来。这个其实相当于求有多少个有序状态对 $x,y$ 满足 $x$ 可能成为初始状态且 $f(x)=f(y)$。

观察 $f(x)$ 的过程，发现对于每一段连续的 $1$，若它的长度为偶数，则会不断往右走（火车），否则末尾的那个 $1$ 会留下来。而一个单独 $1$ 被长度为 $len$ 的火车撞到的时候，它的位置会往左移 $len$。

那么不妨把火车拆为若干个 $11$（车厢），对于一段长度为奇数的连续 $1$，将“末尾留下来”看作“开头被火车撞到”。

那么考虑同时填 $x,y$，设 $f_{i,j}$ 表示 $x_{[1,i-1]}$ 和 $y_{[1,j-1]}$ 填好了，且在火车开过后 $x_i$ 对应 $y_j$。

转移考虑往某个序列末尾填数：

• 填 $11$（车厢）则 $k$ 会对应原来的 $k-2$，转移到 $f_{i+2,j}$ 或者 $f_{i,j+2}$；
• 填 $1$ 和填 $0$ 则转移到 $f_{i+1,j+1}$；

但是这样会有若干问题，首先是填了 $1$ 后不能马上填 $11$，这个可以开个 $g_{i,j}$ 表示末尾填的是 $1$ 来解决。还有一个问题是先往 $x$ 填 $11$ 再往 $y$ 填 $11$ 和先往 $y$ 填 $11$ 和再往 $x$ 填 $11$ 是一样的，这个容斥一下就行，让 $f_{i,j}$ 减掉 $f_{i-2,j-2}$。

时间复杂度 $O(n^2)$。

#include <iostream>
#include <cstdio>

using namespace std;

const int S=5005;
#define p 1000000007

int n;
char a[S];
int f[S][S],g[S][S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline bool ch0(int x){return (a[x]=='0'||a[x]=='?');}
inline bool ch1(int x){return (a[x]=='1'||a[x]=='?');}

int main()
{
	freopen("checkers.in","r",stdin);
	freopen("checkers.out","w",stdout);
	scanf("%d%s",&n,a+1);
	f[1][1]=1;
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=n+1;j++)
		{
			if(i-2>=1&&j-2>=1&&ch1(i-2)&&ch1(i-1))
			{
				add(f[i][j],p-f[i-2][j-2]);
			}
			int u=f[i][j],v=g[i][j];
			// i - j
			if(i<=n&&ch1(i)) // 1
			{
				if(j!=n+1) add(g[i+1][j+1],u);
				if(i+1<=n&&ch1(i+1)) add(f[i+2][j],u); // 11
			}
			if(ch0(i)&&j!=n+1) // 0
			{
				add(f[i+1][j+1],u);
				add(f[i+1][j+1],v);
			}
			if(j+1<=n)
			{
				add(f[i][j+2],u);
			}
		}
	}
	printf("%d\n",(f[n+1][n+1]+g[n+1][n+1])%p);
	return 0;
}