SDOI 2017 Round 2 大赏

2020-03-08

图源 zzq's Blog, 至少我是从那里找到的

这 Round 2 也太毒瘤了 = =

久等了.

「SDOI2017」龙与地下城

验题人在多测的情况下总算是写了十行代码?

题目链接

https://loj.ac/problem/2267

解题思路

首先有一个多项式做法.

构造一个生成函数 $g(x)$, 其 $k$ 次项系数表示掷一次骰子造成伤害 $k$ 的概率, 则

$g(x) = \sum_{k=0}^{X-1} \frac{1}{X} x^k$

那么 $g(x)^Y$ 的 $A_i$ 到 $B_i$ 次项和即为答案.

对于这个多项式幂函数的计算, 可以用带大常数的 $O(n \log n)$ 多项式 $\exp$ , 或者朴素快速幂 $O(n \log ^2 n)$.

但是有精巧的做法, 此处直接把点值做 $Y$ 次幂就好了.

当年考场 AC 似乎有更为精巧的优化方法, 好像 myy 的论文 <再探快速傅里叶变换> 里有涉及, ~~以后再说以后再说~~

对于大数据 ~~如果问什么是大数据, 那就是 FFT 跑不过的数据~~, 则要用到中心极限定理.

记 $\zeta_{n} = \dfrac{\bar X - \mu}{\sigma / \sqrt n} = \dfrac{\sum\limits_{i=1}^n X_i - n \mu}{\sqrt {n \sigma ^2 }}$, 根据中心极限定理, 当 $n \rightarrow \infty$ 时, 认为其满足正态分布 $N(0, 1)$.

而正态分布 $N(\mu, \sigma^2)$ 的概率密度函数为

$f(x) = \frac{1}{\sqrt{ 2 \sigma^2 \pi }} e ^{ -\frac {(x-\mu)^2}{2 \sigma ^2} }$

对于 $N(0, 1)$, 带进去可得

$f(x) = \frac{1}{\sqrt{ 2 \pi}} e ^{ -\frac{x^2}{2} }$

具体应用到这道题中, 用自适应 Simpson 计算

$\int _a^b f(x)\ \mathrm d x$

就好了, 其中 $a = \dfrac{A_i - Y \mu}{\sqrt{ Y \sigma ^2 }}, b = \dfrac{B_i - Y\mu}{\sqrt{ Y \sigma ^ 2}}$.

代码实现

就这样吧 = =, 只能流下没有数理基础的眼泪.

至今不知道为什么直接大力 Simpson $[L, R]$ 会挂, 取端点做差就对了 = =

可能是因为 $L$ 正负性的问题?

> 点击显示 / 隐藏

// LOJ #2267
// DeP
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 262145 << 1, MAXM = 10;
const double PI = acos(-1.0);

struct Complex {
    double x, y;
    Complex(double _x = 0.0, double _y = 0.0): x(_x), y(_y) { }
    Complex operator + (const Complex& rhs) const { return Complex(x + rhs.x, y + rhs.y); }
    Complex operator - (const Complex& rhs) const { return Complex(x - rhs.x, y - rhs.y); }
    Complex operator * (const Complex& rhs) const {
        return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
    }
};

Complex fpow(Complex base, int b) {
    Complex ret(1.0, 0.0);
    while (b > 0) {
        if (b & 1) ret = ret * base;
        base = base * base, b >>= 1;
    }
    return ret;
}

namespace Poly {
    int r[MAXN];
    inline void init(const int& Lim, const int& L) {
        for (int i = 1; i < Lim; ++i) r[i] = (r[i>>1] >> 1) | ((i & 1) << (L-1));
    }

    void FFT(Complex* f, int Lim, int type) {
        for (int i = 1; i < Lim; ++i) if (i < r[i]) swap(f[i], f[r[i]]);
        for (int Mid = 1; Mid < Lim; Mid <<= 1) {
            Complex unit(cos(PI / Mid), type * sin(PI / Mid));
            for (int i = 0; i < Lim; i += (Mid << 1)) {
                Complex w(1.0, 0.0);
                for (int j = 0; j < Mid; ++j, w = w * unit) {
                    Complex f0 = f[i+j], f1 = w * f[i+j+Mid];
                    f[i+j] = f0 + f1, f[i+j+Mid] = f0 - f1;
                }
            }
        }
        if (type < 0) for (int i = 0; i < Lim; ++i) f[i].x /= Lim;
    }
}

int X, Y;
int A[MAXM], B[MAXM];
Complex g[MAXN];

inline double f(const double& x) {
    static const double frac = 1.0 / sqrt(2.0 * PI);
    return frac * exp(x * x / -2.0);
}
inline double simpson(const double& L, const double& R) {
    return (R - L) / 6.0 * (f(L) + f(R) + 4.0 * f((L + R) / 2.0));
}

inline double asr(double L, double R, const double& eps, double ans) {
    double Mid = (L + R) / 2.0;
    double fl = simpson(L, Mid), fr = simpson(Mid, R);
    if (fabs(fl + fr - ans) < 15 * eps) return fl + fr + (fl + fr - ans) / 15;
    return asr(L, Mid, eps / 2.0, fl) + asr(Mid, R, eps / 2.0, fr);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti;
    scanf("%d", &Ti);
    while (Ti--) {
        // init
        memset(g, 0, sizeof g);
        // input
        scanf("%d%d", &X, &Y);
        for (int i = 0; i < MAXM; ++i) scanf("%d%d", A+i, B+i);
        // solve
        if (X * Y < MAXN) {
            int Lim = 1, L = 0;
            while (Lim <= X * Y) Lim <<= 1, ++L;
            Poly::init(Lim, L);
            for (int i = 0; i < X; ++i) g[i].x = 1.0 / X;
            Poly::FFT(g, Lim, 1);
            for (int i = 0; i < Lim; ++i) g[i] = fpow(g[i], Y);
            Poly::FFT(g, Lim, -1);
            for (int i = 0; i < MAXM; ++i) {
                double ans = 0;
                for (int j = A[i]; j <= B[i]; ++j) ans += g[j].x;
                printf("%.6lf\n", ans);
            }
        } else {
            double mu = (X - 1.0) / 2.0, sigma2 = (X * X - 1.0) / 12.0;
            for (int i = 0; i < MAXM; ++i) {
                double L = (A[i] - Y * mu) / sqrt(Y * sigma2),
                       R = (B[i] - Y * mu) / sqrt(Y * sigma2);
                // printf("%.7lf\n", asr(L, R, 1e-9, simpson(L, R)));
                // 如果使用以上写法, 某些答案为 1.0 的情况, 算出来是 0.0 = =
                printf("%.7lf\n", asr(0, R, 1e-9, simpson(0, R)) - asr(0, L, 1e-9, simpson(0, L)));
            }
        }
    }
    return 0;
}

