给定一个size不超过2*106的string，里面仅包含w, o, ?三种字符。问有多少种填写?的方式使得最终的串是一个合法的样式。合法的样式定义为：
- n个w和n个o连接成的串是一个合法的串
- 两个合法的串连接也是一个合法的串
递推方程是裸的。
\[ f_i = \begin{cases} 1 &\mbox{i = 0} \\ \sum{f_j} &\mbox{s[j, i) is a string like w^no^n} \end{cases} \]
求$$f_n$$即可。
关键在于如何转移。其实能加速转移的方法我遇见过的总结起来就那么几种。离不开两个关键词，连续和凸性。
稍微看了一下感觉不满足凸性，于是就找连续性。然而直接看转移区间是不满足连续性的。找了好久发现对于一个给定的对称轴，往两边增长的时候，合法的pattern是满足连续性的(即小于某一长度都是合法pattern，超出的都不合法)。想了很久，发现还是没法转移。大概这种二维关系能做优化的也只有固定一个值再去考虑别的值的影响了。于是去看了题解，发现他将可以形成$$w^no^n$$的字符串分成了两种情况考虑，而这两种情况分别满足连续性。
为了方便讨论，我们设legal(i, j)表示s[i, j)可以形成形如$$w^no^n$$的字符串。
- 前一半全是?的。这种情况对于一个固定的i，legal(i, j)随着j的增长，值是单调的。(由true变false)，所以f[i]往后的影响是某一个区间，这用树状数组或者直接加delta值在起点和终点的办法就可以实现快速转移。
- 前一半包含有w的。这种情况对于一个固定的j，legal(i, j)虽然i的递减，值是单峰的。(由false变true再变false)这个的证明并不是那么显然，但是只要考虑到j前面第一个出现的w就会发现是有上下界限制的。具体限制包含4个，上界两个，下界两个，取交即可。然后就可以用f的部分和来快速求出答案。
实现起来还是有一点细节的。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int MAXN = 2000005;
int f[MAXN / 2 + 10];
int fsum[MAXN / 2 + 10];
int Tr[MAXN / 2 + 10];
int prevw[MAXN], prevo[MAXN], nextw[MAXN], nexto[MAXN];
const int Mod = 1e9 + 7;
string s;
void add(int i, int x) {
x %= Mod;
x += Mod;
x %= Mod;
for (++i; i < MAXN / 2 + 10; i += i & -i) {
Tr[i] += x;
Tr[i] %= Mod;
}
}
int get(int i) {
int res = 0;
for (++i; i; i -= i & -i) {
res += Tr[i];
res %= Mod;
}
return res;
}
int Next(int x, int i) {
if (x == 1)
return s[i] == 'w' ? i : nextw[i];
else
return s[i] == 'o' ? i : nexto[i];
}
int gao() {
int n = s.size();
if (n & 1) return 0;
memset(f, 0, sizeof(f));
memset(fsum, 0, sizeof(fsum));
f[0] = fsum[1] = 1;
fsum[0] = 0;
int wp = -1, op = -1;
rep (i, n + 1) {
prevw[i] = wp;
prevo[i] = op;
if (i < n && s[i] == 'w') wp = i;
if (i < n && s[i] == 'o') op = i;
}
wp = n; op = n;
for (int i = n; i >= 0; i--) {
nextw[i] = wp;
nexto[i] = op;
if (i < n && s[i] == 'w') wp = i;
if (i < n && s[i] == 'o') op = i;
}
rep (i, n / 2 + 1) {
int &res = f[i] += get(i), lhs, rhs;
int p;
lhs = (p = prevw[i * 2]) == -1 ? n : max((i * 2 - p + 1) / 2, i * 2 - nexto[p]);
rhs = (p = prevw[i * 2]) == -1 ? -9 : min(i * 2 - p, (i * 2 - prevo[p] + 1) / 2);
if (lhs < rhs)
res += (fsum[i - lhs + 1] - fsum[i - rhs + 1] + Mod) % Mod;
res %= Mod;
if (i * 2 == n) break;
int len = min((Next(1, i * 2) - i * 2) / 2, Next(0, i * 2) - i * 2);
add(i + 1, res);
add(i + 1 + len, -res);
fsum[i + 1] = (fsum[i] + res) % Mod;
}
return f[n / 2];
}
class WolfDelaymasterHard {
public:
int countWords(int, int, int, int, int, int, int, int, int);
};
int WolfDelaymasterHard::countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd) {
s.resize(N);
rep (i, N) s[i] = '?';
ll x = w0;
for(int i=0;i<wlen;i++){
s[x] = 'w'; // Rewrite the x-th (0-based) character of s
x = (x * wmul + wadd) % N;
}
x = o0;
for(int i=0;i<olen;i++){
s[x] = 'o'; // Rewrite the x-th (0-based) character of s
x = (x * omul + oadd) % N;
}
memset(Tr, 0, sizeof(Tr));
return gao();
}