HNOI 2019 大赏

2020-03-18

AH 跑去十二省联考了 (

HNOI 独自毒瘤.

「HNOI2019」鱼

题目链接

https://loj.ac/problem/3054

解题思路

考虑枚举点 $D$, 将其他点按照极角排序, 在排序后得到的结果中枚举点 $A$.

先处理鱼头部分. 显然有 $AD$ 垂直平分 $BC$, 可以通过二分找到中点在 $AD$ 上, 且垂直于 $AD$ 的线段的范围. 将所有点两两连线, 记录得到的向量及中点, 并排序, 可以保证排序后, 满足以上条件的线段是连续的.

再考虑鱼尾部分. 现在已经确定了 $AD$ 位置, 因为有 $DE = DF$, 以及 $\angle ADE, \angle ADF$ 的限制, 用 map 记录到点 $D$ 为某一长度的线段出现次数, 并用 Two-Points 的技巧维护合法鱼尾的方案数即可.

此时将鱼头鱼尾的方案数相乘即可. 因为翻转后视为不同的鱼, 最后统计答案需 $\times 4$.

实际代码中并没有用到 double 之类的东西… 判断两向量位置关系用叉积和点积就好了 (

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

代码实现

在极角序和平面序的浑水里折腾.cpp

> 点击显示 / 隐藏

// LOJ #3054
// DeP
#include <map>
#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 = 1e3 + 5;

LL gcd(LL a, LL b) { return !b? a: gcd(b, a % b); }

namespace Geo {
    struct Vector {
        LL x, y;
        Vector(LL _x = 0, LL _y = 0): x(_x), y(_y) { }
        Vector operator + (const Vector& rhs) const { return Vector(x + rhs.x, y + rhs.y); }
        Vector operator - (const Vector& rhs) const { return Vector(x - rhs.x, y - rhs.y); }
        Vector operator * (const LL& p) const { return Vector(p * x, p * y); }
    };
    typedef Vector Point;

    bool operator < (const Point& A, const Point& B) {
        return A.x < B.x || (A.x == B.x && A.y < B.y);
    }

    inline LL Dot(const Vector& A, const Vector& B) { return A.x * B.x + A.y * B.y; }
    inline LL Cross(const Vector& A, const Vector& B) { return A.x * B.y - A.y * B.x; }

    inline LL Length2(const Vector& A) { return Dot(A, A); }

    inline Vector Normal(Vector A) {
        LL g = gcd(A.x, A.y);
        A.x /= g, A.y /= g;
        if (A.x < 0 || (A.x == 0 && A.y < 0)) A.x = -A.x, A.y = -A.y;
        return A;
    }

    struct Line {
        Point p; Vector v;
        Line() { p = v = Point(); }
        Line(Point _p, Vector _v): p(_p), v(_v) { }
        bool operator < (const Line& rhs) const {
            if (v < rhs.v || rhs.v < v) return v < rhs.v;
            if (Dot(v, p) != Dot(rhs.v, rhs.p)) return Dot(v, p) < Dot(rhs.v, rhs.p);
            return p < rhs.p;
        }
    };
}
using namespace Geo;

inline int where(const Vector& A) { return A.y > 0 || (A.y == 0 && A.x < 0); }
inline bool cmp(const Vector& A, const Vector& B) {
    return where(A) < where(B) || (where(A) == where(B) && Cross(A, B) > 0);
}

int n, nL, nA;
Point P[MAXN], A[MAXN << 1];
Line Li[MAXN * MAXN / 2];
map<LL, int> M;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n);
    for (int i = 1; i <= n; ++i) read(P[i].x), read(P[i].y);
    // solve
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            Li[++nL] = Line(P[i] + P[j], Normal(P[i] - P[j]));
    sort(Li+1, Li+1+nL);
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        nA = 0;
        for (int j = 1; j <= n; ++j) if (i != j) A[++nA] = P[j] - P[i];
        sort(A+1, A+1+nA, cmp);
        for (int j = 1; j <= nA; ++j) A[nA + j] = A[j];
        M.clear();
        int s = 0, L = 1, R = 1;
        for (int j = 1; j <= nA; ++j) {
            // [L, R)
            while (Cross(A[j], A[R]) > 0 || (R <= nA && Cross(A[j], A[R]) == 0) || Dot(A[j], A[R]) < 0)
                s += M[Length2(A[R++])]++;
            while (L < R && Dot(A[j], A[L]) >= 0) s -= --M[Length2(A[L++])];
            if (s == 0) continue;
            Point v = Normal(Point(A[j].y, -A[j].x)), lp = P[i] * 2, rp = (P[i] + A[j]) * 2;
            if (rp < lp) swap(lp, rp);
            int d = lower_bound(Li+1, Li+1+nL, Line(rp, v)) - upper_bound(Li+1, Li+1+nL, Line(lp, v));
            ans += 4LL * d * s;
        }
    }
    // output
    printf("%lld\n", ans);
    return 0;
}