「SDOI2017」苹果树

题目链接

https://loj.ac/problem/2268

解题思路

观察题意可以发现, 关于 $k$ 的限定可以看作免费取一条从根开始的链, 再取 $k$ 个物品, 取儿子必须取至少一个父亲的树形依赖背包. 棘手的地方在于链的处理.

考虑怎么把链干掉. 可以发现, 树上点权都是正的, 如果取一条链, 那么一定从根一直取到叶子. 所以可以枚举叶子, 把树分成链左半部分和右半部分.

再看一遍树的结构, 实际上把树分成了 3 部分

链上免费取的部分
链左边付费取的部分 (我们把链上付费取的部分归到这里)
链右边付费取的部分

所以设 $f(i, j)$ 表示第 $i$ 个节点, 体积为 $j$ 的最大收益, 也就是在计算第 2 部分的答案.

类似地, 设 $g(i, j)$ 表示 DFS 序翻转后, 第 $i$ 个节点, 体积为 $j$ 的最大收益, 也就是在计算第 3 部分的答案.

树上依赖的关系不好处理, 考虑将每个物品数 $a_i > 1$ 节点拆开, 拆成一个物品数为 $1$ 的节点留在原来的位置, 以及一个物品数为 $a_i - 1$ 的节点挂在另外一个节点旁.

(实际上建图的时候并不必要把这个点真的拆开, 在转移的时候额外判断就好了).

最后枚举叶子, 累加第 1 部分, 把另外两部分拼起来即可. (也就是 $f(i, j) + g(i, j-k)$)

注意到对于每个节点的转移, 实际上是一个多重背包, 使用单调队列优化即可.

时间复杂度 $O(Qnk)$.

代码实现

实现参考了 Claris.

有些卡常, 需要把 DP 的二维数组开成一维, 增加缓存命中率.

> 点击显示 / 隐藏

// LOJ #2268
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 2e4 + 5, MAXK = 5e5 + 5, MAXM = 2 * MAXK + 25e6 + 5;

int n, K, M, ans;
int pre[MAXN], A[MAXN], V[MAXN];
int f[MAXM], g[MAXM];

inline void solve(int* F, const int& a, const int& v) {
    static int Q[MAXK], W[MAXK], head, tail;
    Q[head = 1] = tail = 0;
    for (int i = 0, j = 0; i <= K; ++i, j += v) {
        F[i] -= j;
        while (head <= tail && F[Q[tail]] < F[i]) --tail;
        Q[++tail] = i;
        while (head <= tail && i - Q[head] > a) ++head;
        W[i] = F[Q[head]] + j;
    }
    memcpy(F, W, M * sizeof (int));
}

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, (n + 1) * sizeof (int)), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to };
        head[from] = eidx;
    }

    void dfs0(int u) {
        if (A[u]) solve(f + M * u, A[u], V[u]);
        for (int i = head[u]; ~i; i = edges[i].nxt) {
            int v = edges[i].to;
            memcpy(f + M * v, f + M * u, M * sizeof (int));
            dfs0(v);
            for (int j = 1; j <= K; ++j)
                f[M * u + j] = max(f[M * u + j], f[M * v + j - 1] + V[v]);
            // "至少取一个父节点的物品" 的限制就体现在这里了, g(i, j) 同理
        }
    }

    void dfs1(int u, int s) {
        for (int i = head[u]; ~i; i = edges[i].nxt) {
            int v = edges[i].to;
            memcpy(g + M * v, g + M * u, M * sizeof (int));
            dfs1(v, s + V[u]);
            for (int j = 1; j <= K; ++j)
                g[M * u + j] = max(g[M * u + j], g[M * v + j - 1] + V[v]);
        }
        if (head[u] == -1) // leaf
            for (int j = 0; j <= K; ++j)
                ans = max(ans, V[u] + s + f[M * u + j] + g[M * u + K - j]);
        if (A[u]) solve(g + M * u, A[u], V[u]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti);
    while (Ti--) {
        // input
        read(n), read(K);
        for (int i = 1; i <= n; ++i)
            read(pre[i]), read(A[i]), read(V[i]), --A[i];
        // init
        ans = 0, M = K + 1;
        memset(f + M, 0, M * sizeof (int));
        memset(g + M, 0, M * sizeof (int));
        // solve
        Graph::init();
        for (int i = 2; i <= n; ++i) Graph::AddEdge(pre[i], i);
        Graph::dfs0(1);
        // 对于 "DFS 翻转", 反着建图即可
        Graph::init();
        for (int i = n; i >= 2; --i) Graph::AddEdge(pre[i], i);
        Graph::dfs1(1, 0);
        // output
        printf("%d\n", ans);
    }
    return 0;
}

「SDOI2017」切树游戏

题目链接

https://loj.ac/problem/2269

解题思路

先祭上猫锟的解题报告.

然后就是动态 DP 了.

此处信息仍具有可减性, 维护数非 0 部分的积, 以及乘积中 0 的个数即可了.

落实到代码中就是那个 Num 了.

还有个可以借鉴的 Trick 就是化简矩阵减小常数了. 直接搬来 immortalCO 的公式.

