题目回顾

我们需要模拟一个二进制女巫的天气预测方法。给定一个长度为$N$的二进制字符串（$0$表示雨天，$1$表示晴天），预测接下来的$L$天的天气。预测规则如下：

1. 对于第$N+1$天的预测，从最后$13$位开始（$t=13$），逐步减少$t$的值（$12,11,...,1$），检查当前序列的最后$t$位是否在之前出现过。
2. 如果找到匹配的后缀，则预测值为该匹配位置后一位的值（即$a_{k + t}$）。
3. 如果有多个匹配，选择最靠右的（即最大的$k$）。
4. 如果没有找到匹配，则预测为雨天（$0$）。
5. 对于后续的预测（第$N+2$天到第$N+L$天），将之前的预测结果添加到序列末尾，并重复上述过程。

解题思路

为了高效实现上述规则，可以采用以下方法：

1. 预处理：使用一个二维数组$d[t][mask]$，其中$t$表示后缀长度（$1$到$13$），$mask$是一个$t$位的二进制数的十进制表示。$d[t][mask]$存储的是该$mask$最后一次出现的起始位置。
2. 动态更新：在遍历序列时，动态更新$d[t][mask]$，记录每个可能的$t$位后缀的最后出现位置。
3. 预测：
   • 对于第$i$天（$i$从$N+1$到$N+L$），检查最后$1$到$13$位的所有可能后缀，找到最大的$t$使得后缀在之前出现过。
   • 根据匹配的后缀位置，确定预测值（即匹配位置后一位的值）。
   • 如果没有匹配，预测为$0$。
   • 将预测值添加到序列末尾，并继续更新$d[t][mask]$。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1111111;

int d[14][1<<14]; // d[t][mask] stores the last occurrence of the t-length suffix represented by mask

char str[MAXN];

int main()
{
    int n, l;
    while(~scanf("%d%d", &n, &l))
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1111111;

int d[14][1<<14];

char str[MAXN];

int main()
{
	int n,l;
	while(~scanf("%d%d",&n,&l))
	{
		scanf("%s",str+1);
		memset(d,-1,sizeof(d));
		for(int i = 1;i<=n+l;i++)
		{
			if(i >= n)
			{
				int pos = -1;
				int tmp = 0;
				for(int j = 1;j<=13;j++)
				{
					if(i - j + 1 <= 0) break;
					tmp = (tmp<<1) + str[i - j + 1] - '0';
					if(d[j][tmp] != -1)
					{
						pos = d[j][tmp];
					}
				}
				if(pos != -1)
				{
					str[i+1] = str[pos+1];
				}
				else str[i+1] = '0';
				//printf("i = %d,pos = %d\n",i,pos);
			}
			int tmp = 0;
			for(int j = 1;j<=13;j++)
			{
				if(i - j + 1 <= 0) break;
				tmp = (tmp << 1) + str[i - j + 1] - '0';
				d[j][tmp] = i;
			}
		}
		for(int i = 1;i<=l;i++)
			printf("%c",str[n+i]);
		puts("");
	}
	return 0;
}