21年1月3日 省选五校联合集训考试三

计数 + SAM + 计数。

\(\rm \color{black}{E}\color{red}{ternalAlexander}\) 出的神仙模拟赛，我再一次爆零垫底了，不过题目质量很高👍。

EA 的官方题解

A 通用计数

题目

求有多少不同的包含 \(n\) 个点的有标号无根树，满足：对于任何一个点 \(x\) ，都存在点 \(y\) 使得 \(x\) 和 \(y\) 之间有一条边且 \(|x-y| = 1\)。

\(2\le n\le 10^5\)。

容斥 + 多项式求逆。

转化题意将带标号的点 \(1\dots n\) 依次连成一条链，将其划分，并且一个点的两条边不能同时被割去，然后连接成一棵新树。

有个引理：\(n\) 个点 \(k\) 个连通块形成生成树方案数为 \(n^{k-2}\prod_{i=1}^k a_i\)。

枚举合法划分方案（看做一个割掉边的集合）\(P\)，记 \(W(P)\) 为划分 \(P\) 产生的方案数，这里提出一个 \(n^{-2}\) 后面再乘回去，所以 \(W(P)=\prod_{i=1}^k a_in\)。

设 \(n\) 个点满足要求的答案为 \(F(n)\times n^{-2}\)，现在要计算 \(F(n)\)。

直接计和会发现有的方案重复了，因为没有限定连的是那条边，两个连通块可能重新连上割掉的边合并成一个。

考虑容斥，然后推式子（这里 \(Q\) 是 \(P\) 的父集代表 \(P\) 进一步划分得到的方案）： \[ \begin{aligned} F(n)&=\sum_{P}\sum_{P\subset Q}(-1)^{|Q|-|P|}W(Q)\\ &=\sum_{Q}W(Q)\sum_{P\subset Q}(-1)^{|Q|-|P|}\\ \end{aligned}\\ \] 设 \(D(P)=\sum_{P\subset Q}(-1)^{|Q|-|P|}\)，表示 \(P\) 的容斥系数。

若 \(P\) 将链划分成连通块 \(\{a_1,a_2\dots a_k\}\)，发现各个连通块的 \(D\) 值相互不影响，于是得到 \(D(P)=\prod_{i=1}^kD(\{a_i\})\)。

而连通块的 \(D\) 值是可以 DP 得到的，这里变量为数值代表连通块大小： \[ \begin{aligned} D(1)&=0\\ D(2)&=1\\ D(i)&=D(i-1)-D(i-2) \end{aligned} \] 递推式可以理解为：为了合法最后一条边不能断，对于一条链最后倒数第二条边，断掉对系数可以产生 \(-1\) 的贡献。

对 \(F\) 我们进一步得到： \[ \begin{aligned} F(n)&=\sum_{Q}W(Q)D(Q)\\ &=\sum_{Q}\prod_{i=1}^ka_inD(a_i)\\ \end{aligned} \] 再巧妙地设 \(G(i)=i\cdot n\cdot D(i)\)，我们只要枚举第一个连通块的大小： \[ \begin{aligned} F(n)&=\sum_{Q}\prod_{i=1}^kG(i)\\ &=\sum_{i=1}^nG(i)F(n-i) \end{aligned} \] 哇塞是个卷积，\(G\) 可以由 \(D\) 得到，那么就可以分治 FFT 得到 \(F(n)\) 了。

或者（这里）用多项式求逆解决，计算 \((1-G(x))^{-1}\) 即可。

复杂度 \(\mathcal O(n\log n)\)。

const int N = 4e5 + 9;
const int P = 998244353;

// 省略一大堆多项式模板代码

inline void poly_inv(int *f, int n);

int n;
int D[N], F[N];

inline void main() {
    read(n);
    D[2] = 1;
    for (int i = 3; i <= n; ++i) D[i] = (D[i - 1] - D[i - 2] + P) % P;
    for (int i = 1; i <= n; ++i) F[i] = (LL)i * n % P * D[i] % P;
    for (int i = 1; i <= n; ++i) F[i] = (P - F[i]) % P;
    F[0] += 1;
    poly_inv(F, n + 1);
    printf("%lld\n", (LL)F[n] * power((LL)n * n % P, P - 2) % P);
}

B 屏蔽词汇

题目

给出串 \(S\)，每次询问 \(S\) 的一个子串 \(T\)，求出至少要往 \(S\) 中插入多少个分隔符使得 \(T\) 不再是 \(S\) 的子串。

\(3\le n,q\le 10^5\)。

SAM + 线段树合并。

贪心的想，每次找到 \(T\) 在 \(S\) 中最早出现的位置，然后在最后一个字符之前加一个分隔符，继续做下去。（考场上没想到线段树合并就删了 SAM 像这样写了 \(\mathcal O(n^2)\) 暴力。）

那么先把 \(S\) 串扔到 SAM 里面，考虑维护子串出现位置集合，那就每个节点挂一棵线段树。

建出 parent 树后，每个节点就需要维护子树中所有线段树的并，就用到线段树合并。

这样对于询问，在 parent 树上倍增找到代表子串 \(T\) 的节点，然后贪心做。