$\begin{pmatrix} \underline{a_1} & \underline{b_1} & 0 \\ 0 & 1 & 0 \\ \underline{c_1} & \underline{d_1} & 1 \end{pmatrix} \times \begin{pmatrix} \underline{a_2} & \underline{b_2} & 0 \\ 0 & 1 & 0 \\ \underline{c_2} & \underline{d_2} & 1 \end{pmatrix} = \begin{pmatrix} \underline{a_1 a_2} & \underline{b_1 + a_1 b_2} & 0 \\ 0 & 1 & 0 \\ \underline{a_2 c_1 + c_2} & \underline{b_2 c_1 + d_1 + d_2} & 1 \end{pmatrix}$

运用这个 Trick 的时候, 需要额外注意矩阵的运算顺序.

动态 DP 采用树链剖分实现, 时间复杂度 $O(n\log ^ 3 n)$.

~~最近一群毒瘤看着这个 log^3 不爽, 看来要去学 DDP 的 LCT 实现了~~

代码实现

> 点击显示 / 隐藏

// LOJ #2269
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read; using IO::Gc;

typedef long long LL;
const int MAXN = 3e4+5, MAXM = 128, P = 10007;

void FWT(int* f, int Lim, int type) {
    static const LL inv2 = 5004;
    for (int k = 1, Mid = 2; Mid <= Lim; Mid <<= 1, k <<= 1)
        for (int i = 0; i < Lim; i += Mid)
            for (int j = 0; j < k; ++j) {
                int f0 = f[i+j], f1 = f[i+j+k];
                f[i+j] = (f0 + f1) % P, f[i+j+k] = (f0 - f1 + P) % P;
                if (type == -1) f[i+j] = inv2 * f[i+j] % P, f[i+j+k] = inv2 * f[i+j+k] % P;
            }
}

int n, m, q;
int E[MAXM][MAXM], V[MAXN], inv[P];
int f[MAXN][MAXM], g[MAXN][MAXM], lg[MAXN][MAXM];

struct Num {
    int x, c;
    Num() { x = c = 0; }
    Num(int _x): x((_x == 0)? 1: _x), c(_x == 0) { }
    inline int val() { return c? 0: x; }
    Num& operator*= (const int& rhs) {
        if (rhs != 0) x = 1LL * x * rhs % P; else ++c;
        return *this;
    }
    Num& operator/= (const int& rhs) {
        if (rhs != 0) x = 1LL * x * inv[rhs] % P; else --c;
        return *this;
    }
} lf[MAXN][MAXM];

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN << 1];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to };
        head[from] = eidx;
    }
}

namespace HLD {
    using namespace Graph;
    int son[MAXN], pre[MAXN], depth[MAXN], size[MAXN];
    int dfn[MAXN], Ed[MAXN], rnk[MAXN], topfa[MAXN], dfs_clock;

    void dfs1(int u, int fa) {
        depth[u] = depth[fa] + 1;
        size[u] = 1, son[u] = -1, pre[u] = fa;
        for (int j = 0; j < m; ++j) f[u][j] = E[V[u]][j];
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if ((v = edges[i].to) == fa) continue;
            dfs1(v, u), size[u] += size[v];
            if (son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
            for (int j = 0; j < m; ++j) {
                f[u][j] = (f[u][j] + 1LL * f[u][j] * f[v][j] % P) % P;
                g[u][j] = (g[u][j] + g[v][j]) % P;
            }
        }
        for (int j = 0; j < m; ++j) g[u][j] = (g[u][j] + f[u][j]) % P;
    }

    void dfs2(int u, int top) {
        topfa[u] = top;
        dfn[u] = ++dfs_clock, rnk[dfs_clock] = u, Ed[top] = dfs_clock;
        if (~son[u]) dfs2(son[u], top);
        for (int j = 0; j < m; ++j) lf[u][j] = Num(E[0][j]);
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if ((v = edges[i].to) == pre[u] || v == son[u]) continue;
            dfs2(v, v);
            for (int j = 0; j < m; ++j)
                lf[u][j] *= (1 + f[v][j]) % P, lg[u][j] = (lg[u][j] + g[v][j]) % P;
        }
    }

    inline void solve(int rt = 1) { dfs1(rt, 0), dfs2(rt, rt); }
}

struct Node {
    int A[MAXM], B[MAXM], C[MAXM], D[MAXM];
    Node() { memset(this, 0, sizeof *this); }
    Node operator * (const Node& rhs) const {
        Node ret;
        for (int i = 0; i < m; ++i) {
            ret.A[i] = 1LL * A[i] * rhs.A[i] % P;
            ret.B[i] = (1LL * A[i] * rhs.B[i] % P + B[i]) % P;
            ret.C[i] = (1LL * rhs.A[i] * C[i] % P + rhs.C[i]) % P;
            ret.D[i] = (1LL * C[i] * rhs.B[i] % P + rhs.D[i] + D[i]) % P;
        }
        return ret;
    }
};

namespace SGT {
#define lc (nd<<1)
#define rc (nd<<1|1)
    Node dat[MAXN << 2];

    inline void maintain(int nd) { dat[nd] = dat[rc] * dat[lc]; }
    // 注意 maintain 合并两矩阵的顺序
    inline void newnode(int nd, int u) {
        for (int i = 0; i < m; ++i) {
            int a = 1LL * lf[u][i].val() * E[V[u]][i] % P;
            dat[nd].A[i] = dat[nd].B[i] = dat[nd].C[i] = a;
            dat[nd].D[i] = (a + lg[u][i]) % P;
        }
    }

    void build(int nd, int L, int R) {
        if (L == R) return newnode(nd, HLD::rnk[L]);
        int Mid = (L + R) / 2;
        build(lc, L, Mid), build(rc, Mid+1, R);
        maintain(nd);
    }

    void Mdy(int nd, int L, int R, const int& pos) {
        if (L == R) return newnode(nd, HLD::rnk[L]);
        int Mid = (L + R) / 2;
        if (pos <= Mid) Mdy(lc, L, Mid, pos);
        else Mdy(rc, Mid+1, R, pos);
        maintain(nd);
    }

