每次跳到的位置模 \(k\) 同余，将黑块延长 \(s\) 后模 \(k\)，如果 \([0,k)\) 中出现了一个点没被黑块覆盖说明有解。细节比较多。

const int N = 5e5+5;
int T,s,k,n;

PII f[N*2];

void solve() {
	int cnt = 0; LL now = 0; bool flg = 0;
	read(s,k,n); assert(k>s);
	For(i,1,n) {
		int len; read(len);
		if( i & 1 ) {
			LL l = now+1, r = now+len+s-1;
			if( r-l+1 >= k-1 ) flg = 1;
			l %= k, r %= k;
			if( l <= r ) f[++cnt] = MP(l,r);
			else f[++cnt] = MP(0,r), f[++cnt] = MP(l,k-1);
		}
		now += len;
	}
	if( flg ) return puts("NIE"), void();
	sort(f+1,f+cnt+1);
	For(i,2,cnt) assert(f[i].fi!=f[i-1].fi||f[i].se>=f[i-1].se);
	For(i,1,cnt) {
		ckmax(f[i].se,f[i-1].se);
		if( f[i-1].se+1 < f[i].fi ) return puts("TAK"), void();
	}
	puts(f[cnt].se+1<k ? "TAK" : "NIE");
}

signed main() {
	f[0].se = -1;
	read(T);
	while( T-- ) solve();
	return iocl();
}

由于字典序从前往后比，即前面的影响更大，考虑从后往前 DP。设 \(f[i,j,l,r]\) 为第 \(l\) 个字符串到第 \(f\) 个，后缀 \(i\) 填完，当前这位至少是字符 \(j\) 的方案数

const int N = 55, L = 25, mod = 990804011;
int n;
char s[N][L];

int m;
LL f[L][30][N][N];

signed main() {
	scanf("%d",&n);
	For(i,1,n) {
		scanf("%s",s[i]+1);
		ckmax(m,(int)strlen(s[i]+1));
	}
	For(i,1,n) {
		For(j,1,m) if( !s[i][j] ) s[i][j] = 'a'-1;
		For(j,0,26) f[m+1][j][i][i] = 1;
	}
	rFor(i,m,1) rFor(j,26,0) rFor(l,n,1) For(r,l,n) {
		LL &dp = f[i][j][l][r];
		dp += f[i][j+1][l][r];
		for(int mid = l; (s[mid][i]=='a'+j-1||s[mid][i]=='?') && mid <= r; ++mid) {
			if( s[mid][i] == '?' && !j ) break;
			dp += f[i+1][0][l][mid] * (mid==r?1:f[i][j+1][mid+1][r]) %mod;
		}
		dp %= mod;
	}
	write(f[1][0][1][n]);
	return iocl();
}

const int mod = 990804011;
int T,k;
LL l[9],r[9];

int all;
LL n[9],f[51][1<<10];

template<typename T>void ckadd(T &x,T y)
	{ x += y; if(x>=mod) x-=mod; else if(x<0) x+=mod; }

LL dfs(int u,int lim) {
	if( !u ) return 1;
	if( ~f[u][lim] ) return f[u][lim];
	int lim1 = 0;
	For(i,0,k) if( (lim & (1<<i)) && !(n[i] & (1ll<<u-1)) ) lim1 |= 1<<i;
	LL res = dfs(u-1,lim1);
	For(i,0,k) if( !(lim & (1<<i)) || (n[i] & (1ll<<u-1)) )
		ckadd(res,dfs(u-1,lim&(1<<i) ? lim1|(1<<i) : lim1));
	return f[u][lim] = res;
}
void solve() {
	LL ans = 0;
	read(k); all = (1<<k--)-1;
	For(i,0,k) read(l[i],r[i]), --l[i], --r[i];
	for(int s = all; ~s; --s) {
		int cnt = 0; memset(f,0xff,sizeof f);
		For(i,0,k)
			if( s & (1<<i) ) n[i] = r[i];
			else ++cnt, n[i] = l[i]-1;
		if( *min_element(n,n+k+1) >= 0 ) ckadd(ans,(cnt&1?-1:1) * dfs(50,all));
	}
	write(ans);
}

signed main() {
	read(T);
	while( T-- ) solve();
	return iocl();
}

考虑贪心，那么中间部分一定全填 \(0\)，否则最后一位填 \(1\) 即可，能否全填 \(0\) 可以填出来后暴力 kmp，看与原串是否一样。

证明：题解给了个挂掉的链接。。。

const int N = 2e5+1;
int T;
char s[N];

int n,n1,f[N],g[N],pos[N];

void kmp(int *nxt,int l,int r) {
	for(int i = l+1, j = nxt[l]; i <= r; ++i) {
		while( j && s[j+1] != s[i] ) j = nxt[j];
		if( s[j+1] == s[i] ) ++j;
		nxt[i] = j;
	}
}
bool check(int u) {
	for(; u; u = f[u]) if( f[u] != g[u] ) return 0;
	return 1;
}
void solve() {
	scanf("%s",s+1); n = strlen(s+1);
	kmp(f,1,n);
	For(i,1,n) s[i] = '0'; s[n+1] = 0;
	for(int i = n; i; i = f[i]) pos[++n1] = i; reverse(pos+1,pos+n1+1);
	s[pos[1]] = '0'+(pos[1]!=1), kmp(g,1,pos[1]);
	For(i,2,n1) {
		if( pos[i-1]*2 >= pos[i] )
			For(j,pos[i-1]+1,pos[i]) s[j] = s[pos[i-1]-(pos[i]-j)];
		else {
			For(j,pos[i]-pos[i-1]+1,pos[i]) s[j] = s[pos[i-1]-(pos[i]-j)];
			kmp(g,pos[i-1],pos[i]);
			if( !check(pos[i]) ) s[pos[i]-pos[i-1]] = '1';
		}
		kmp(g,pos[i-1],pos[i]);
	}
	printf("%s\n",s+1);
}

signed main() {
	scanf("%d",&T);
	while( T-- ) {
		n1 = 0;
		solve();
	}
	return iocl();
}