「HNOI2019」JOJO

题目链接

https://loj.ac/problem/3055

解题思路

~~还是 dsidsi 的题解好啊.~~

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

代码实现

> 点击显示 / 隐藏

// LOJ #3055
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
#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; using IO::Gc;

const int MAXN = 1e5 + 5, M = 1e4 + 5, SIGMA = 26;
const int P = 998244353;

inline int s1(int p) { return 1LL * p * (p + 1) / 2 % P; }

int n, uidx, top;
int Ans[MAXN], pos[MAXN], val[MAXN];
int rt[MAXN][SIGMA], mx[MAXN][SIGMA];

vector<int> G[MAXN];

namespace PSGT {
    struct Node { int lc, rc, s, t, f; } dat[MAXN << 6];
    int nidx;

    inline void init() {
        nidx = 0;
        memset(rt[1], 0, sizeof rt[1]);
        memset(mx[1], 0, sizeof mx[1]);
    }
    inline void newnode(int& nd) { dat[++nidx] = dat[nd], nd = nidx; }

    inline void maintain(int nd) {
        dat[nd].s = (dat[dat[nd].lc].s + dat[dat[nd].rc].s) % P;
    }

    inline void pushset(int nd, int L, int R, int v) {
        dat[nd].s = 1LL * v * (R - L + 1) % P, dat[nd].t = v;
    }
    inline void pushdown(int nd, int L, int R) {
        if (!dat[nd].t) return;
        int &lc = dat[nd].lc, &rc = dat[nd].rc, Mid = (L + R) / 2;
        newnode(lc), pushset(lc, L, Mid, dat[nd].t);
        newnode(rc), pushset(rc, Mid+1, R, dat[nd].t);
        dat[nd].t = 0;
    }

    // [1, p]: 前缀赋值, 前缀求和

    void Mdy(int& nd, int L, int R, const int& p, const int& v, const int& f) {
        newnode(nd);
        if (R < p) return pushset(nd, L, R, v);
        if (L == R) return dat[nd].f = f, pushset(nd, L, R, v);
        pushdown(nd, L, R);
        int Mid = (L + R) / 2;
        Mdy(dat[nd].lc, L, Mid, p, v, f);
        if (p > Mid) Mdy(dat[nd].rc, Mid+1, R, p, v, f);
        maintain(nd);
    }

    void Qry(int nd, int L, int R, const int& p, int& s, int& fail) {
        if (R < p) return void( s = (s + dat[nd].s) % P );
        if (L == R) return s = (s + dat[nd].s) % P, void( fail = dat[nd].f );
        pushdown(nd, L, R);
        int Mid = (L + R) / 2;
        Qry(dat[nd].lc, L, Mid, p, s, fail);
        if (p > Mid) Qry(dat[nd].rc, Mid+1, R, p, s, fail);
    }
}

void dfs(int u) {
    static int A[MAXN], B[MAXN];
    // 维护根节点到 u 的一条链, A[i] 记录链上颜色, B[i] 记录链长度
    ++top;
    int x = val[u] % M, c = val[u] / M, fail = 0;
    A[top] = c, B[top] = B[top - 1] + x;
    if (top == 1) Ans[u] = s1(x - 1);
    else {
        Ans[u] = (Ans[u] + s1(min(mx[top][c], x))) % P;
        PSGT::Qry(rt[top][c], 1, M, x, Ans[u], fail);
        // 特判前缀第一段字符同末尾相同的情况
        if (!fail && A[1] == c && B[1] < x)
            fail = 1, Ans[u] = (Ans[u] + 1LL * B[1] * max(0, x - mx[top][c]) % P) % P;
    }
    mx[top][c] = max(mx[top][c], x);
    PSGT::Mdy(rt[top][c], 1, M, x, B[top - 1], top);
    for (auto v: G[u]) {
        memcpy(rt[top + 1], rt[fail + 1], sizeof rt[top + 1]);
        memcpy(mx[top + 1], mx[fail + 1], sizeof mx[top + 1]);
        Ans[v] = Ans[u], dfs(v);
    }
    --top;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n);
    for (int i = 1; i <= n; ++i) {
        static int opt, x, c;
        read(opt), read(x);
        switch (opt) {
            case 1:
                c = Gc();
                while (isspace(c)) c = Gc();
                val[++uidx] = (c - 'a') * M + x;
                G[pos[i - 1]].push_back(pos[i] = uidx);
                break;
            case 2: pos[i] = pos[x]; break;
            default: fprintf(stderr, "ERR\n");
        }
    }
    // solve
    for (auto v: G[0]) PSGT::init(), dfs(v);
    // output
    for (int i = 1; i <= n; ++i) printf("%d\n", Ans[pos[i]]);
    return 0;
}