    Node Qry(int nd, int L, int R, const int& opL, const int& opR) {
        if (opL <= L && R <= opR) return dat[nd];
        int Mid = (L + R) / 2;
        if (opR <= Mid) return Qry(lc, L, Mid, opL, opR);
        if (opL > Mid) return Qry(rc, Mid+1, R, opL, opR);
        return Qry(rc, Mid+1, R, opL, opR) * Qry(lc, L, Mid, opL, opR);
    }
#undef lc
#undef rc
}

int t1[MAXN], t2[MAXN];

namespace HLD {
    inline void Qry(int u) {
        Node res = SGT::Qry(1, 1, n, dfn[u], Ed[u]);
        for (int i = 0; i < m; ++i) t1[i] = res.C[i], t2[i] = res.D[i];
    }

    inline void Mdy(int u, int val) {
        V[u] = val;
        while (u > 0) {
            int fa = pre[topfa[u]];
            Qry(topfa[u]);
            if (fa) for (int i = 0; i < m; ++i)
                lf[fa][i] /= (t1[i] + 1) % P, lg[fa][i] = (lg[fa][i] - t2[i] + P) % P;
            SGT::Mdy(1, 1, n, dfn[u]);
            Qry(topfa[u]);
            if (fa) for (int i = 0; i < m; ++i)
                lf[fa][i] *= (t1[i] + 1) % P, lg[fa][i] = (lg[fa][i] + t2[i]) % P;
            u = fa;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    inv[1] = 1;
    for (int i = 2; i < P; ++i) inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
    // input
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(V[i]);
    for (int u, v, i = 1; i < n; ++i)
        read(u), read(v), Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    // solve
    for (int i = 0; i < m; ++i) E[i][i] = 1, FWT(E[i], m, 1);
    HLD::solve(), SGT::build(1, 1, n);
    // output
    read(q);
    while (q--) {
        static int opt, x, y;
        opt = Gc();
        while (isspace(opt)) opt = Gc();
        read(x);
        switch (opt) {
            case 'C': read(y), HLD::Mdy(x, y); break;
            case 'Q': HLD::Qry(1), FWT(t2, m, -1), printf("%d\n", t2[x]); break;
            default: fprintf(stderr, "ERR\n");
        }
    }
    return 0;
}

「SDOI2017」天才黑客

题目链接

https://loj.ac/problem/2270

解题思路

如果把边看作点, 容易得到这样一个做法:

枚举边, 假设当前枚举到的边为 $(a, b)$.
找到形如 $(b, c)$ 的边, 两者之间连边, 边权为两者 LCP, 也就是 Trie 树上 LCA 到根的距离.
跑 Dijkstra, 对于每个点 $u$, 找到形如 $(a, u)$ 的边更新答案.

但是这个算法有一个明显的问题, 遇到原图中点数度数很大的情况就会连很多边…

考虑如何优化这个过程.

对于 Trie 上一个节点 $u$, 将 $u$ 周围一圈节点按 DFS 序排序, 类似于后缀数组, 设 $h_i = \operatorname{LCP}(s_i, s_{i+1})$, 那么

$\operatorname{LCP}(s_L,\ s_R) = \min \{ h_j \mid L \le j \le R \}$

利用后缀数组中常见套路, 可以利用单调栈求出 LCP 为 $h_i$ 的一段区间, 然后点向区间连边, 区间向点连边即可. 利用线段树优化建图即可.

但是有更加简便的办法. 还是引用 Claris 的博客:

枚举每个 $h_i$ 作为分界线，那么新图中两侧的点均可以通过不超过 $h_i$ 的代价互相访问.

建立一排前缀虚点和后缀虚点然后对应前后缀之间连边即可.

具体地说, 前缀入点 prei 和前缀出点 preo 之间边权分别为 $0$, 每个 prei[i] 向 preo[i+1] 连边, 权值为 $h_i$.

这样连边就以较小的代价做了等效的事情. 后缀同理.

可能还是有些抽象, 不过在代码实现里还是很清晰的. 以及一些入点出点的细节也体现在代码里.

时间复杂度 $O(m \log m)$.

代码实现

你问我为什么执意写树剖求 LCA… 这… 我要是会倍增我不就写倍增了吗 = =

以及边拆为点时, 并不需要额外新增一条边记录初始边权, 直接视作点权在跑 Dijkstra 的过程中更新即可.

> 点击显示 / 隐藏

// LOJ #2270
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef pair<int, int> Pii;
const int MAXN = 5e4 + 5, MAXK = 2e4 + 5;
const int MAXV = MAXN * 10, MAXE = 1e6 + 5;

int n, m, K, uidx;
int U[MAXN], D[MAXN], Ans[MAXN];
vector<int> In[MAXN], Out[MAXN];

namespace Graph {
    struct Edge { int nxt, to, w; } edges[MAXE];
    int head[MAXV], eidx;
    int dist[MAXV], val[MAXV];

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to, int w) {
        edges[++eidx] = (Edge){ head[from], to, w }, head[from] = eidx;
    }

    void Dijkstra() {
        priority_queue<Pii, vector<Pii>, greater<Pii> > PQ;
        for (int i = 1; i <= uidx; ++i) dist[i] = INT_MAX;
        for (int i = 1; i <= m; ++i)
            if (U[i] == 1) PQ.push(Pii(dist[i] = val[i], i));
        while (!PQ.empty()) {
            int d = PQ.top().first, u = PQ.top().second; PQ.pop();
            if (d != dist[u]) continue;
            for (int i = head[u]; ~i; i = edges[i].nxt) {
                int v = edges[i].to;
                if (dist[v] > val[v] + dist[u] + edges[i].w)
                    PQ.push(Pii(dist[v] = val[v] + dist[u] + edges[i].w, v));
            }
        }
        for (int u = 2; u <= n; ++u) {
            Ans[u] = INT_MAX;
            for (size_t i = 0; i < In[u].size(); ++i)
                Ans[u] = min(Ans[u], Graph::dist[In[u][i]]);
        }
    }
}

namespace HLD {
    struct Edge { int nxt, to; } edges[MAXK];
    int head[MAXK], eidx;
    int depth[MAXK], pre[MAXK], son[MAXK], size[MAXK];
    int topfa[MAXK], dfn[MAXK], dfs_clock;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
    }

