【解题报告】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;
}
添加新评论