「HNOI2019」多边形

题目链接

https://loj.ac/problem/3056

解题思路

通过手玩可以发现, 最终状态一定是多边形内所有的边都连向顶点 $n$. 如果要保证旋转次数最小, 那么每次操作都要使不连向顶点 $n$ 的边, 连向顶点 $n$.

记 $s$ 为 $S_0$ 中同 $n$ 直接相连的边数, 最小旋转次数即为 $n - 3 - s$. 接下来的问题就是求解方案数了.

按照顶点 $n$ 出发的边将多边形分成多个部分, 那么各部分之间互不影响.

单独考虑每个部分. 设当前操作的部分, 边界处顶点为 $[L, R]$, 如果要保证旋转次数最小, 那么第一次旋转操作一定选择顶点 $R$ 出边中最靠近 $L$ 的可行边旋转. 设当前选择边为 $(R, k)$, 此后该部分被分成两块: $[L, k]$, $[k, R]$.

此时就可以建立出二叉树的模型. 方案数可以通过子树大小和树上结构计算.

考虑子树间的转移, 也就是取出根节点后, 其余节点按照子树内部顺序考虑. 记左儿子为 $lc$, 右儿子为 $rc$, 根据乘法原理, 方案数乘上

$\binom{\mathrm{size}(lc) + \mathrm{size}(rc)}{\mathrm{size}(lc)} \cdot \binom{\mathrm{size}(lc) + \mathrm{size}(rc)}{\mathrm{size}(rc)} = \dfrac{(\mathrm{size}(lc) + \mathrm{size}(rc))!}{\mathrm{size}(lc)! \cdot \mathrm{size}(rc)!}$

即可. 根节点之间的情况则类似.

此时的转移, 化简之后可以得到相当简洁的结果. 参见: zhouyuheng2003 的博客.

但是原来的式子就很够用了, 只有代码长度与常数的区别.

接下来考虑做一次旋转对答案的影响.

在二叉树上考虑. 如果强制旋转一条边, 那么二叉树结构的改变类似于平衡树的旋转操作.