    void dfs1(int u, int fa) {
        depth[u] = depth[fa] + 1;
        son[u] = -1, size[u] = 1, pre[u] = fa;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            dfs1(v = edges[i].to, u), size[u] += size[v];
            if (son[u] == -1 || size[son[u]] < size[v]) son[u] = v;
        }
    }
    void dfs2(int u, int top) {
        topfa[u] = top, dfn[u] = ++dfs_clock;
        if (~son[u]) dfs2(son[u], top);
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            if ((v = edges[i].to) != son[u]) dfs2(v, v);
    }
    inline void solve(int rt = 1) {
        depth[0] = -1, dfs1(rt, 0), dfs2(rt, rt);
    }

    inline int LCA(int u, int v) {
        while (topfa[u] != topfa[v]) {
            if (depth[topfa[u]] < depth[topfa[v]]) swap(u, v);
            u = pre[topfa[u]];
        }
        return depth[u] > depth[v]? v: u;
    }

    inline int Abs(int x) { return x < 0? -x: x; }
    inline bool cmp(const int& x, const int& y) {
        return dfn[D[Abs(x)]] < dfn[D[Abs(y)]];
    }

    void build(int u) {
        static int preo[MAXN], prei[MAXN], sufi[MAXN], sufo[MAXN], q[MAXN];
        int nq = 0;
        for (size_t i = 0; i < In[u].size(); ++i) q[++nq] = In[u][i];
        for (size_t i = 0; i < Out[u].size(); ++i) q[++nq] = -Out[u][i];
        // 区分出入点和出点
        sort(q+1, q+1+nq, cmp);
        for (int i = 1; i <= nq; ++i) {
            preo[i] = ++uidx, prei[i] = ++uidx, sufo[i] = ++uidx, sufi[i] = ++uidx;
            if (i > 1) {
                Graph::AddEdge(preo[i-1], preo[i], 0), Graph::AddEdge(prei[i-1], prei[i], 0);
                Graph::AddEdge(sufo[i], sufo[i-1], 0), Graph::AddEdge(sufi[i], sufi[i-1], 0);
            }
            if (q[i] > 0)
                Graph::AddEdge(q[i], prei[i], 0), Graph::AddEdge(q[i], sufi[i], 0);
            else
                q[i] = -q[i], Graph::AddEdge(preo[i], q[i], 0), Graph::AddEdge(sufo[i], q[i], 0);
        }
        // 
        for (int i = 1; i < nq; ++i) {
            int lca = LCA(D[q[i]], D[q[i + 1]]);
            Graph::AddEdge(prei[i], preo[i + 1], depth[lca]);
            Graph::AddEdge(sufi[i + 1], sufo[i], depth[lca]);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti);
    while (Ti--) {
        // init
        Graph::init(), HLD::init();
        // input
        read(n), read(m), read(K); uidx = m;
        for (int v, i = 1; i <= m; ++i) {
            read(U[i]), read(v), read(Graph::val[i]), read(D[i]);
            In[v].push_back(i), Out[U[i]].push_back(i);
        }
        for (int u, v, w, i = 1; i < K; ++i)
            read(u), read(v), read(w), HLD::AddEdge(u, v);
        // solve
        HLD::solve();
        for (int i = 1; i <= n; ++i) HLD::build(i);
        Graph::Dijkstra();
        // output
        for (int i = 2; i <= n; ++i) printf("%d\n", Ans[i]);
        // clear
        for (int i = 1; i <= m; ++i) Graph::val[i] = 0;
        for (int i = 1; i <= n; ++i) In[i].clear(), Out[i].clear();
    }
    return 0;
}

「SDOI2017」遗忘的集合

题目链接

https://loj.ac/problem/2271

解题思路

如果把所求和已知交换, 那么这道题就是一道生成函数套路题了.

设序列 $a_i$ 表示元素 $i$ 是否存在于集合 $S$ 中. 那么取 $S$ 中元素之和的方案数的生成函数为

$F(x) = \prod_{i \in S} (\sum_{k=0}^{\infty} x^{ki}) = \prod_{i \in S} \frac{1}{1 - x^i} = \prod_{i=1}^n (\frac{1}{1 - x^i} ) ^ {a_i}$

看到乘积不爽. 两边同时取 $\ln$, 得

$- \ln F(x) = \sum_{i=1}^n a_i \ln (1-x^i)$

记 $g(x) = \ln (1-x^i)$, 那么对 $g(x)$ 求导得到

$\frac{(1 - x^i)'}{1 - x^i} = \frac{-i x^{i-1}}{1 - x^i} = g'(x)$

由广义二项式定理, 得

$-ix^{i-1} \sum_{k=0}^{\infty} x ^{ki} = -\sum_{k=0}^{\infty} i x^{ki +i-1} = g'(x)$

再积分, 得

$-\sum_{k=0} ^ {\infty} \frac{i}{ki + i} x^{ki + i} = -\sum_{k=1}^{\infty} \frac{1}{k} x ^ {ki} = g(x)$

所以我们就得到了

$g(x) = \ln (1 - x^i) = -\sum_{k=1}^{\infty} \frac{1}{k} x^{ki}$

代入原式, 可以得到

$\ln F(x) = \sum_{i=1}^n a_i \sum_{k=1}^{\infty} \frac{1}{k} x^{ki}$

设 $T = ki$, 并交换枚举顺序, 得

$\ln F(x) = \sum_{T=1}^\infty (\sum_{d \mid T} a_d \frac{d}{T} ) x^T$

至此, 这道题就做完了. 对给定的 $F(x)$ 求 $\ln$ 后莫比乌斯反演即可.

此处并不需要筛出来 $\mu$ 之后 $O(\sqrt n)$ 枚举约数… 直接利用 VFleaKing 反演课件里的技巧即可.

时间复杂度 $O(n\log n)$.

其实整个过程叫做 “Euler Transform”? 类似的技巧也在 Luogu P4389 付公主的背包用到过.

代码实现

先滚过去学了 MTT 才写了这道题 = =

> 点击显示 / 隐藏

// LOJ #2271
// DeP
#include <cmath>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 1 << 19, M = (1 << 15) - 1;
const double PI = acos(-1.0);

struct Complex {
    double x, y;
    Complex(double _x = 0.0, double _y = 0.0): x(_x), y(_y) { }
    Complex operator + (const Complex& rhs) const { return Complex(x + rhs.x, y + rhs.y); }
    Complex operator - (const Complex& rhs) const { return Complex(x - rhs.x, y - rhs.y); }
    Complex operator * (const Complex& rhs) const {
        return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
    }
};
inline Complex conj(const Complex& p) { return Complex(p.x, -p.y); }

int P;

int fpow(int base, int b, int m = P) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = 1LL * ret * base % m;
        base = 1LL * base * base % m, b >>= 1;
    }
    return ret % m;
}

