• 欢迎光临~

[CF506E] Mr. Kitayuta's Gift 题解

开发技术 开发技术 2022-07-31 次浏览

下面先处理 n+m 为偶

计数,考虑 DP

一般的字符串dp的套路:一位一位的放字符来进行决策

即枚举下一位放什么,这样dp有一个相当棒的好处就是我们永远不会重复数同一个串

考虑设 (f(I,l,r)) 表示在能够匹配原串的时候不会放着比配的前提下,处理了最终形成的串的前 I 个和后 I 个,原串剩下 [l,r] 没有处理的方案数

前提的意思是说,比如有一个 aab ,不能说加上一个 baabb ,因为这样会与 aabb 加上 b 算重

而这样的 DP 状态可以保证所有可以形成的串都可以被识别且不会算重,感性理解就是每次贴着边边走

这样,通过恰当的状态设计避免了算重的风险

转移:

(S[l]==s[r] and r-l <= 1 ,25 * f[i][l][r] to f[i+1][l][r])

(S[l]==s[r] and r-1 > 1 , f[i][l][r] to f[i+1][l+1][r-1])

? $ 25 * f[i][l][r] to f[i+1][l][r]$

(S[l]!=s[r] f[i][l][r] * 24 to f[i+1][l][r])

? $ f[i][l][r] to f[i+1][l+1][r]/f[i+1][l][r-1]$

将 (l,r) 视作一个点, (to) 视作连系数(1,24,25)条边,发现形成一个 DAG,问题变成求有多少种方式可以走 (ceil((n+m)/2)) 步到达最终状态 $(l>r) $

这里连边实际上是方案数的意思,最终状态连 (26) 个自环

这里所谓的 DAG 实际上就是把本来不是非常清晰的 DP 转移过程刻画出来,使得我们可以更好地观察来优化

发现转移方式只和 (s[l],s[r]) 有关,可以对这个 (m=strlen(s+1)) ,m^4 大小的邻接矩阵强行快速幂,复杂度 $ m^6log$

观察信息冗余/寻找性质合并状态,发现我们并不关心具体是由那些状态到达,我们只关系路径上点的种类(24点,25点,26 点)的数量,顺序之类其都无关紧要

发现想要走出一个 24 点需要匹配掉一个原字符,走出一个 25 点需要匹配掉两个

所以如若途径 x 个 24 点,那么就有 (ceil((m-x)/2)) 个 25 点

所以我们可以把经过 24 点的个数相同的状态数算出来一起处理,可以设 (h[i,l,r]) 表示从 [1,m] 走到 [l,r] 经过 I 个 24 点的方案数,(m^3)

此时,我们可以考虑把每一种链单独提出来做一遍矩阵快速幂,一共 (O(m)) 次,每次 m^3logn

矩阵乘法兹瓷计算多个源点和汇点的路径方案数的,且此时顺序已经不重要了,我们考虑优化建图,把原本需要算 m 次的合起来算

[1,m-1] 为 24 点,[m,m+ceil(m/2)) 为 25 点, m+ceil(m/2) 为终点

对于每一个 24 点,连边 m+ceil(x/2) ,边权 (= sum h(x,j,j)+sum[s[j]==s[j+1]]h(x,j,j+1)) ,连边 x,x+1 ,边权 1

对于每一个 25 点,连边 x, x+1 ,边权 1 ,让最后一个 25 点链接终点

最后处理奇数的问题,正难则反,发现奇数在上述算法中唯一不合法的贡献就是:

整条长为n+m的路径,恰好第 (n+m) 步是从[i,i+1]走到终点,所以只需要将终点的自环数量置为 0,且 24 点连边时,边权仅计算 (sum[s[j]==s[j+1]]h(x,j,j+1)) 即可

O(m^3log(n+m))

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e4 + 7;
const int N = 305;
const int M = 205;

