【解题报告】NOI Online 2021 提高组
$\text{angry}$
观察字符串：
$\texttt{abbabaabbaababba....}$
考虑 $\texttt{b}$ 的位置，如果现在有一个长度为 $2^k$ 的前缀，且位置 $x$ 为 $\texttt{b}$，那么 $2^k+x$ 必然为 $\text{a}$。反之亦然。因此可以观察到相当于在 $x$ 的二进制位上加一个 $1$，这会使得 $\texttt{a},\texttt{b}$ 翻转。
因此可以得到：第 $x$ 位为 $\texttt{b}$ 当且仅当 $\text{popcount(x)}$ 是奇数。设计函数 $h(x)=(-1)^{\text{popcount(x)}}$。
那么柿子可以变成：
$$ \dfrac{1}{2}\sum_{x=0}^{n-1} (1-h(x))\times f(x) $$
分开变成：
$$ \dfrac{1}{2}(\sum_{x=0}^{n-1} f(x)-\sum_{x=0}^{n-1} h(x)f(x)) $$
前面把多项式拆掉就可以转换为自然数等幂和，考虑求后面。
考虑使用类似数位 $\text{dp}$ 的方式，把 $n$ 按照二进制位拆掉。令：
$$ n=\sum_{i=1}^t 2^{b_i} $$
那么 $\sum_{x=0}^{n-1} (-1)^{\text{popcount(x)}}f(x)$ 变为：
$$ \sum_{x=0}^{n-1} (-1)^{\text{popcount(x)}}\sum_{i=0}^{k-1} a_i x^i $$
交换和式：
$$ \sum_{i=0}^{k-1} a_i \sum_{x=0}^{n-1} (-1)^{\text{popcount(x)}} x^i $$
然后把 $n$ 拆掉，类似按照数字最高位分组：
$$ \sum_{i=0}^{k-1} a_i \sum_{p=1}^{t} (-1)^{t-p} (\sum_{x=0}^{2^{b_p}-1}(-1)^{\text{popcount(x)}}\times(x+\sum_{q=p+1}^t 2^{b_q})^i) $$
例如 $n=101001_{(2)}$，那么划分为 $[0,100000)$，$[100000,101000)$，$[101000,101001)$。
看到后面的柿子：
$$ \sum_{x=0}^{2^{b_p}-1}(-1)^{\text{popcount(x)}}\times(x+\sum_{q=p+1}^t 2^{b_q})^i $$
令：
$$ \text{F}(i,s,b)=\sum_{x=0}^{2^{b}-1}(-1)^{\text{popcount(x)}}\times(x+s)^i $$
二项式定理展开：
$$ \text{F}(i,s,b)=\sum_{x=0}^{2^{b}-1}(-1)^{\text{popcount(x)}}\sum_{c=0}^{i}\binom{i}{c}x^c s^{i-c} $$
交换和式：
$$ \text{F}(i,s,b)=\sum_{c=0}^i \binom{i}{c} s^{i-c} \sum_{x=0}^{2^b-1} (-1)^{\text{popcount(x)}}x^c $$
令后面 $\sum_{x=0}^{2^b-1} (-1)^{\text{popcount(x)}}x^c$ 为 $g(b,c)$。考虑递推来求这个东西，从 $g(b,c)$ 转移到 $g(b+1,c)$。
$$ g(b+1,c)=g(b,c)+(-1)\times \sum_{x=0}^{2^b-1} (-1)^{\text{popcount(x)}}(x+2^b)^c $$
$$ =g(b,c)-\sum_{x=0}^{2^b-1} (-1)^{\text{popcount(x)}}\sum_{l=0}^c\binom{c}{l} x^l(2^b)^{c-l} $$
$$ =g(b,c)-\sum_{l=0}^c\binom{c}{l}(2^b)^{c-l}g(b,l) $$
实际上就是加上最高位为 $1$ 的那些。
玄幻的来了 有定理：
若 $b>c$，则 $g(b,c)=0$。
这个可以归纳证明。表示这个证明我咕了
而次数只有 $500$，所以可以推出 $\mathcal{O}(k^2)$ 个状态，然后一步一步推回去即可，需要注意的是，在这题中我们大部分情况认为 $0^0=1$。时间复杂度 $\mathcal{O}(k^3+\log n)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 5e5 + 10;
const int SIZ = 510;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, k, popc, sum, Ans, inv2 = (mod + 1) >> 1;
int a[MAXN], p2[MAXN], fac[SIZ], ifac[SIZ];
int g[SIZ][SIZ];
char s[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
void Modadd(int &x, int y) {
if(y < 0) y += mod;
x += y;
if(x >= mod) x -= mod;
}
int qpow(int x, int b) {
int res = 1;
for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
return res;
}
int C(int x, int y) {
if(x < y) return 0;
return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
void Init() {
fac[0] = ifac[0] = p2[0] = 1;
for(int i = 1; i < MAXN; ++i) p2[i] = p2[i - 1] * 2 % mod;
for(int i = 1; i < SIZ; ++i) fac[i] = fac[i - 1] * i % mod;
ifac[SIZ - 1] = inv(fac[SIZ - 1]);
for(int i = SIZ - 2; i; --i) ifac[i] = ifac[i + 1] * (i + 1) % mod;
for(int i = 1; i <= n; ++i) {
popc ^= (s[i] == '1');
if(s[i] == '1') (sum += p2[n - i]) %= mod;
}
}
namespace Kpow {
int y[MAXN];
int a[MAXN], b[MAXN], cnt;
int kpow(int n, int k) {
if(n < 0) return 0;
int ans = 0;
for(int i = 1; i <= min(n, k + 2); ++i)
(y[i] = y[i - 1] + qpow(i, k)) %= mod;
if(n <= k + 2) return y[n];
cnt = a[0] = b[0] = 1;
for(int i = 1; i <= k + 2; ++i) {
(cnt *= (n - i) % mod) %= mod;
a[i] = (a[i - 1] * i) % mod;
b[i] = ((-b[i - 1] * i) % mod + mod) % mod;
}
for(register int i = 1;i <= k + 2; ++i)
(ans += y[i] * cnt % mod * inv(n - i) % mod * inv(a[i - 1] * b[k - i + 2] % mod) % mod + mod) %= mod;
return ans;
}
}
using Kpow :: kpow;
void GetG() {
g[0][0] = 1;
for(int i = 1; i < k; ++i) g[1][i] = mod - 1;
for(int c = 0; c < k; ++c) {
for(int b = 1, tmp; b <= c; ++b) {
tmp = 0;
for(int l = 0; l <= c; ++l)
(tmp += C(c, l) * p2[b * (c - l)] % mod * g[b][l] % mod) %= mod;
g[b + 1][c] = (g[b][c] - tmp + mod) % mod;
}
}
}
int F(int i, int s, int b) {
int res = 0, now = 1;
for(int c = 0; c <= i; ++c) {
(res += C(i, c) * now % mod * g[b][i - c] % mod) %= mod;
now = now * s % mod;
}
return res;
}
int calc() {
int res = 0;
for(int i = 0, tmp, opt, ss; i < k; ++i) {
tmp = 0, opt = popc ? -1 : 1, ss = sum;
for(int p = n, bp = 0; p >= 1; --p, ++bp) {
if(bp > k) break;
if(s[p] == '0') continue;
opt = -opt;
ss = (ss - p2[bp]) % mod;
(tmp += opt * F(i, ss, bp)) %= mod;
}
(res += tmp * a[i] % mod) %= mod;
}
return res;
}
int A() {
int res = 0;
for(int i = 0; i < k; ++i)
(res += a[i] * ((i == 0) + kpow(sum - 1, i)) % mod) %= mod;
return res;
}
signed main () {
#ifdef FILE
freopen("angry.in", "r", stdin);
freopen("angry.out", "w", stdout);
#endif
scanf("%s", s + 1); n = strlen(s + 1);
read(k);
for(int i = 0; i < k; ++i) read(a[i]);
Init(); GetG();
Ans = (A() - calc()) % mod;
Ans = Ans * inv2 % mod;
printf("%lld\n", (Ans + mod) % mod);
return 0;
}
$\text{block}$
对字符串 $s$ 建立子序列自动机，然后在 $t$ 上枚举子串，在子序列自动机上走，然后就可以判断一个子串是否合法了，这里是 $\mathcal{O}(n^2)$。
接着考虑去除 $t$ 中相同的子串的重复贡献，写个哈希表或者上 $\text{SAM}$ 就可以了。
时间复杂度 $\mathcal{O}(n^2)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 3010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, Ans, st[MAXN << 1];
char a[MAXN], b[MAXN];
bool ok[MAXN][MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
struct SubseqAutomaton {
int ch[MAXN][26], pre[MAXN];
void build() {
for(int c = 0; c < 26; ++c) {
pre[c] = INF;
for(int i = 0; i <= n; ++i) ch[i][c] = INF;
}
for(int i = n; i >= 0; --i) {
for(int c = 0; c < 26; ++c) {
if(pre[c] == INF) continue;
ch[i][c] = pre[c];
}
pre[a[i] - 'a'] = i;
}
}
} A;
struct SuffixAutomaton {
struct NODE {
int len, fa;
int ch[26];
} T[MAXN << 1];
int las = 1, tot = 1, pos[MAXN << 1];
void Insert(int c, int at) {
int p = las, np;
np = las = ++tot;
pos[at] = tot;
T[np].len = T[p].len + 1;
for(; p && !T[p].ch[c]; p = T[p].fa) T[p].ch[c] = np;
if(!p) return T[np].fa = 1, void();
int q = T[p].ch[c];
if(T[q].len == T[p].len + 1) return T[np].fa = q, void();
int nq = ++tot;
T[nq] = T[q]; T[nq].len = T[p].len + 1;
T[q].fa = T[np].fa = nq;
for(; p && T[p].ch[c] == q; p = T[p].fa) T[p].ch[c] = nq;
}
void build() {
for(int i = 1; i <= n; ++i)
Insert(b[i] - 'a', i);
}
} SAM;
signed main () {
#ifdef FILE
freopen("block.in", "r", stdin);
freopen("block.out", "w", stdout);
#endif
read(n);
scanf("%s", a + 1), scanf("%s", b + 1);
A.build(); SAM.build();
for(int i = 1, now; i <= n; ++i) {
now = 0;
for(int j = i; j <= n; ++j) {
if(A.ch[now][b[j] - 'a'] == INF) break;
ok[i][j] = true;
now = A.ch[now][b[j] - 'a'];
}
}
for(int i = 1, now; i <= n; ++i) {
now = SAM.pos[i];
while(now) {st[now] = i; now = SAM.T[now].fa;}
}
for(int i = 2; i <= SAM.tot; ++i)
for(int l = SAM.T[SAM.T[i].fa].len + 1; l <= SAM.T[i].len; ++l)
Ans += ok[st[i] - l + 1][st[i]];
printf("%d\n", Ans);
return 0;
}$\text{island}$
考虑 $\text{01trie}$。
对于 $\max\{d_i\}\le \min\{b_i\}$，也就是等号右边全是 $d$。可以直接建立可持久化 $\text{trie}$，然后每次拿 $d$ 在上面走。判断一下，然后加几个子树的 $\text{size}$ 就行。
对于 $\max\{b_i\}\le \min\{d_i\}$，也就是等号右边全是 $b$。把询问差分掉，然后离线询问。用 $\text{trie}$ 维护前缀，然后每次对于当前询问的 $c$，加上 $c$ 在 $\text{trie}$ 上走的路上的一些 $\text{tag}$。具体来说，每次可以考虑 $a\text{ xor } b$ 每一位的取值，然后相应的分类讨论一下是否要打 $\text{tag}$。
对于全体情况，沿用离线的思想。而我们需要将上述两种情况划分开。可以考虑先将插入和询问均按照 $b/d$ 排序，然后考虑 $\text{cdq}$ 分治。
分治的时候将区间内的节点按照下标排序，考虑左边的插入对右边的询问的贡献，这时候左边的 $b$ 较小，用第二种方法；右边的插入对左边的询问的贡献，左边的 $d$ 比较小，用第一种方法即可。
时间复杂度 $\mathcal{O}(n\log^2n)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 1e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
struct Query {
int a, b, c, d, p, id, opt;
Query(int _a = 0, int _b = 0, int _c = 0, int _d = 0, int _p = 0, int _id = 0, int _o = 0) :
a(_a), b(_b), c(_c), d(_d), p(_p), id(_id), opt(_o) {}
} q[MAXN << 2];
struct Trieb {
int root = 0, ch[MAXN * 24][2], cnt = 0;
int tag[MAXN * 24];
int *stk[MAXN * 48], top;
void Insert(int a, int b) {
int now = root, x = (a ^ b);
for(int i = 23; ~i; --i) {
int &to = ch[now][(x >> i) & 1];
int &ito = ch[now][!((x >> i) & 1)];
if(!ito) ito = ++cnt, stk[++top] = &ito;
if(((b >> i) & 1)) tag[ito]++;
if(!to) to = ++cnt, stk[++top] = &to;
now = to;
}
tag[now]++;
}
int Query(int x) {
int res = 0, now = root;
for(int i = 23; ~i; --i) {
if(!ch[now][(x >> i) & 1]) break;
now = ch[now][(x >> i) & 1];
res += tag[now];
}
return res;
}
void clear() {
while(top) *stk[top--] = 0;
for(int i = 1; i <= cnt; ++i) tag[i] = 0;
cnt = 0;
}
} Tb;
struct Tried {
int root = 0, ch[MAXN * 24][2], cnt = 0;
int siz[MAXN * 24];
int *stk[MAXN * 48], top;
void Insert(int a) {
int now = root;
for(int i = 23; ~i; --i) {
int &to = ch[now][(a >> i) & 1];
if(!to) to = ++cnt, stk[++top] = &to;
now = to; siz[now]++;
}
}
int Query(int c, int d) {
int now = root, x = (c ^ d), res = 0;
bool ok = true;
for(int i = 23; ~i; --i) {
if(ch[now][!((x >> i) & 1)] && ((d >> i) & 1))
res += siz[ch[now][!((x >> i) & 1)]];
if(!ch[now][(x >> i) & 1]) {ok = false; break;}
now = ch[now][(x >> i) & 1];
}
if(ok) res += siz[now];
return res;
}
void clear() {
while(top) *stk[top--] = 0;
for(int i = 1; i <= cnt; ++i) siz[i] = 0;
cnt = 0;
}
} Td;
int n, qs;
int Ans[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
bool cmpd(Query a, Query b) {return a.d < b.d;}
bool cmppos(Query a, Query b) {return a.p < b.p;}
void DoL(int L, int R) {
int mid = (L + R) >> 1;
sort(q + L, q + mid + 1, cmppos);
sort(q + mid + 1, q + R + 1, cmppos);
int p1 = L, p2 = mid + 1;
while(p2 <= R) {
if(!q[p2].opt) {p2++; continue;}
while(p1 <= mid && q[p1].p <= q[p2].p) {
if(!q[p1].opt) Tb.Insert(q[p1].a, q[p1].b);
p1++;
}
Ans[q[p2].id] += q[p2].opt * Tb.Query(q[p2].c);
p2++;
}
Tb.clear();
}
void DoR(int L, int R) {
int mid = (L + R) >> 1;
int p1 = L, p2 = mid + 1;
while(p1 <= mid) {
if(!q[p1].opt) {p1++; continue;}
while(p2 <= R && q[p2].p <= q[p1].p) {
if(!q[p2].opt) Td.Insert(q[p2].a);
p2++;
}
Ans[q[p1].id] += q[p1].opt * Td.Query(q[p1].c, q[p1].d);
p1++;
}
Td.clear();
}
void solve(int L, int R) {
if(L == R) return;
int mid = (L + R) >> 1;
solve(L, mid), solve(mid + 1, R);
DoL(L, R); DoR(L, R);
}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(n), read(qs);
for(int i = 1, a, b; i <= n; ++i) {
read(a), read(b);
q[i] = Query(a, b, 0, b, i, 0, 0);
}
int tmp = n;
for(int i = 1, c, d, l, r; i <= qs; ++i) {
read(l), read(r), read(c), read(d);
q[++tmp] = Query(0, 0, c, d, r, i, 1);
if(l - 1 > 0) q[++tmp] = Query(0, 0, c, d, l - 1, i, -1);
}
sort(q + 1, q + tmp + 1, cmpd);
solve(1, tmp);
for(int i = 1; i <= qs; ++i)
printf("%d\n", Ans[i]);
return 0;
}