namespace Poly {
    int r[MAXN];
    Complex W[MAXN];
    inline void init(const int& Lim, const int& L) {
        for (int i = 1; i < Lim; ++i) r[i] = (r[i>>1] >> 1) | ((i & 1) << (L-1));
        for (int i = 0; i < Lim; ++i) W[i] = Complex(cos(PI / Lim * i), sin(PI / Lim * i));
    }

    void FFT(Complex* f, const int& Lim) {
        for (int i = 1; i < Lim; ++i) if (i < r[i]) swap(f[i], f[r[i]]);
        for (int Mid = 1; Mid < Lim; Mid <<= 1)
            for (int i = 0; i < Lim; i += Mid << 1)
                for (int j = 0; j < Mid; ++j) {
                    Complex f0 = f[i+j], f1 = W[1LL * j * Lim / Mid] * f[i+j+Mid];
                    f[i+j] = f0 + f1, f[i+j+Mid] = f0 - f1;
                }
    }

    void MTT(const int* f, const int* g, int Lim, int* h) {
        static Complex A[MAXN], B[MAXN];
        static Complex dfta[MAXN], dftb[MAXN], dftc[MAXN], dftd[MAXN];
        for (int i = 0; i < Lim; ++i) A[i] = Complex(f[i] & M, f[i] >> 15);
        for (int i = 0; i < Lim; ++i) B[i] = Complex(g[i] & M, g[i] >> 15);
        FFT(A, Lim), FFT(B, Lim);
        for (int i = 0; i < Lim; ++i) {
            int j = (Lim - i) & (Lim - 1);
            static Complex da, db, dc, dd;
            da = (A[i] + conj(A[j])) * Complex(0.5, 0.0);
            db = (A[i] - conj(A[j])) * Complex(0.0, -0.5);
            dc = (B[i] + conj(B[j])) * Complex(0.5, 0.0);
            dd = (B[i] - conj(B[j])) * Complex(0.0, -0.5);
            dfta[j] = da * dc, dftb[j] = da * dd;
            dftc[j] = db * dc, dftd[j] = db * dd;
        }
        for (int i = 0; i < Lim; ++i) A[i] = dfta[i] + dftb[i] * Complex(0.0, 1.0);
        for (int i = 0; i < Lim; ++i) B[i] = dftc[i] + dftd[i] * Complex(0.0, 1.0);
        FFT(A, Lim), FFT(B, Lim);
        for (int i = 0; i < Lim; ++i) {
            int da = LL(A[i].x / Lim + 0.5) % P, db = LL(A[i].y / Lim + 0.5) % P;
            int dc = LL(B[i].x / Lim + 0.5) % P, dd = LL(B[i].y / Lim + 0.5) % P;
            h[i] = (da + (LL(db + dc) << 15) + (LL(dd) << 30)) % P;
        }
    }

    void Inv(int* f, int* g, int n) {
        static int A[MAXN], B[MAXN], ab[MAXN], abb[MAXN];
        g[0] = fpow(f[0], P-2);
        for (int L = 0, Lim = 1, Mid = 2; Mid < 2*n; Mid <<= 1) {
            while (Lim < 2*Mid) Lim <<= 1, ++L;
            init(Lim, L);
            for (int i = 0; i < Mid; ++i) A[i] = f[i], B[i] = g[i];
            for (int i = Mid; i < Lim; ++i) A[i] = B[i] = 0;
            MTT(A, B, Lim, ab), MTT(ab, B, Lim, abb);
            for (int i = 0; i < Lim; ++i)
                g[i] = ((B[i] + B[i]) % P - abb[i] + P) % P;
            for (int i = min(n, Mid); i < Lim; ++i) g[i] = 0;
        }
    }

    void Der(int* f, int* g, int n) {
        for (int i = 1; i < n; ++i) g[i-1] = 1LL * i * f[i] % P;
        g[n - 1] = 0;
    }
    void Int(int* f, int* g, int n) {
        g[0] = 0;
        for (int i = 1; i < n; ++i) g[i] = 1LL * fpow(i, P-2) * f[i-1] % P;
    }

    void Ln(int* f, int* g, int n) {
        static int df[MAXN], invf[MAXN];
        Der(f, df, n), Inv(f, invf, n);
        int Lim = 1, L = 0;
        while (Lim < 2*n) Lim <<= 1, ++L;
        init(Lim, L);
        for (int i = n; i < Lim; ++i) df[i] = invf[i] = 0;
        MTT(df, invf, Lim, invf), Int(invf, g, n);
    }
}

int n;
int Ans[MAXN], nA;
int f[MAXN], lnf[MAXN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(P), ++n;
    for (int i = 1; i < n; ++i) read(f[i]);
    // solve
    f[0] = 1;
    Poly::Ln(f, lnf, n);
    for (int i = 1; i < n; ++i) lnf[i] = 1LL * i * lnf[i] % P;
    for (int i = 1; i < n; ++i)
        for (int j = i + i; j < n; j += i) lnf[j] = (lnf[j] - lnf[i] + P) % P;
    for (int i = 1; i < n; ++i) if (lnf[i]) Ans[++nA] = i;
    // output
    printf("%d\n", nA);
    for (int i = 1; i <= nA; ++i) printf("%d%c", Ans[i], " \n"[i==nA]);
    return 0;
}

「SDOI2017」文本校正

题目链接

https://loj.ac/problem/2272

解题思路