同时需要将计算过的答案记忆化。

复杂度是 \(\mathcal O((n+q)\sqrt{n}\log n)\) 的，证明：

设询问子串 \(T\) 长度为 \(L\)，分类讨论：

• \(L\le \sqrt{n}\)：我们贪心一次的复杂度 \(\mathcal O(c\log n)\)，\(c\) 为 \(T\) 的出现次数，\(c\) 上界是 \(\mathcal O(n)\) 的；但是加上记忆化之后，发现长度 \(\le \sqrt{n}\) 的串一共 \(n\sqrt{n}\) 个，总复杂度 \(\mathcal O(n\sqrt{n}\log n)\)。
• \(L>\sqrt{n}\)：贪心时每次向后跳 \(L-1\) 个单位，所以产生贡献的位置集合大小不超过 \(\sqrt{n}\)，总复杂度 \(\mathcal O(q\sqrt{n}\log n)\)。

const int N = 4e5 + 9;
const int M = 6e6 + 9;

int n, Q;
int id[N];
char str[N];
map<int, int> mem[N];

struct Graph {
    int cnt;
    int head[N], nxt[N], to[N];
    inline void add(int u, int v) {
        ++cnt, nxt[cnt] = head[u], to[cnt] = v, head[u] = cnt;
    }
} G;

struct SegmentTree {
    int tot;
    int rt[N], sum[M], ls[M], rs[M];
    inline void push_up(int suc) {
        sum[suc] = sum[ls[suc]] + sum[rs[suc]];
    }
    void modify(int &suc, int l, int r, int p) {
        if (!suc) suc = ++tot;
        if (l == r) {
            sum[suc] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) modify(ls[suc], l, mid, p);
        else modify(rs[suc], mid + 1, r, p);
        push_up(suc);
    }
    int merge(int u, int v, int l, int r) {
        if (!u || !v) return u + v;
        if (l == r) {
            sum[u] += sum[v];
            return u;
        }
        int mid = (l + r) >> 1, suc = ++tot;
        ls[suc] = merge(ls[u], ls[v], l, mid);
        rs[suc] = merge(rs[u], rs[v], mid + 1, r);
        push_up(suc);
        return suc;
    }
    int find(int suc, int l, int r, int p) {
        if (!sum[suc]) return 0;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (p > mid) return find(rs[suc], mid + 1, r, p);
        int res = find(ls[suc], l, mid, p);
        if (!res) res = find(rs[suc], mid + 1, r, p);
        return res;
    }
} T;

struct SuffixAutomaton {
    int tot, last;
    int link[N], ch[N][26], len[N], fa[N][20];
    SuffixAutomaton() : tot(1), last(1) {}
    inline int insert(int c, int pos) {
        int p = last, np = last = ++tot;
        len[np] = len[p] + 1, T.modify(T.rt[np], 1, n, pos);
        while (p && !ch[p][c]) ch[p][c] = np, p = link[p];
        if (!p) link[np] = 1;
        else {
            int q = ch[p][c];
            if (len[q] == len[p] + 1) link[np] = q;
            else {
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                len[nq] = len[p] + 1, link[nq] = link[q];
                link[q] = link[np] = nq;
                while (p && ch[p][c] == q) ch[p][c] = nq, p = link[p];
            }
        }
        return np;
    }
    inline void init() {
        for (int i = 2; i <= tot; ++i) G.add(link[i], i);
        dfs(1, 0);
    }
    void dfs(int u, int fat) {
        fa[u][0] = fat;
        for (int i = 1; i <= 17; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
        for (int i = G.head[u]; i; i = G.nxt[i]) {
            int v = G.to[i];
            dfs(v, u);
            T.rt[u] = T.merge(T.rt[u], T.rt[v], 1, n);
        }
    }
    inline int get_fa(int u, int k) {
        for (int i = 17; ~i; --i)
            if (fa[u][i] && len[fa[u][i]] >= k) u = fa[u][i];
        return u;
    }
} A;

inline void main() {
    cin >> n >> Q >> (str + 1);
    for (int i = 1; i <= n; ++i)
        id[i] = A.insert(str[i] - 'a', i);
    A.init();
    while (Q--) {
        int l, r, len;
        cin >> l >> r;
        if (l == r) {
            cout << "-1\n";
            continue;
        }
        len = r - l + 1;
        int x = A.get_fa(id[r], len), i = 1, ans = 0;
        if (mem[x].count(len)) {
            cout << mem[x][len] << '\n';
            continue;
        }
        while (i <= n) {
            int p = T.find(T.rt[x], 1, n, i);
            if (!p) break;
            ++ans, i = p + len - 1;
        }
        mem[x][len] = ans;
        cout << ans << '\n';
    }
}

C 数位规划

题目

对于一个长度为 \(n\) 的由 \(0 \sim 9\) 组成的数字串 \(S\)，定义 \(S\) 的优秀度为：在 \([L,R]\) 范围内的，且在 \(S\) 中作为子串出现过的整数的个数。

给出 \(L,R,n\)，求所有长度为 \(n\) 的 \(S\) 的优秀度的之和。

\(n\le 400\)，\(L,R\le 10^{18}\)。

太难了，先咕着。