• 欢迎光临~

# [CF506E] Mr. Kitayuta's Gift 题解

(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]\$

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

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 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;
}
``````