一道毒瘤的字符串匹配题.

假设串 $T$ 被拆分为形如 ABC 的三段, 有一个大力匹配的思路, 即枚举 $3!$ 种情况, 依次判定即可.

ABC

直接用哈希判断两串是否相等即可…
CAB, BCA

以 CAB 为例, 注意到 AB 在 $T$ 中是连续的一段, 枚举 AB 和 C 的断点, 用哈希判断是否和 $S$ 中对应一段相等即可.

BCA 同理.
CBA

开始了.

我们先把 $T$ 倒过来再插入 $S$, 得到一个新串 $S_1 T_n S_2 T_{n-1} \cdots S_n T_1$, 那么 CBA 的判断就是在判断得到的新串是否可以被拆成 3 个偶回文串.

可以在新串上枚举一个拆分点, 现在的问题就是: 判断后缀是否构成一个双回文串.

有一个来自的结论

如果 $s = ab$, $a$, $b$ 都是回文串, 则称 $s$ 是一个双回文串.

如果 $s$ 是一个双回文串, 则存在一种拆分方法 $s = ab$, 使得 $a$ 是 $s$ 的最长回文前缀, 或者 $b$ 是 $s$ 的最长回文后缀.

所以可以用 Manacher 处理出
1. 当前拆分点向右延伸的最长回文串的结束位置, 也就是最长回文前缀, 代码中为 Rpos[i].
2. 能够到达新串结尾的回文中心集合, 也就是最长回文后缀, 打标记后丢到队列里.
假设当前枚举到的断点为 $i$, 若 $i$ 位置前是一个偶回文串, 依次用最长回文前缀和最长回文后缀判断 $i$ 位置后是否满足限制即可.
BAC, ACB

以 BAC 为例, 如果枚举 C 的位置, 利用上面的经验, 剩下的部分就是一个判断双回文串的问题…

但是有简单一些的办法.

回忆 Case 3 处理问题的过程, Manacher 其实在做一个最大匹配, 也就是说, 此处 BA 两串一定有一者是长度最大的, 利用 KMP 完成这个最大匹配即可. 剩下部分利用哈希判断就好了.

那么对于 ACB 的情况, 真的是字面意思上倒过来就可以了, 注意最后的答案, 先前的哈希值也要翻转. 当然再写一遍也是可以的, 有常数上的优势.

时间复杂度 $O(n)$.

考场上我当然是选择 $O(n^2)$ 的暴力匹配 = =.

代码实现

> 点击显示 / 隐藏

// LOJ #2272
// DeP
#include <cctype>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef pair<int, int> Pii;
const int MAXN = 1e6 + 5;

int n, m;
Pii Ans[3];
int S[MAXN], T[MAXN];

// 双模数 Hash ...
struct Hash {
    static const int P1 = 998244353, P2 = 1e9+7, B = 19260817;
    int H1, H2;

    Hash(int _H1 = 0, int _H2 = 0): H1(_H1), H2(_H2) { }
    inline void insert(const int& ch) {
        H1 = (1LL * H1 * B % P1 + ch) % P1, H2 = (1LL * H2 * B % P2 + ch) % P2;
    }

    Hash operator + (const Hash& rhs) const {
        return Hash((H1 + rhs.H1) % P1, (H2 + rhs.H2) % P2);
    }
    Hash operator - (const Hash& rhs) const {
        return Hash((H1 - rhs.H1 + P1) % P1, (H2 - rhs.H2 + P2) % P2);
    }
    Hash operator * (const Hash& rhs) const {
        return Hash(1LL * H1 * rhs.H1 % P1, 1LL * H2 * rhs.H2 % P2);
    }

    bool operator== (const Hash& rhs) const { return H1 == rhs.H1 && H2 == rhs.H2; }
    bool operator!= (const Hash& rhs) const { return !(*this == rhs); }
} A[MAXN], B[MAXN], powB[MAXN];
inline Hash Part(Hash* H, int L, int R) { return H[R] - H[L-1] * powB[R-L+1]; }

bool ABC() {
    if (A[n] != B[n]) return false;
    return Ans[0] = Pii(1, 1), Ans[1] = Pii(2, 2), Ans[2] = Pii(3, n), true;
}

bool CAB() {
    for (int i = 3; i <= n; ++i)
        if (Part(A, 1, n - i + 1) == Part(B, i, n)
                && Part(A, n - i + 2, n) == Part(B, 1, i - 1)) {
            Ans[0] = Pii(i, n), Ans[1] = Pii(1, 1), Ans[2] = Pii(2, i-1);
            return true;
        }
    return false;
}
bool BCA() {
    for (int i = 1; i <= n - 2; ++i)
        if (Part(A, 1, n - i) == Part(B, i + 1, n)
                && Part(A, n - i + 1, n) == Part(B, 1, i)) {
            Ans[0] = Pii(i + 1, i + 1), Ans[1] = Pii(i + 2, n), Ans[2] = Pii(1, i);
            return true;
        }
    return false;
}

int MaxR[MAXN << 2];

// 利用回文半径判断回文串
inline bool isP(const int& L, const int& R) {
    if (L > R) return false;
    int Mid = (L + R) / 2;
    return Mid - L + 1 <= MaxR[Mid];
}
// 判断双回文串, 其实只判定了长度...
inline bool isDP(const int& L, const int& R) {
    return L < R && (R - L) % 4 == 0;
}

