我觉得这道题非常有前途.......
题意：给定一个填了一半的数组，你要把它补完，使之不存在奇回文串，求方案数。字符集为k。
n,k<=20w
解：不能有长为三的回文串。也就是不能有两个相隔1的数相同。
发现奇偶下标互相独立，抽出来就是不能有两个相邻的数相同。
我们可以设f[i][0]表示第i位填的跟之后第一个非空位置不同的方案数，f[i][1]是相同。
转移的时候，反正我个大SB分8类分类讨论，还要考虑后面没有非空位置的情况......
#include <bits/stdc++.h> typedef long long LL;
const int N = ;
const LL MO = ; int a[N], n, k, nex[N];
LL f[N][]; int main() {
int cnt = ;
scanf("%d%d", &n, &k); for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
if(i >= && a[i] == a[i - ] && a[i] != -) {
puts("");
return ;
}
} for(int i = n; i >= ; i--) {
if(a[i] != -) nex[i] = a[i];
else nex[i] = nex[i + ];
}
LL ans = ;
f[][] = f[][] = ;
for(int i = ; i <= n; i += ) {
if(a[i] != -) continue;
if(i - < && i + > n) {
ans *= k;
}
else if(i - < && a[i + ] == -) {
f[i][] = nex[i] ? k - : k;
f[i][] = nex[i] ? : ;
}
else if(i - < ) {
ans = ans * (k - ) % MO;
}
else if(i + > n && a[i - ] == -) {
ans = ans * f[i - ][] % MO * (k - ) % MO;
}
else if(i + > n) {
ans = ans * (k - ) % MO;
}
else if(a[i + ] != - && a[i - ] != -) {
ans = ans * (a[i - ] == a[i + ] ? k - : k - ) % MO;
}
else if(a[i - ] != - && a[i + ] == -) {
f[i][] = ((a[i - ] == nex[i] || !nex[i]) ? k - : k - );
f[i][] = ((a[i - ] == nex[i] || !nex[i]) ? : );
}
else if(a[i - ] == - && a[i + ] != -) {
ans = ans * ((f[i - ][] * (k - ) % MO + f[i - ][] * (k - ) % MO) % MO) % MO;
}
else {
f[i][] = (f[i - ][] * (k - ) % MO + f[i - ][] * (nex[i] ? k - : k - ) % MO) % MO;
f[i][] = nex[i] ? f[i - ][] : ;
}
}
LL temp = ans; ans = ;
for(int i = ; i <= n; i += ) {
if(a[i] != -) continue;
if(i - < && i + > n) {
ans *= k;
}
else if(i - < && a[i + ] == -) {
f[i][] = nex[i] ? k - : k;
f[i][] = nex[i] ? : ;
}
else if(i - < ) {
ans = ans * (k - ) % MO;
}
else if(i + > n && a[i - ] == -) {
ans = ans * f[i - ][] % MO * (k - ) % MO;
}
else if(i + > n) {
ans = ans * (k - ) % MO;
}
else if(a[i + ] != - && a[i - ] != -) {
ans = ans * (a[i - ] == a[i + ] ? k - : k - ) % MO;
}
else if(a[i - ] != - && a[i + ] == -) {
f[i][] = ((a[i - ] == nex[i] || !nex[i]) ? k - : k - );
f[i][] = ((a[i - ] == nex[i] || !nex[i]) ? : );
}
else if(a[i - ] == - && a[i + ] != -) {
ans = ans * ((f[i - ][] * (k - ) % MO + f[i - ][] * (k - ) % MO) % MO) % MO;
}
else {
f[i][] = (f[i - ][] * (k - ) % MO + f[i - ][] * (nex[i] ? k - : k - ) % MO) % MO;
f[i][] = nex[i] ? f[i - ][] : ;
}
} printf("%lld\n", ans * temp % MO);
return ;
}
AC代码