~~此处有张图会非常好理解, 但是这位退役选手却非常鸽子 (~~

图例就参考 https://www.cnblogs.com/xzz_233/p/10672208.html 好了 (

去掉原有贡献, 并计算新增贡献即可.

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

代码实现

采用了代码较为冗长的写法…

> 点击显示 / 隐藏

// LOJ #3056
// DeP
#include <map>
#include <cctype>
#include <cstdio>
#include <vector>
#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 = 1e5 + 5, P = 1e9 + 7;

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

int fac[MAXN << 1], ifac[MAXN << 1];

inline int calc(int n, int m) { return 1LL * fac[n + m] * ifac[n] % P * ifac[m] % P; }
inline int invc(int n, int m) { return 1LL * ifac[n + m] * fac[n] % P * fac[m] % P; }

int n, m, W;
map<Pii, int> M;
vector<int> G[MAXN];
int rt[MAXN], ch[2][MAXN], pre[MAXN], size[MAXN], nidx;

void dfs(int& u, int fa, int L, int R, int& p2) {
    if (L + 1 >= R) return;
    M[Pii(L, R)] = u = ++nidx;
    size[u] = 1, pre[u] = fa;
    int k = *lower_bound(G[R].begin(), G[R].end(), L + 1);
    dfs(ch[0][u], u, L, k, p2), dfs(ch[1][u], u, k, R, p2);
    size[u] += size[ch[0][u]] + size[ch[1][u]];
    p2 = 1LL * p2 * calc(size[ch[0][u]], size[ch[1][u]]) % P;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(W), read(n);
    for (int u, v, i = 1; i <= n-3; ++i)
        read(u), read(v), G[u].push_back(v), G[v].push_back(u);
    // init factorial
    int N = n << 1;
    ifac[0] = fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = 1LL * i * fac[i-1] % P;
    ifac[N] = fpow(fac[N], P-2);
    for (int i = N; i; --i) ifac[i-1] = 1LL * i * ifac[i] % P;
    // build polygon
    for (int i = 1; i <= n; ++i) {
        if (i < n) G[i].push_back(i + 1);
        if (i > 1) G[i].push_back(i - 1);
    }
    G[1].push_back(n), G[n].push_back(1);
    for (int i = 1; i <= n; ++i) sort(G[i].begin(), G[i].end());
    // calculate
    int p1 = (n-3) - (G[n].size() - 2), p2 = 1, s = 0;
    for (size_t i = 0; i + 1 < G[n].size(); ++i) {
        dfs(rt[i], 0, G[n][i], G[n][i + 1], p2);
        p2 = 1LL * p2 * calc(s, size[rt[i]]) % P, s += size[rt[i]];
    }
    if (W) printf("%d %d\n", p1, p2); else printf("%d\n", p1);
    // solve & output
    read(m);
    for (int L, R, i = 1; i <= m; ++i) {
        read(L), read(R);
        int n1 = p1, n2 = p2, u = M[Pii(L, R)];
        if (pre[u]) {
            int fa = pre[u], w = ch[1][fa] == u;
            n2 = 1LL * n2 * invc(size[ch[0][u]], size[ch[1][u]]) % P;
            n2 = 1LL * n2 * invc(size[ch[0][fa]], size[ch[1][fa]]) % P;
            n2 = 1LL * n2 * calc(size[ch[w^1][fa]], size[ch[w^1][u]]) % P;
            n2 = 1LL * n2 * calc(size[fa] - size[u] + size[ch[w^1][u]], size[ch[w][u]]) % P;
        } else {
            --n1;
            n2 = 1LL * n2 * invc(size[ch[0][u]], size[ch[1][u]]) % P;
            n2 = 1LL * n2 * invc(s - size[u], size[u]) % P;
            n2 = 1LL * n2 * calc(s - size[u], size[ch[0][u]]) % P;
            n2 = 1LL * n2 * calc(s - size[u] + size[ch[0][u]], size[ch[1][u]]) % P;
        }
        if (W) printf("%d %d\n", n1, n2); else printf("%d\n", n1);
    }
    return 0;
}

「HNOI2019」校园旅行

myy 的题感觉很有意思… 就是做不出来 (

题目链接

https://loj.ac/problem/3057

解题思路

先祭上官方题解: https://matthew99.blog.uoj.ac/blog/4968

首先有一个朴素的 DP.

设 $f(i, j)$ 表示节点 $i$ 到 $j$ 是否存在一条路径, 使得标记形成回文串.

将所有在给定条件下能形成回文串的点对丢到队列中, 枚举边更新 $f$ 即可. 注意到单独一个点也是合法的情况. 此时的时间复杂度为 $O(m^2)$.

考虑到边数较多, 而点数较少. 可以将连通块内连边情况进行一些改造, 以降低时间复杂度.

先只考虑连接两相同标记的边, 对于此时的一个连通块, 如果

为二分图, 那么保留连通块的任意一个生成树即可.

因为不限制为简单路径, 因此可以在连通块内一条边上反复横跳, 此时得到的标记串长度可以改变, 而奇偶性并不改变. 因此保留生成树即可.
不为二分图, 此时保留任意一个生成树, 并选择任意一个节点增加一个自环.

此时存在奇环, 标记串长度和奇偶性都可以任意改变, 增加一个自环就好了.

对于连接两不同标记的边, 直接按标记分类即可得到一个二分图, 因此保留任意一个生成树.

转化后边数不超过 $2n - 2$, 且不会影响到原来 DP 的转移, 用原来的 DP 就好了.

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

代码实现

> 点击显示 / 隐藏

// LOJ #3057
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
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 = 5e3 + 5, MAXM = 5e5 + 5;

inline int Abs(const int& x) { return x < 0? -x: x; }

int n, m, q;
char S[MAXN];
int C[MAXN], U[MAXM], V[MAXM];

queue<Pii> Q;
bool f[MAXN][MAXN], Odd[MAXN], vis[MAXN];

namespace DSU {
    int fa[2][MAXN];

    inline void init() {
        for (int i = 1; i <= n; ++i) fa[0][i] = fa[1][i] = i;
    }

    int findfa(const int& idx, int u) {
        return fa[idx][u] == u? u: fa[idx][u] = findfa(idx, fa[idx][u]);
    }
}

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXM << 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;
    }

    void BFS() {
        while (!Q.empty()) {
            int u = Q.front().first, v = Q.front().second; Q.pop();
            for (int iu = head[u]; ~iu; iu = edges[iu].nxt) {
                int vu = edges[iu].to;
                for (int vv, iv = head[v]; ~iv; iv = edges[iv].nxt)
                    if (S[vu] == S[vv = edges[iv].to] && !f[vu][vv])
                        f[vu][vv] = f[vv][vu] = true, Q.push(Pii(vu, vv));
            }
        }
    }

    void dfs(int u, int c) {
        C[u] = c;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if (!C[v = edges[i].to]) dfs(v, -c);
            else if (C[v] == c) Odd[Abs(c)] = true;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    // freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    scanf("%d%d%d%s", &n, &m, &q, S+1);
    for (int u, v, i = 1; i <= m; ++i) {
        read(u), read(v), U[i] = u, V[i] = v;
        if (S[u] == S[v]) Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    }
    // solve
    for (int i = 1; i <= n; ++i) if (!C[i]) Graph::dfs(i, i);
    Graph::init(), DSU::init();
    for (int i = 1; i <= m; ++i) {
        const int &u = U[i], &v = V[i];
        if (S[u] != S[v]) {
            int fu = DSU::findfa(1, u), fv = DSU::findfa(1, v);
            if (fu == fv) continue;
            DSU::fa[1][fv] = fu;
            Graph::AddEdge(u, v), Graph::AddEdge(v, u);
        } else {
            int fu = DSU::findfa(0, u), fv = DSU::findfa(0, v);
            if (fu == fv) continue;
            DSU::fa[0][fv] = fu;
            Graph::AddEdge(u, v), Graph::AddEdge(v, u);
            Q.push(Pii(u, v)), f[u][v] = f[v][u] = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        int c = Abs(C[i]);
        Q.push(Pii(i, i)), f[i][i] = true;
        if (Odd[c] && !vis[c]) Graph::AddEdge(i, i), vis[c] = true;
    }
    Graph::BFS();
    // output
    while (q--) {
        static int x, y;
        read(x), read(y), puts(f[x][y]? "YES": "NO");
    }
    return 0;
}

「HNOI2019」白兔之舞

强制类型转换而 “溢出” 不会被 -fsanitize=undefined 警告, -Wconversion 报平安.

题目链接

https://loj.ac/problem/3058

前置知识

单位根反演

~~之前看 VFleaKing 课件还以为这个东西没考过 (~~

给定两个长度为 $n$ 的序列 $a_0, a_1, \ldots, a_{n-1}$, $b_0, b_1, \ldots, b_{n-1}$, 求序列 $c$ 满足
$c_r = \sum_{p,\ q} [(p + q) \bmod n = r] a_p b_q$
由单位根反演, 可得
$c_r = \sum_{p,\ q} (\frac{1}{n} \sum_{k = 0} ^ {n-1} \omega_{n}^{-rk} \omega_{n}^{pk} \omega_{n}^{qk} )\ a_p b_q = \frac{1}{n} \sum_{k = 0}^{n-1} \omega_{n}^{-rk} \sum_{p} \omega_{n}^{pk} a_p \sum_{q} \omega_{n}^{qk} b_q$
具体证明参见课件好了…

解题思路

将题目中 “有向图” 看作二维平面, 并称第一维为行, 第二维为列. 那么共有 $L+1$ 行, 以及 $n$ 列.

考虑朴素 DP. 设 $f(i, j)$ 表示共走 $i$ 步, 到达第 $j$ 行任意位置的方案数. $g(i, j)$ 表示共走 $i$ 步, 达到第 $j$ 行的方案数. 那么有

$f(i, j) = \binom{L}{i} g(i, j)$ $g(i, j) = \sum_{k = 1} ^ n g(i-1, k) \cdot w(k, j)$

显然 $g$ 的转移可以用矩阵快速幂优化. 记初始矩阵为 $G_0$, 转移矩阵为 $S$. 设所求答案为 $A_t$, 那么

$A_t = \sum_{i = 1} ^ L [i \bmod k = t]\ f(i, y)$

由单位根反演, 得

$A_t = \sum_{i = 1} ^ L \frac{1}{k} \sum_{j = 0} ^ {k-1} \omega_{k}^{-tj} \omega_{k}^{ij}\ f(i, y)$

简单整理, 得

$A_t = \frac{1}{k} \sum_{j = 0}^{k-1} \omega_{k}^{-tj} \sum_{i = 1} ^ L \omega_{k}^{ij} \binom{L}{i} g(i, j) \\\\ A_t = \frac{1}{k} \sum_{j = 0}^{k-1} \omega_{k}^{-tj} \sum_{i = 1} ^ L \binom{L}{i} \omega_{k}^{ij} G_0 S^i$

根据二项式定理, 并设矩阵 $B_t$ 的第 $y$ 项为 $A_t$, 可知

$B_t = \frac{1}{k} \sum_{i = 0}^{k-1} \omega_{k}^{-ti} G_0 (\omega_{k}^{i} S + I)^L$

设 $h_i$ 为 $G_0 (\omega_{k}^{i} + I) ^ L$ 的第 $y$ 项. 那么

$A_t = \frac{1}{k} \sum_{i = 0} ^ {k-1} \omega_{k}^{-ti} h_i$

考虑 $\omega_{k}^{ti}$ 如何处理. 此处可以构造

$ti = \binom{t + i}{2} - \binom{t}{2} - \binom{i}{2}$

容易发现这是对的. 此外还有

$ti = \frac{1}{2} (t + i) ^ 2 - \frac{1}{2}\ t ^ 2 - \frac{1}{2}\ i ^ 2$

不过在此题中并不适用. ~~想一想, 为什么.~~

那么答案可写作

$A_t = \frac{1}{k} \omega_{k}^{\binom{t}{2}} \sum_{i = 0} ^ {k-1} \omega_{k}^{\binom{i}{2}} h_i \cdot \omega_{k}^{-\binom{t+i}{2}}$

模意义下单位根用原根就好了, 翻转即可凑出来卷积…

使用 MTT, 时间复杂度 $O(n \log n)$.

代码实现

> 点击显示 / 隐藏

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

typedef long long LL;
const int MAXN = 1 << 18 | 1, MAXM = 4, MAXL = 64, MAXK = 7e4 + 5;
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(int* f, 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] & 32767, f[i] >> 15);
        for (int i = 0; i < Lim; ++i) B[i] = Complex(g[i] & 32767, g[i] >> 15);
        FFT(A, Lim), FFT(B, Lim);
        for (int i = 0; i < Lim; ++i) {
            static Complex da, db, dc, dd;
            int j = (Lim - i) & (Lim - 1);
            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 Mul(int* f, int n, int* g, int m, int* h) {
        int Lim = 1, L = 0;
        while (Lim <= n + m) Lim <<= 1, ++L;
        init(Lim, L), MTT(f, g, Lim, h);
    }
}

int proot(int p) {
    static int fact[MAXL];
    int phi = p - 1, tot = 0;
    for (int d = 2; d*d <= phi; ++d) if (phi % d == 0) {
        fact[++tot] = d;
        while (phi % d == 0) phi /= d;
    }
    if (phi > 1) fact[++tot] = phi;
    phi = p - 1;
    for (int i = 2; i <= phi; ++i) {
        bool flag = true;
        for (int j = 1; j <= tot && flag; ++j)
            if (fpow(i, phi / fact[j], p) == 1) flag = false;
        if (flag) return i;
    }
    return -1;
}

// 返回 long long --- 引用部分就是在说这个 (
inline LL C2(int n) { return 1LL * n * (n-1) / 2; }

int n, K, L, x, y;
int W[MAXM][MAXM], powG[MAXK];
int f[MAXN], g[MAXN], h[MAXN];

struct Matrix {
    int m[MAXM][MAXM];
    Matrix() { memset(m, 0, sizeof m); }
    Matrix operator * (const Matrix& rhs) const {
        Matrix ret;
        for (int i = 1; i <= n; ++i)
            for (int k = 1; k <= n; ++k)
                for (int j = 1; j <= n; ++j)
                    ret.m[i][j] = (ret.m[i][j] + 1LL * m[i][k] * rhs.m[k][j] % P) % P;
        return ret;
    }
};

Matrix fpow(Matrix base, int b) {
    Matrix ret;
    for (int i = 1; i <= n; ++i) ret.m[i][i] = 1;
    while (b > 0) {
        if (b & 1) ret = ret * base;
        base = base * base, b >>= 1;
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d%d%d%d%d", &n, &K, &L, &x, &y, &P);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) scanf("%d", W[i] + j);
    // solve
    int G = fpow(proot(P), (P - 1) / K);
    powG[0] = 1;
    for (int i = 1; i < K; ++i) powG[i] = 1LL * powG[i-1] * G % P;
    Matrix base, G0;
    G0.m[1][x] = 1;
    for (int i = 0; i < K; ++i) {
        for (int a = 1; a <= n; ++a) {
            for (int b = 1; b <= n; ++b) base.m[a][b] = 1LL * W[a][b] * powG[i] % P;
            base.m[a][a] = (base.m[a][a] + 1) % P;
        }
        base = G0 * fpow(base, L);
        f[i] = 1LL * base.m[1][y] * powG[C2(i) % K] % P;
    }
    for (int i = 0; i <= 2*K; ++i) g[i] = powG[(K - C2(i) % K) % K];
    reverse(g, g + 2*K + 1);
    Poly::Mul(f, K, g, 2*K + 1, h);
    // output
    int invK = fpow(K, P-2);
    for (int t = 0; t < K; ++t) {
        LL s1 = 1LL * invK * powG[C2(t) % K] % P;
        printf("%lld\n", s1 * h[2*K - t] % P);
    }
    return 0;
}

「HNOI2019」序列

题目链接

https://loj.ac/problem/3059

解题思路

类似于 BZOJ 1367, 可得到这样的思路:

将 $A$ 分段, 对每一段 $[L, R]$ 构造相同的序列 $B_i$, 并令 $B_i$ 为该段 $A_i$ 的平均值. 在满足 $B$ 单调不降的条件下使每次分出区间长度尽量小, 此时可以得到最优结果.

~~个人感觉证明方法应该类似于黄源河 <左偏树的特点及其应用> 例题部分对 BZOJ 1367 的证明~~.

证明参见 https://www.cnblogs.com/Paul-Guderian/p/10801584.html 好了.

$A$ 的分段情况可以利用单调栈维护.

具体地说, 每个单调栈中元素对应 $A$ 中一段区间. 假设单调栈内某一元素对应 $A_i$ 中区间 $[L, R]$, 记该段平均值为 $\bar x$, 那么区间内的答案为

$\sum_{i = L}^ R (A_i - \bar x) ^ 2 = \sum_{i = L}^R A_i^2 - \frac{1}{R - L + 1} (\sum_{i = L}^R A_i) ^ 2$

此时记录区间和, 区间平方和, 区间大小就可以快速合并两个区间的信息, 也就是单调栈内两元素的值.

从前往后扫描 $A$, 假设当前扫描到位置 $i$, 那么在单调栈中加入 $i$. 此时不断检查栈中元素. 如果不满足 $B$ 单调不降, 则不断向栈内元素合并. 同时记录在每个位置得到的答案.

此时得到了 $m = 0$ 情况下的做法.

注意到每次都是单点修改, 考虑单点修改对单调栈中元素的影响. 设当前修改位置为 $x$, 那么在修改后重新计算得到单调栈中一定存在一个区间满足 $L \le x \le R$.

重构单调栈的复杂度过高, 如果确定了 $L$, $R$ 的位置, 那么除去这一部分, 其他部分并不会改变. 因此仿照从前到后维护单调栈的过程, 从后往前扫描 $A$, 这样配合可持久化就能快速得到 $[1, L)$ 以及 $(R, n]$ 的信息.

现在的问题就是如何确定 $L, R$ 的位置. 根据单调性, $L, R$ 的位置可以通过二分来确定.

具体地说, 在维护单调栈的过程中, 利用可持久化线段树维护单调栈中每个元素在序列上的实际范围. 线段树向上合并时维护该节点对应实际范围 $[L, R]$, 以及最靠左元素对应的右端点位置 $k$.

不断二分 $x$ 修改后影响到的单调栈编号 $p$, 每次在线段树上查询到该编号对应的右端点位置 $R$. 可以证明, 改变 $x$ 位置的值后, 确定的 $L$, $R$ 位置仍是原有单调栈中某个元素的左右端点之一, 否则答案一定不优.

另外需保证选择的区间长度尽量小, 因此 $R$ 的位置很好确定, 直接找到编号 $p$ 对应的右端点位置. 根据 $R$ 的位置, 并利用 $B$ 单调不降的限制, 可以确定出左端点 $L$ 的位置, 并在查询 $L$ 位置的同时维护 $[L, R]$ 这一段合并后得到的元素. 如果该元素小于后一位置单调栈中元素, 那么编号 $p$ 合法, 减小区间长度继续二分.

~~似乎也可以通过二分套二分实现这个过程 ?~~

时间复杂度 $O(n \log n + m \log ^ 2 n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3059
// DeP
#include <cctype>
#include <cstdio>

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 = 1e5 + 5, P = 998244353;

int inv[MAXN];

struct Data {
    int s0; LL s1; int s2;
    Data() { s1 = s0 = s2 = 0; }
    Data(int _s0, LL _s1, int _s2): s0(_s0), s1(_s1), s2(_s2) { }
    bool operator < (const Data& rhs) const {
        return s1 * rhs.s0 < rhs.s1 * s0;
    }
    bool operator <= (const Data& rhs) const { return !(rhs < *this); }
    Data operator + (const Data& rhs) const {
        return Data(s0 + rhs.s0, s1 + rhs.s1, (s2 + rhs.s2) % P);
    }
    Data operator - (const Data& rhs) const {
        return Data(s0 - rhs.s0, s1 - rhs.s1, (s2 - rhs.s2 + P) % P);
    }
    inline int calc() { int s = s1 % P; return (s2 - 1LL * s % P * s % P * inv[s0] % P + P) % P; }
} Sum[MAXN], stk[MAXN];

int n, m, top;
int A[MAXN];
int pre[MAXN], suf[MAXN];
int Ansp[MAXN], Anss[MAXN], Posp[MAXN], Poss[MAXN];

inline Data Part(int L, int R) {
    if (L == 0 || R == 0) return Data();
    return Sum[R] - Sum[L - 1];
}

namespace PSGT {
    // [L, k], (k, ..., R]
    // [L, k] 为一段, 其余部分不一定是一段 
    struct Node { int lc, rc, L, R, k; } dat[MAXN << 6];
    int nidx;

    inline void maintain(int nd) {
        const int &rc = dat[nd].rc, &lc = dat[nd].lc;
        dat[nd].L = dat[nd].R = dat[lc].L;
        if (rc) dat[nd].R = dat[rc].R;
        dat[nd].k = dat[lc].k;
    }

    int Mdy(int nd, int L, int R, const int& pos, const int& vL, const int& vR) {
        int nxt = ++nidx;
        dat[nxt] = dat[nd];
        if (L == R) return dat[nxt].L = vL, dat[nxt].R = dat[nxt].k = vR, nxt;
        int Mid = (L + R) / 2;
        if (pos <= Mid) dat[nxt].lc = Mdy(dat[nxt].lc, L, Mid, pos, vL, vR);
        else dat[nxt].rc = Mdy(dat[nxt].rc, Mid+1, R, pos, vL, vR);
        return maintain(nxt), nxt;
    }

    int QryR(int nd, int L, int R, const int& pos) {
        if (L == R) return dat[nd].R;
        int Mid = (L + R) / 2;
        if (pos <= Mid) return QryR(dat[nd].lc, L, Mid, pos);
        return QryR(dat[nd].rc, Mid+1, R, pos);
    }

    int QryL(int nd, int L, int R, const int& pos, Data& d) {
        if (R <= pos) {
            Data vL = Part(dat[nd].L, dat[nd].k), vR = Part(dat[nd].k + 1, dat[nd].R);
            if (vR + d <= vL)
                return d = d + Part(dat[nd].L, dat[nd].R), 0;
            if (L == R) return dat[nd].R;
        }
        int Mid = (L + R) / 2;
        // 尽可能找到最大的可行 L
        if (pos > Mid) {
            int ret = QryL(dat[nd].rc, Mid+1, R, pos, d); 
            if (ret != 0) return ret;
        }
        return QryL(dat[nd].lc, L, Mid, pos, d);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(A[i]);
    // init
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; ++i) inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
    // solve
    for (int i = 1; i <= n; ++i)
        Sum[i] = Sum[i-1] + Data(1, A[i], 1LL * A[i] * A[i] % P);
    // pre done
    stk[top = 0] = Data();
    for (int i = 1; i <= n; ++i) {
        stk[++top] = Data(1, A[i], 1LL * A[i] * A[i] % P);
        while (top > 1 && stk[top] <= stk[top-1])
            stk[top-1] = stk[top-1] + stk[top], --top;
        Posp[i] = top;
        Ansp[i] = (Ansp[i - stk[top].s0] + stk[top].calc()) % P;
        pre[i] = PSGT::Mdy(pre[i-1], 1, n, top, i - stk[top].s0 + 1, i);
    }
    // suf done
    stk[top = 0] = Data();
    for (int i = n; i; --i) {
        stk[++top] = Data(1, A[i], 1LL * A[i] * A[i] % P);
        while (top > 1 && stk[top-1] <= stk[top])
            stk[top-1] = stk[top-1] + stk[top], --top;
        Poss[i] = top;
        Anss[i] = (Anss[i + stk[top].s0] + stk[top].calc()) % P;
        suf[i] = PSGT::Mdy(suf[i+1], 1, n, top, i, i + stk[top].s0 - 1);
    }
    printf("%d\n", Ansp[n]);
    // output
    while (m--) {
        static int x, val;
        read(x), read(val);
        int L = 0, R = Poss[x + 1] - 1;
        while (L <= R) {
            int Mid = (L + R) / 2;
            int Rp = Mid? PSGT::QryR(suf[x+1], 1, n, Poss[x+1] - Mid + 1): x;
            Data d = Data(1, val, 1LL * val * val % P) + Part(x+1, Rp);
            if (x > 1) PSGT::QryL(pre[x-1], 1, n, Posp[x-1], d);
            if (d < Part(Rp + 1, PSGT::QryR(suf[x+1], 1, n, Poss[x+1] - Mid))) R = Mid - 1;
            else L = Mid + 1;
        }
        int Rp = (R + 1 > 0)? PSGT::QryR(suf[x+1], 1, n, Poss[x+1] - R): x;
        Data d = Data(1, val, 1LL * val * val % P) + Part(x+1, Rp);
        int Lp = x > 1? PSGT::QryL(pre[x-1], 1, n, Posp[x-1], d): x;
        printf("%d\n", ((Ansp[Lp] + d.calc()) % P + Anss[Rp+1]) % P);
    }
    return 0;
}

DepletedPrism's Blog

HNOI 2019 大赏

「HNOI2019」鱼

题目链接

解题思路

代码实现

「HNOI2019」JOJO

题目链接

解题思路

代码实现

「HNOI2019」多边形

题目链接

解题思路

代码实现

「HNOI2019」校园旅行

题目链接

解题思路

代码实现

「HNOI2019」白兔之舞

题目链接

前置知识

解题思路

代码实现

「HNOI2019」序列

题目链接

解题思路

代码实现