bool CBA() {
    static int C[MAXN << 1], D[MAXN << 2], nD, nC;
    static int Rpos[MAXN << 1], Q[MAXN << 2], head, tail;
    static bool vis[MAXN << 2];
    // C tansform
    nD = nC = 0;
    for (int i = 1; i <= n; ++i) C[++nC] = S[i], C[++nC] = T[n - i + 1];
    // Manacher
    D[0] = -1;
    for (int i = 1; i <= nC; ++i) D[++nD] = C[i], D[++nD] = -1;
    for (int i = 0; i <= nD; i += 2) vis[i] = false, Rpos[i] = 0;
    int Mid = 0, mx = 0;
    for (int i = 0; i <= nD; ++i) {
        MaxR[i] = (i < mx)? min(MaxR[Mid * 2 - i], mx - i): 1;
        while (i >= MaxR[i] && D[i + MaxR[i]] == D[i - MaxR[i]]) ++MaxR[i];
        if (mx < i + MaxR[i]) mx = i + MaxR[i], Mid = i;
        Rpos[i - MaxR[i] + 1] = max(Rpos[i - MaxR[i] + 1], i + MaxR[i] - 1);
        if (i + MaxR[i] - 1 == nD) vis[i - MaxR[i] + 1] = true;
    }
    // Judge
    Q[head = 1] = tail = 0;
    for (int i = 2; i <= nD; i += 2) {
        // 注意此处的更新
        Rpos[i] = max(Rpos[i], Rpos[i - 2] - 2);
        if (vis[i]) Q[++tail] = i;
    }
    // i 是断点, 真的是断点, 换言之, D[i] = -1
    for (int i = 4; i <= nD; i += 4) if (isP(0, i)) {
        while (head <= tail && Q[head] < i) ++head;
        static int Algt, Clgt;
        bool flag = false;
        if (isDP(i, Rpos[i]) && isDP(Rpos[i], nD) && isP(Rpos[i], nD))
            flag = true, Algt = i / 4, Clgt = (nD - Rpos[i]) / 4;
        if (!flag && isDP(Q[head], nD) && isDP(i, Q[head]) && isP(i, Q[head]))
            flag = true, Algt = i / 4, Clgt = (nD - Q[head]) / 4;
        if (flag) {
            Ans[0] = Pii(n - Algt + 1, n);
            Ans[1] = Pii(Clgt + 1, n - Algt), Ans[2] = Pii(1, Clgt);
            return true;
        }
    }
    return false;
}

int Sfail[MAXN], Tfail[MAXN];

// KMP
inline void getFail(int* P, int* fail) {
    int j = fail[1] = 0;
    for (int i = 2; i <= n; ++i) {
        while (j && P[i] != P[j + 1]) j = fail[j];
        fail[i] = (j += P[i] == P[j + 1]);
    }
}

bool BAC() {
    int Climit = n + 1;
    // 注意要让 C 匹配上
    while (Climit > 1 && S[Climit - 1] == T[Climit - 1]) --Climit;
    int ptrS = 0, ptrT = 0;
    for (int i = 1; i <= n; ++i) {
        while (ptrS && S[ptrS+1] != T[i]) ptrS = Sfail[ptrS];
        if (S[ptrS + 1] == T[i]) ++ptrS;
        while (ptrT && T[ptrT+1] != S[i]) ptrT = Tfail[ptrT];
        if (T[ptrT + 1] == S[i]) ++ptrT;
        if (i + 1 < Climit) continue;
        if (Part(A, ptrS+1, i) == Part(B, 1, i - ptrS)) {
            Ans[0] = Pii(i - ptrS + 1, i);
            Ans[1] = Pii(1, i - ptrS), Ans[2] = Pii(i + 1, n);
            return true;
        }
        if (Part(A, 1, i - ptrT) == Part(B, ptrT + 1, i)) {
            Ans[0] = Pii(ptrT + 1, i);
            Ans[1] = Pii(1, ptrT), Ans[2] = Pii(i + 1, n);
            return true;
        }
    }
    return false;
}
bool ACB() {
    int Alimit = 0;
    while (Alimit < n && S[Alimit + 1] == T[Alimit + 1]) ++Alimit;
    int ptrS = n+1, ptrT = n+1;
    for (int i = n; i >= 1; --i) {
        while (ptrS != n+1 && S[ptrS-1] != T[i]) ptrS = n - Sfail[n-ptrS+1] + 1;
        if (S[ptrS - 1] == T[i]) --ptrS;
        while (ptrT != n+1 && T[ptrT-1] != S[i]) ptrT = n - Tfail[n-ptrT+1] + 1;
        if (T[ptrT - 1] == S[i]) --ptrT;
        if (i - 1 > Alimit) continue;
        if (Part(A, i, ptrS - 1) == Part(B, i + n - ptrS + 1, n)) {
            Ans[0] = Pii(1, i - 1), Ans[1] = Pii(i + n - ptrS + 1, n);
            Ans[2] = Pii(i, i + n - ptrS);
            return true;
        }
        if (Part(A, i + n - ptrT + 1, n) == Part(B, i, ptrT - 1)) {
            Ans[0] = Pii(1, i - 1), Ans[1] = Pii(ptrT, n);
            Ans[2] = Pii(i, ptrT - 1);
            return true;
        }
    }
    return false;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti);
    // init
    powB[0] = Hash(1, 1);
    for (int i = 1; i < MAXN; ++i) powB[i] = powB[i-1] * Hash(Hash::B, Hash::B);
    while (Ti--) {
        // input
        read(n), read(m);
        for (int i = 1; i <= n; ++i) read(S[i]);
        for (int i = 1; i <= n; ++i) read(T[i]);
        // solve & output
        getFail(S, Sfail), getFail(T, Tfail);
        for (int i = 1; i <= n; ++i)
            A[i] = A[i-1], A[i].insert(S[i]), B[i] = B[i-1], B[i].insert(T[i]);
        if (ABC() || CAB() || BCA() || CBA() || BAC() || ACB()) {
            puts("YES");
            for (int i = 0; i < 3; ++i) printf("%d %d\n", Ans[i].first, Ans[i].second);
        } else puts("NO");
    }
    return 0;
}

后记

本来想简单地写写, 后来发现自己言简意赅的能力不足 = =

以后尽量少写一点废话吧.

DepletedPrism's Blog

SDOI 2017 Round 2 大赏

「SDOI2017」龙与地下城

题目链接

解题思路

代码实现

「SDOI2017」苹果树

题目链接

解题思路

代码实现

「SDOI2017」切树游戏

题目链接

解题思路

代码实现

「SDOI2017」天才黑客

题目链接

解题思路

代码实现

「SDOI2017」遗忘的集合

题目链接

解题思路

代码实现

「SDOI2017」文本校正

题目链接

解题思路

代码实现

后记