char buf[1 << 23], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
int read() {
	int s = 0, w = 1; char ch = getchar();
	while(!isdigit(ch))	{
		if(ch == '-') w = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		s = s * 10 + (ch ^ 48);
		ch = getchar();
	}
	return s * w; 
}
void inc(int &a, int b) { a = a >= mod - b ? a - mod + b : a + b; }
void dec(int &a, int b) { a = a >= b ? a - b : a + mod - b; }

int g[N][N], f[N], h[M][M][M];
bool vis[M][M][M];
int m, n, k;
char s[M];

int ceil(int x) { return (x >> 1) + (x & 1); }
int H(int i, int l, int r){
	if(i < 0) return 0;
	if(vis[i][l][r]) return h[i][l][r];
	vis[i][l][r] = 1;
	if(l == 1 && r == m) return h[i][l][r] = i == 0;
	if(l != 1 && s[l - 1] != s[r]) inc(h[i][l][r], H(i - 1, l - 1, r));
	if(r != m && s[l] != s[r + 1]) inc(h[i][l][r], H(i - 1, l, r + 1));
	if(l != 1 && r != m && s[l - 1] == s[r + 1]) inc(h[i][l][r], H(i, l - 1, r + 1));
	return h[i][l][r]; 
} 

void mul(int f[N], int g[N][N]) {
	int a[N] = {0};
	for(int j = 1; j <= k; ++ j)
		for(int i = 1; i <= k; ++ i)
			inc(a[i], f[j] * g[j][i] % mod);
	for(int i = 1; i <= k; ++ i) f[i] = a[i]; 
}
void mul(int g[N][N]) {
	int a[N][N] = {0};
	for(int i = 1; i <= k; ++ i)
		for(int l = i; l <= k; ++ l)
			for(int j = l; j <= k; ++ j)
				inc(a[i][j], g[i][l] * g[l][j] % mod);
	for(int i = 1; i <= k; ++ i)
		for(int j = 1; j <= k; ++ j)
			g[i][j] = a[i][j];
}
void ksm(int b) {
	while(b) {
		if(b & 1) mul(f, g);
		mul(g), b >>= 1;
	}
}

signed main() {
	scanf("%s %d", s + 1, &n);
	m = strlen(s + 1), k = m + ceil(m);

	for(int i = 0; i < m; ++ i) {
		int c = 0;
		for(int j = 1; j <= m; ++ j) {
			inc(c, H(i, j, j));
			if(j != m && s[j] == s[j + 1]) 
				inc(c, H(i, j, j + 1));
//			cout << c << endl;
		} 
//		puts("");
		if(i == 0) {
			f[m] = c, g[k][k] = 26;
			for(int j = m; j < k; ++ j)
				g[j][j] = 25, g[j][j + 1] = 1;
		} else {
			g[i][i] = 24, g[i][k - ceil(m - i)] = c;
			if(i == 1) f[1] = 1;
			else g[i - 1][i] = 1;
		}
	}
		
	ksm(ceil(n + m));
	if((n + m) % 2 == 0) 
		return printf("%dn", f[k]), 0;
	
	int ans = f[k];
	memset(f, 0, sizeof(f));
	memset(g, 0, sizeof(g));
	
	for(int i = 0; i < m; ++ i) {
		int c = 0;
		for(int j = 1; j <= m; ++ j)
			if(j != m && s[j] == s[j + 1])
				inc(c, H(i, j, j + 1));
		if(i == 0) {
			f[m] = c, g[k][k] = 0;
			for(int j = m; j < k; ++ j)
				g[j][j] = 25, g[j][j + 1] = 1;
		} else {
			g[i][i] = 24, g[i][k - ceil(m - i)] = c;
			if(i == 1) f[1] = 1;
			else g[i - 1][i] = 1;
		}
		// only when progressing (n+m)/2-th step ,
		// I chose s[j],s[j + 1] ,then the answer is wrong 
	}
	
	ksm(ceil(n + m));
	dec(ans, f[k]);
	printf("%dn", ans);
	return 0;
}
程序员灯塔
转载请注明原文链接:[CF506E] Mr. Kitayuta's Gift 题解
喜欢 (0)