夏晓光(loveJY)的博客

SDOI2019D2T3

唔母,这道题确实是不错的找规律+思维题,导致考场上没有人发现了规律然后就无人AC了

一般来讲,SD能进国家集训队的几位总有人能AC掉D2T3,不过他就是毒瘤,所以就无人过掉QAQ

我不想被人称为眼高手低,因为那只是我的努力你看不见2333

• 题目大意：有一个01串$tm$，满足$tm(0)=0$，tm(i)=tm(i>>1)^(i&1)。给定01串s和整数k，问有多少个本质不同的01串t满足：t是tm的子串，s是t的前缀，t的长度是$|s|+k$。

这样的题我们首先要寻找TM序列的性质,否则我们没法做,因为TM序列长度是无限长的同时没有循环节,理论上可能任何一个0/1串都会出现在其中

于是证明定理一:任何一个长度大于2的连续的0/1不会出现在TM序列里面

打表可得显然成立,然而正规证法是啥啊?

我们要用到一个trick,就是如果我们没法构造母串直接匹配,那么我们可以考虑按某种规律缩减子串来使得长度变短从而计算出方案

TM序列的规律?包括翻转后接在后面好像都没法实现缩短.我们需要** 元素 **之间的扩张关系

定理二:TM序列的扩展可以看做** 0后放1,1后放0 **进行展开

这个也是打表可知正确,然后用定理二就可以反推定理一正确了

好像走上了正道,我们再看看方案数怎么计数

你发现了我们好像可以通过这个方法不断减少|S|,以及后面的k,从而达到一个很短的境地满足不能再缩了就是一种方案了

这好像有点动态规划啊?f(S,k),S是原串,k是后面还要接k,的总方案数,我们来考虑状态转移

1. 实际的状态数不多,我们要记搜

2. 考虑什么时候S不能再缩了,分...|S|+k<=3吧...

case 1:|S|=1

1. k=0
2. k=1 2种
3. k=2 3种,除去一个连续的000/111

case2:|S|=2

1. k=0
2. k=1,如果前面两个相等只有1种,否则两种

case3:|S|=3

1. k=0 如果三个相同就0种

然后在考虑每种压缩方式

case1 |S|&1==0

我们考虑要么从第一个开始每个都分成两组,要么我们保留第一个和最后一个然后分成两组

case2 |S|&1==1

要么保留第一个位置然后把剩下的分成两组,要么保留最后一个位置把剩下的分成两组

如果分到有一组是11/00就挂掉了不行

然后必要性显然,充分性....我们想,由于整个序列中不会出现连续三个1或0,所以可以认为我们错位一个分组一定能分到合法方案

这一部k的变化也很显然对吧,所以这样搞下去就做完了

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define fi first
#define se second
#define mp make_pair
const int P = 1e9 + 9;
#define ll long long
int t;
string s;
long long k;
#define par pair<string,ll>
map<par, ll> mm;

inline ll wk(par p) {
	//puts("???");
	if(p.fi.size() == 1) {
		if(!p.se)return 1;
		if(p.se == 1)return 2;
		if(p.se == 2)return 3;
		//s的大小为1
	}
	if(p.fi.size() == 2) {
		if(!p.se)return 1;
		if(p.se == 1)return (p.fi[0] == p.fi[1] ? 1 : 2);
	}
	if(p.fi.size() == 3 && !p.se)return (p.fi[0] == p.fi[1] && p.fi[1] == p.fi[2] ? 0 : 1);
	//	puts("???");
	if(mm.find(p) != mm.end())return mm[p];
	ll as = 0;
	//printf("%d %lld\n", p.fi.size(), p.se);
	int i;
	bool fg = 1;
	string nxt;
	nxt.clear();
	for(i = 0; i < p.fi.size(); i += 2) {
		if(i == p.fi.size() - 1)nxt += p.fi[i];
		else if(p.fi[i] == p.fi[i + 1]) {
			fg = 0;
			break;
		} else nxt += p.fi[i];
	}
	if(fg)as += wk(mp(nxt, (p.fi.size() % 2 ? (p.se >> 1) : (p.se + 1 >> 1))));
	fg = 1;
	nxt.clear();
	nxt += (p.fi[0] ^ 1);
	for(i = 1; i < p.fi.size(); i += 2) {
		if(i == p.fi.size() - 1)nxt += p.fi[i];
		else if(p.fi[i] == p.fi[i + 1]) {
			fg = 0;
			break;
		} else nxt += p.fi[i];
	}
	if(fg)as += wk(mp(nxt, (p.fi.size() % 2 ? (p.se + 1 >> 1) : (p.se >> 1))));
	return mm[p] = as;
}


int main() {
	scanf("%d", &t);
	while(t--) {
		std::cin >> s >> k;
		printf("%lld\n", wk(mp(s, k)) % P);
	}
	return 0;
}