十二省联考 2019 大赏

2020-03-16

其实之前都已经写地差不多了…

「十二省联考 2019」异或粽子

~~听说是原题? 原题没写过怎么办啊.~~

题目链接

https://loj.ac/problem/3048

解题思路

考虑到区间异或值, 可以看作前缀异或值的两点异或值. 那么在处理出前缀异或值后, 所求即为前 $k$ 大有序对, 对应位置异或值的和.

考虑到 $a \mathrm {xor} b$ = $b \mathrm{xor} a$, 以及 $a \mathrm{xor} a = 0$, 求出前 $2k$ 大两两异或最大值, 并将最终答案 / 2 即可.

整个过程可以用 0-1 Trie 和优先队列实现.

具体地说, 对每个位置在 Trie 上查出最大异或值, 丢进优先队列. 此后在优先队列中取出 $2k$ 个元素, 若取出元素为该位置第 $x$ 大异或值, 那么重新放入第 $x+1$ 大异或值.

类似的优先队列技巧也在「NOI2010」超级钢琴中使用过.

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

代码实现

> 点击显示 / 隐藏

// LOJ #3048
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
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 = 5e5 + 5, LOG = 32;

struct Item {
    int u, k; LL s;
    Item(int _u, int _k, LL _s): u(_u), k(_k), s(_s) { }
    bool operator < (const Item& rhs) const {
        return s < rhs.s;
    }
};

int n, K;
LL A[MAXN];
priority_queue<Item> PQ;

namespace Trie {
    int ch[2][MAXN << 5], size[MAXN << 5], nidx;

    inline void init() { nidx = 1; }

    inline void insert(LL S) {
        int u = 1;
        for (int i = LOG - 1; i >= 0; --i) {
            int c = (S >> i) & 1;
            ++size[u];
            if (!ch[c][u]) ch[c][u] = ++nidx;
            u = ch[c][u];
        }
        ++size[u];
    }

    LL Qry(LL S, int k) {
        LL ret = 0;
        for (int u = 1, i = LOG - 1; i >= 0; --i) {
            int c = (S >> i) & 1;
            if (!ch[!c][u]) u = ch[c][u];
            else if (k <= size[ch[!c][u]]) u = ch[!c][u], ret |= 1LL << i;
            else k -= size[ch[!c][u]], u = ch[c][u];
        }
        return ret;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Trie::init();
    // input
    read(n), read(K), K <<= 1;
    for (int i = 1; i <= n; ++i) {
        static LL x;
        read(x), A[i] = A[i-1] ^ x;
    }
    // solve
    // 注意到要往 Trie 里塞个 0
    for (int i = 0; i <= n; ++i) Trie::insert(A[i]);
    for (int i = 0; i <= n; ++i) PQ.push(Item(i, 1, Trie::Qry(A[i], 1)));
    LL ans = 0;
    while (K--) {
        Item u = PQ.top(); PQ.pop();
        ans += u.s;
        if (u.k + 1 <= n) PQ.push(Item(u.u, u.k + 1, Trie::Qry(A[u.u], u.k + 1)));
    }
    // output
    printf("%lld\n", ans >> 1);
    return 0;
}

「十二省联考 2019」字符串问题

题目链接

https://loj.ac/problem/3049

解题思路

我之前有写过的说… 参见「十二省联考 2019」字符串问题题解.

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

代码实现

~~假装自己又写了一遍~~

> 点击显示 / 隐藏

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

typedef long long LL;
const int MAXN = 2e5 + 5, MAXM = MAXN << 1, LOG = 19, SIGMA = 26;
const int MAXV = MAXM << 1, MAXE = MAXV << 1;

int n, m, uidx;
char S[MAXN];
int A[MAXN], B[MAXN], nA, nB;

bool isA[MAXV];
int pre[LOG][MAXM], pos[MAXN], len[MAXV], lst[MAXM];
vector<int> G[MAXM];

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

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

    LL Toposort() {
        static LL f[MAXV];
        queue<int> Q;
        memset(f, 0, (uidx + 1) * sizeof (LL));
        for (int i = 1; i <= uidx; ++i) if (!in[i]) Q.push(i);
        LL ret = 0;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            ret = max(ret, f[u] + len[u]);
            for (int i = head[u]; ~i; i = edges[i].nxt) {
                int v = edges[i].to;
                f[v] = max(f[v], f[u] + len[u]);
                if (!(--in[v])) Q.push(v);
            }
        }
        for (int i = 1; i <= uidx; ++i) if (in[i]) return -1;
        return ret;
    }
}

namespace SAM {
    int ch[MAXM][SIGMA], lnk[MAXM], nidx, last;

    inline void init() {
        nidx = last = 1, memset(ch[1], 0, sizeof ch[1]);
    }
    inline int newnode(int l) {
        len[++nidx] = l, lnk[nidx] = 0;
        return memset(ch[nidx], 0, sizeof ch[nidx]), nidx;
    }

    inline void insert(int val) {
        int nd = newnode(len[last] + 1), p = last;
        while (p && !ch[p][val]) ch[p][val] = nd, p = lnk[p];
        if (!p) lnk[nd] = 1;
        else {
            int q = ch[p][val];
            if (len[q] == len[p] + 1) lnk[nd] = q;
            else {
                int nxt = newnode(len[p] + 1);
                lnk[nxt] = lnk[q], memcpy(ch[nxt], ch[q], sizeof ch[nxt]);
                while (p && ch[p][val] == q) ch[p][val] = nxt, p = lnk[p];
                lnk[q] = lnk[nd] = nxt;
            }
        }
        last = nd;
    }

    void build() {
        for (int i = 1; i <= nidx; ++i) pre[0][i] = lnk[i];
        for (int j = 1; j < LOG; ++j)
            for (int i = 1; i <= nidx; ++i) pre[j][i] = pre[j-1][pre[j-1][i]];
    }

    inline int Jump(int u, const int& lgt) {
        for (int j = LOG - 1; j >= 0; --j)
            if (pre[j][u] && len[pre[j][u]] >= lgt) u = pre[j][u];
        return u;
    }
}

inline bool cmp(const int& a, const int& b) {
    return len[a] < len[b] || (len[a] == len[b] && isA[a] < isA[b]);
}

int main() {
#ifndef ONLINE_JUDGE
    // freopen("input.in", "r", stdin);
#endif
    int Ti; scanf("%d", &Ti);
    while (Ti--) {
        // init
        SAM::init(), Graph::init();
        memset(isA, false, sizeof isA);
        // input
        scanf("%s", S+1);
        // solve
        n = (int) strlen(S + 1);
        for (int i = n; i; --i) SAM::insert(S[i] - 'a'), pos[i] = SAM::last;
        SAM::build();
        // build graph
        uidx = SAM::nidx;
        scanf("%d", &nA);
        for (int L, R, i = 1; i <= nA; ++i) {
            scanf("%d%d", &L, &R);
            int lgt = R - L + 1, u = SAM::Jump(pos[L], lgt);
            len[++uidx] = lgt, A[i] = uidx, isA[uidx] = true;
            G[u].push_back(uidx);
        }
        scanf("%d", &nB);
        for (int L, R, i = 1; i <= nB; ++i) {
            scanf("%d%d", &L, &R);
            int lgt = R - L + 1, u = SAM::Jump(pos[L], lgt);
            len[++uidx] = lgt, B[i] = uidx;
            G[u].push_back(uidx);
        }
        for (int v, u = 1; u <= SAM::nidx; ++u) {
            int last = u;
            sort(G[u].begin(), G[u].end(), cmp);
            for (size_t i = 0; i < G[u].size(); ++i) {
                Graph::AddEdge(last, v = G[u][i]);
                if (!isA[v]) last = v;
            }
            lst[u] = last, G[u].clear();
        }
        for (int u = 2; u <= SAM::nidx; ++u) Graph::AddEdge(lst[SAM::lnk[u]], u);
        for (int i = 1; i <= uidx; ++i) if (!isA[i]) len[i] = 0;
        scanf("%d", &m);
        for (int u, v, i = 1; i <= m; ++i)
            scanf("%d%d", &u, &v), Graph::AddEdge(A[u], B[v]);
        // output
        printf("%lld\n", Graph::Toposort());
    }
    return 0;
}

「十二省联考 2019」骗分过样例

题目链接

https://loj.ac/problem/3050

解题思路

$\texttt{1_998244353}$

观察到结果是 $19$ 的幂次, 直接快速幂即可. 对于较大的数, 读入的同时模 $\varphi(998244353) = 998244352$ 即可.
$\texttt{1?}$

~~可以开始吐槽出题人了 (~~

观察到结果的最大值为 $1145099$, 从此处枚举模数 $p$, 并用一个大数验证即可.

为防止出题人毒瘤, 可以用拓展欧拉定理处理这个较大数. 实际上得到的模数是 $1145141$, 恰好是一个 ~~恶臭的~~ 素数.
$\texttt{1?+}$

此时需要猜一个 $10^{18}$ 级别的大模数…

观察到数据中有
1
2
264708066 1996649514996338529
264708068 1589589654696467295
那么有

即

先考虑 $m$ 是素数的情况, 用 Linux 下命令 factor 分解, 得
1
719200885258981741674: 2 3 23 5211600617818708273
选择 $5211600617818708273$ 检验, 发现这就是要找的模数.

$\texttt{1wa_998244353}$

~~那么出题人是怎么写挂的呢~~

猜测这个写法是 int 溢出得到的… 而测试点 #6 也印证了这一点.

此时答案会出现循环, 找到起始位置和循环节长度即可. 似乎可以手算, 但是我选择写程序暴力.

#include <bits/stdc++.h>
using namespace std;

const int P = 998244353;

map<int, int> M;

int main() {
    int x = 1;
    M[1] = 0;
    for (int i = 1; ; ++i) {
        x = 19 * x % P;
        if (M.count(x) != 0) { printf("%d %d\n", M[x], i); break; }
        M[x] = i;
    }
    return 0;
}

得到 55245 100944, 那么循环节长度为 45699, 起始位置为 55245, 预处理出前 100944 位答案即可.

尽管出题人提醒自然溢出是 ub, 但是强制类型转换我没能调出来, 于是只能 “自然溢出啥事没有” 了, ~~感谢编译器没有把我的电脑关掉~~.

$\texttt{2p}$

题意: 判断区间内每一个数是否为素数, 若为素数输出 'p', 否则输出 '.'.

观察到区间长度是 $10^6$ 级别的, 那么用 Miller-Rabin 判素即可.

单次 Miller-Rabin 判素的时间复杂度为 $O(k \log^3 n)$. 来源: 米勒-拉宾素性检验.

此处只选择 $2$, $3$ 两个素数即可. 虽然正确性堪忧, 但是可以通过给定的数据.
$\texttt{2u}$

题意: 计算区间内每一个数的 $\mu(n)$, 根据 $\mu(n)$ 的值输出 '0' / '+' / '-'.

观察到区间长度为 $10^6$, 最大值为 $10^{18}$. 在筛出 $10^6$ 以内的素数后, 枚举素数的该区间内的倍数.

由 $\mu$ 的定义可知,
- 如果此时某个数 $n$ 被 $p^2$ 整除, 那么 $\mu(n) = 0$.
- 如果此时某个数 $n$ 被 $p$ 整除, 则令 $\mu(n) := -\mu(n)$.
此后剩下的数 $n$, 若 $n \neq 1$, 那么 $n$ 可表示为最多两个 $> 10^6$ 的素数的乘积.
- 如果 $n$ 为素数, 那么 $\mu(n)$ 取反.
- 如果 $n$ 为完全平方数, 那么 $\mu(n) = 0$.
- 对于其余情况, $n$ 为两不同素数乘积, 对 $\mu(n)$ 取值没有影响.
$\texttt{2g}$

题意: 判断区间内每一个数是否为给定数的原根, 若为原根输出 'g', 否则输出 '.'.

神仙曾经教育过, “求原根大多数情况直接按定义暴力”. 此时可解决求 $998244353$ 原根的情况.

具体地说, 若 $g$ 为 $m$ 原根, 将 $\varphi(m)$ 质因数分解, 对于每个质因数 $p_i$ 都满足 $g ^ {\frac{\varphi(m)}{p_i}} \not\equiv 1 \pmod m$. from OI-Wiki 原根.

显然这个方法在 $\varphi(m)$ 质因数个数较多, 判断区间长度较大时有效率问题. 考虑此种情况下的数 $13123111$ 较小, 可以预处理出答案后 $O(1)$ 回答.

假定已经找到了 $m$ 的一个原根 $g$, 设 $x = g ^ k\mod m$, 那么 $x$ 为 $m$ 的原根当且仅当 $k$ 同 $\varphi(m)$ 互质.

此时枚举指标 $k$, 并标记 $\varphi(m)$ 质因数的倍数即可.
$\texttt{2g?}$

此时又需要猜数…

// Hint: ? is a prime number larger than 1000000000 but smaller than 2000000000

考虑到存在原根的数必然形如 $2, 4, p^a, 2p^a$, 其中 $p$ 为奇素数. $a$ 为正整数. from OI-Wiki 原根.

直接在这个范围内大力寻找就好了.

还是优先考虑素数, 可以得到结果 1515343657.

代码实现

写得很垃圾…

Miller-Rabin 的快速幂部分用 __int128 / __float128 才能勉强保证精度, 为了拯救代码的大常数只用了 2 个素数, 没救了.

> 点击显示 / 隐藏

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

typedef long long LL;
typedef unsigned long long uLL;

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;
    }
    template<typename T> inline void read(T& x, LL m) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = (x * 10LL + ch - '0') % m, ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

namespace Solve1 {
    const int P = 998244353;

    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 main() {
        int n; read(n);
        for (int x, i = 1; i <= n; ++i)
            read(x, P-1), printf("%d\n", fpow(19, x));
        return 0;
    }
}

namespace Solve2 {
    const int P = 1145141;

    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 main() {
        int n; read(n);
        for (int x, i = 1; i <= n; ++i)
            read(x, P-1), printf("%d\n", fpow(19, x));
        return 0;
    }
}

namespace Solve3 {
    const LL P = 5211600617818708273;

    inline LL plus(uLL a, uLL b) { return a + b >= P? a + b - P: a + b; }
    LL smul(LL base, LL b) {
        LL ret = 0;
        while (b > 0) {
            if (b & 1) ret = plus(ret, base);
            base = plus(base, base), b >>= 1;
        }
        return ret;
    }
    LL fpow(LL base, LL b) {
        LL ret = 1;
        while (b > 0) {
            if (b & 1) ret = smul(ret, base);
            base = smul(base, base), b >>= 1;
        }
        return ret;
    }

    int main() {
        int n; read(n);
        for (int x, i = 1; i <= n; ++i)
            read(x), printf("%lld\n", fpow(19, x));
        return 0;
    }
}

namespace Solve4 {
    const int P = 998244353, BEG = 55244, LOOP = 45699;

    int n, A[BEG + LOOP + 1];

    int main() {
        A[0] = 1;
        for (int i = 1; i <= BEG + LOOP; ++i) A[i] = 19 * A[i-1] % P;
        read(n); LL x;
        while (n--) read(x), printf("%d\n", A[x < BEG? x: (x - BEG) % LOOP + BEG]);
        return 0;
    }
}

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

    bool isPrime(LL p, int L = 2) {
        if (p == 2 || p == 3) return true;
        if (p < 2 || p % 2 == 0) return false;
        for (int a = 2; a <= L; ++a) {
            if (fpow(a, p-1, p) != 1) return false;
            LL t, k = p - 1;
            while (!(k & 1)) {
                k >>= 1, t = fpow(a, k, p);
                if (t != p-1 && t != 1) return false;
                if (t == p-1) break;
            }
        }
        return true;
    }
}
using MillerRabin::isPrime;

namespace Solve5 {
    int main() {
        int n; read(n);
        while (n--) {
            static LL L, R; 
            read(L), read(R);
            for (LL i = L; i <= R; ++i) putchar(isPrime(i, 3)? 'p': '.');
            putchar('\n');
        }
        return 0;
    }
}

namespace Solve6 {
    const int MAXN = 1e6 + 5;

    int n;
    LL L, R, A[MAXN];

    bool notPrime[MAXN];
    int mu[MAXN], Prime[MAXN], tot;

    void EulerSieve() {
        notPrime[1] = true;
        for (int i = 2; i < MAXN; ++i) {
            if (!notPrime[i]) Prime[++tot] = i;
            for (int j = 1; j <= tot && i*Prime[j] < MAXN; ++j) {
                notPrime[i*Prime[j]] = true;
                if (i % Prime[j] == 0) break;
            }
        }
    }

    inline char val(int x) { return (x == 0)? '0': (x < 0? '-': '+'); }

    int main() {
        EulerSieve(), read(n);
        while (n--) {
            read(L), read(R);
            for (int i = 1; i <= R - L + 1; ++i) mu[i] = 1, A[i] = i + L - 1;
            for (int j = 1; j <= tot; ++j) {
                const int& p = Prime[j];
                // 枚举倍数
                for (int i = 1LL * p * ((L-1) / p + 1) - L + 1; i <= R-L+1; i += p) {
                    if (A[i] % (1LL * p * p) == 0) mu[i] = 0;
                    else mu[i] = -mu[i], A[i] /= p;
                }
            }
            for (int i = 1; i <= R - L + 1; ++i) {
                if (mu[i] != 0 && A[i] > 1) {
                    LL m = sqrt(A[i]);
                    if (m * m == A[i]) mu[i] = 0;
                    else if (A[i] <= 1e12 || isPrime(A[i])) mu[i] = -mu[i];
                    // A[i] <= 1e12 时, 一定是素数
                }
                putchar(val(mu[i]));
            }
            putchar('\n');
        }
        return 0;
    }
}

namespace Solve7 {
    const int MAXN = 2e7+5, MAXM = 1e6+5;

    int n, p, L, R;
    int fact[MAXM], tot;
    int vis[MAXN], lg[MAXN];

    void prime(int x) {
        tot = 0;
        for (int i = 2; i*i < x; ++i) if (x % i == 0) {
            fact[++tot] = i;
            while (x % i == 0) x /= i;
        }
        if (x > 1) fact[++tot] = x;
    }
    int fpow(int base, int b, int m) {
        int ret = 1;
        while (b > 0) {
            if (b & 1) ret = 1LL * ret * base % m;
            base = 1LL * base * base % m, b >>= 1;
        }
        return ret % m;
    }

    bool isroot(int g) {
        for (int i = 1; i <= tot; ++i)
            if (fpow(g, (p - 1) / fact[i], p) == 1) return false;
        return true;
    }

    int main() {
        read(n);
        while (n--) {
            read(L), read(R);
            if (R != 234133333) read(p); else p = 1515343657;
            prime(p - 1);
            if (p == 13123111) {
                for (int j = 1; j <= tot; ++j)
                    for (int i = 1; i <= (p-1) / fact[j]; ++i) vis[i * fact[j]] = 1;
                // 6 为 13123111 原根
                for (int x = 6, i = 1; i < p; ++i, x = 6LL * x % p) lg[x] = i;
                for (int i = L; i <= R; ++i) putchar(vis[lg[i]]? '.': 'g');
            } else for (int i = L; i <= R; ++i) putchar(isroot(i)? 'g': '.');
            putchar('\n');
        }
        return 0;
    }
}

const int MAXL = 32;
char cmd[MAXL];

int main() {
#ifndef ONLINE_JUDGE
    freopen("output.out", "w", stdout);
#endif
    scanf("%s", cmd);
    if (cmd[0] == '1') {
        if (cmd[1] == '_') return Solve1::main();
        if (cmd[1] == '?') {
            if (cmd[2] == '+') return Solve3::main();
            return Solve2::main();
        }
        if (cmd[1] == 'w') return Solve4::main();
    }
    if (cmd[0] == '2') {
        if (cmd[1] == 'p') return Solve5::main();
        if (cmd[1] == 'u') return Solve6::main();
        if (cmd[1] == 'g') return Solve7::main();
    }
    return 0;
}

「十二省联考 2019」皮配

不是网络流.

题目链接

https://loj.ac/problem/3051

解题思路

考虑背包.

如果 $k = 0$, 此时为城市选定阵营, 为学校选定导师两种决策互不影响, 直接朴素背包计算方案数, 利用乘法原理相乘即可.

具体地说, 用 $f(i)$ 表示选择蓝阵营总人数为 $i$ 的方案数, $g(i)$ 表示选择鸭派系总人数为 $i$ 的方案数, 记 $S$ 为总人数和, 那么答案为

$\sum_{i = S - C1} ^ {C0} f(i) \sum_{j = S - D1} ^ {D0} g(j)$

此时时间复杂度为 $O((n + c) M)$.

如果 $k > 0$, 没有偏好的城市 / 学校不会受到影响, 直接用以上方法处理即可.

考虑有偏好的城市 / 学校如何处理. 观察到 $k$ 很小, 此时使用高维 DP. 设 $F(i, j)$ 表示在有偏好的城市及学校中, 城市选择蓝阵营人数为 $i$, 学校选择鸭派系人数为 $j$ 的方案数.

转移有些复杂… 大力讨论学校偏好即可. 此时动态维护阵营和派系的人数上限可减小常数.

最后分别枚举蓝阵营和鸭派系人数, 利用 $f, g$ 的前缀和 $O(1)$ 合并答案即可.

综上, 时间复杂度为 $O((n + c) M + kM \min \{M, k \cdot \max \{ s_i \}\})$.

代码实现

> 点击显示 / 隐藏

// LOJ #3051
// 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 = 1e3 + 5, MAXM = 2.5e3 + 5, MAXK = 35;
const int P = 998244353;

int n, c, K;
int C0, C1, D0, D1;

bool vis[MAXN];
int b[MAXN], s[MAXN], cs[MAXN], p[MAXN];

int f[MAXM], g[MAXM], pf[MAXM], pg[MAXM];
int F[MAXM][MAXM], G[MAXM][MAXM];

int solve() {
    // init
    read(n), read(c);
    read(C0), read(C1), read(D0), read(D1);
    memset(p, -1, (n+1) * sizeof (int));
    for (int i = 1; i <= c; ++i)
        vis[i] = false, cs[i] = 0;
    // input
    int S = 0;
    for (int i = 1; i <= n; ++i)
        read(b[i]), read(s[i]), cs[b[i]] += s[i], S += s[i];
    read(K);
    for (int idx, i = 1; i <= K; ++i)
        read(idx), read(p[idx]), vis[b[idx]] = true;
    // solve
    memset(f, 0, (C0 + 1) * sizeof (int));
    pf[0] = f[0] = 1;
    for (int i = 1; i <= c; ++i) if (!vis[i] && cs[i] > 0) {
        const int& w = cs[i];
        for (int j = C0; j >= w; --j)
            f[j] = (f[j] + f[j - w]) % P;
    }
    for (int i = 1; i <= C0; ++i) pf[i] = (pf[i-1] + f[i]) % P;
    memset(g, 0, (D0 + 1) * sizeof (int));
    pg[0] = g[0] = 1;
    for (int i = 1; i <= n; ++i) if (p[i] == -1) {
        const int& w = s[i];
        for (int j = D0; j >= w; --j)
            g[j] = (g[j] + g[j - w]) % P;
    }
    for (int i = 1; i <= D0; ++i) pg[i] = (pg[i-1] + g[i]) % P;
    memset(F, 0, sizeof F);
    memset(G, 0, sizeof G);
    F[0][0] = 1;
    int Cs = 0, Ss = 0;
    for (int ci = 1; ci <= c; ++ci) if (vis[ci]) {
        Cs = min(C0, Cs + cs[ci]);
        for (int i = 0; i <= Cs; ++i)
            for (int j = 0; j <= Ss; ++j) G[i][j] = F[i][j];
        for (int si = 1; si <= n; ++si) {
            const int &w = s[si], &h = p[si];
            if (b[si] != ci || h == -1) continue;
            Ss = min(D0, Ss + w);
            if (h == 1 || h == 3) {
                // 二维指针不会开.c
                // auto 真香.cpp
                auto A = (h == 1)? F: G;
                for (int i = 0; i <= Cs; ++i) {
                    for (int j = Ss; j >= w; --j) A[i][j] = A[i][j - w];
                    for (int j = 0; j < w; ++j) A[i][j] = 0;
                }
            }
            auto A = (h >= 2)? F: G;
            for (int i = 0; i <= Cs; ++i)
                for (int j = Ss; j >= w; --j)
                    A[i][j] = (A[i][j] + A[i][j - w]) % P;
        }
        const int& w = cs[ci];
        for (int j = 0; j <= Ss; ++j) {
            for (int i = Cs; i >= w; --i) F[i][j] = F[i - w][j];
            for (int i = 0; i < w; ++i) F[i][j] = 0;
        }
        for (int i = 0; i <= Cs; ++i)
            for (int j = 0; j <= Ss; ++j) F[i][j] = (F[i][j] + G[i][j]) % P;
    }
    // output
    int ret = 0;
    for (int i = 0; i <= Cs; ++i)
        for (int j = 0; j <= Ss; ++j) {
            int L1 = max(0, S - C1 - i), R1 = C0 - i,
                L2 = max(0, S - D1 - j), R2 = D0 - j;
            if (L1 > R1 || L2 > R2) continue;
            int s1 = (pf[R1] + (L1 > 0? P - pf[L1-1]: 0)) % P,
                s2 = (pg[R2] + (L2 > 0? P - pg[L2-1]: 0)) % P;
            ret = (ret + 1LL * s1 * s2 % P * F[i][j] % P) % P;
        }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti);
    while (Ti--) printf("%d\n", solve());
    return 0;
}

「十二省联考 2019」春节十二响

~~清明十二响~~

题目链接

https://loj.ac/problem/3052

解题思路

这是一道清新题.

部分分的提示很明显了, 先考虑一条链的情况怎么做.

假设当前链被根分成了两段, 且这两段之间没有祖先-后代关系. 记这两段序列为 $a_1, a_2, \ldots, a_n$, $b_1, b_2, \ldots, b_m$.

令 $n \ge m$, 那么将 $a$ 前 $m$ 大元素取出, 并从大到小依次对应 $b$ 中每一个元素, 取最大值作为当前段的权值, 也就是 “这个段的子程序所需内存大小的最大值”. 此时同 $b$ 合并后得到权值, $a$ 中剩余元素, 根的权值的和即为答案.

对于树的情况, 直接把每个儿子的答案序列, 按链的方式依次合并即可.

具体证明参见官方题解好了 (

用优先队列实现这个过程就好了. 由于每个节点出队后不会再进队, 换句话说, 总的合并次数为 $O(n)$.

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

代码实现

> 点击显示 / 隐藏

// LOJ #3052
// 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 long long LL;
const int MAXN = 2e5 + 5;

int n;
priority_queue<int> PQ[MAXN];
int pre[MAXN], M[MAXN], Idx[MAXN];

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN];
    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 dfs(int u) {
        static int A[MAXN], nA;
        Idx[u] = u;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            dfs(v = edges[i].to);
            int &iu = Idx[u], &iv = Idx[v];
            if (PQ[iv].size() > PQ[iu].size()) swap(iu, iv);
            nA = 0;
            while (!PQ[iv].empty())
                A[++nA] = max(PQ[iv].top(), PQ[iu].top()), PQ[iv].pop(), PQ[iu].pop();
            for (int j = 1; j <= nA; ++j) PQ[iu].push(A[j]);
        }
        PQ[Idx[u]].push(M[u]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    // freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    read(n);
    for (int i = 1; i <= n; ++i) read(M[i]);
    for (int i = 2; i <= n; ++i) read(pre[i]);
    // solve
    for (int i = 2; i <= n; ++i) Graph::AddEdge(pre[i], i);
    Graph::dfs(1);
    // output
    LL ans = 0;
    const int& u = Idx[1];
    while (!PQ[u].empty()) ans += PQ[u].top(), PQ[u].pop();
    printf("%lld\n", ans);
    return 0;
}

「十二省联考 2019」希望

题目链接

https://loj.ac/problem/3053

解题思路

~~没希望, 走了.~~

可以发现, 对于一个联通块 $S$, 设满足在 $S$ 中且到 $S$ 中任意点距离都 $\le L$ 的点集为 $T$, 则 $T$ 也是一个联通块.

推广到 $k$ 个连通块的情况, 也就是满足题目要求的点集 $T$ 为一个连通块.

设连通块边集为 $E$, 点集为 $V$, 考虑到树上连通块的性质, 有 $|E| - |V| = 1$.

那么可以通过容斥计算答案. 设 $f(u)$ 表示以点 $u$ 为中心点的联通块数, $g(e)$ 表示以边 $e$ 的两个端点为中心点联通块数, 那么答案可表示为

$\sum_{u \in V} f(u)^k - \sum_{e \in E} g(e)^k$

于是就可以 DP 了. 以下过程中钦定根节点为 $1$.

设 $f(i, j)$ 表示以 $i$ 为根的子树, 包含节点 $i$ 且同 $i$ 距离不超过 $j$ 的连通块个数. 那么转移为

$f(u, i) = \prod_{v \in son(u)} \left(f(v, i-1) + 1\right)$

设 $g(i, j)$ 表示包含节点 $i$, 不包含以 $i$ 为根的子树, 且同 $i$ 距离不超过 $j$ 的连通块个数. 记 $fa$ 为 $u$ 父亲节点, 那么转移为

$g(u, i) = g(fa, i-1) \prod_{v \in son(fa),\ v \neq u} \left(f(v, i-2) + 1\right) + 1$

记边 $(u, v)$ 中 $v$ 为较深节点, 那么答案为

$\sum_{u = 1} ^ n \big(f(u, L)\cdot g(u, L)\big) ^ k - \sum_{(u, v) \in E} \big(f(v, L-1) \cdot (g(v, L) - 1)\big) ^ k$

此时直接树形 DP, 两次 DFS 分别处理 $f, g$ 即可.

时间复杂度 $O(nL)$. 36 pts 滚出.

~~使用长链剖分, 可回退数据结构, 离线求逆元优化即可 AC~~.

注意到 $f, g$ 的转移可以通过长链剖分优化, 转移时可以用数据结构维护.

另外 $f, g$ 的状态在设计时, 给出的限制是 “距离不超过”. 记 $d(u)$ 为节点 $u$ 到子树内叶子的最长距离, 那么不管 $L$ 的限制, 第二维 $\geq d(u)$ 的状态和第二维等于 $d(u)$ 的状态值相等.

直接记录 $d(u)$ 的值, 对于超过 $d(u)$ 的部分直接取 $d(u)$ 的值即可.

转移对 $f, g$ 的修改只是后缀乘, 全局加, 以及单点修改. 利用可回退数据结构 —- 也就是用类似栈的结构记录操作, 每次记录修改的位置和值, 回退时恢复 —- 即可. 此步骤的时间复杂度和空间复杂度都是 $O(n)$.

回退时还有一个细节. 在更新 $g$ 的值时, 为了使将来会用到的值不会被提前弹出, 所以转移 $g$ 时需要将 DFS 序翻转.

后缀乘时可能出现模数 $P$ 的倍数, 也就是要考虑后缀乘 $0$ 的问题. 另外维护一个标记, 表示这个标记后的值全部为 $0$ 即可. 注意此时的 “为 $0$” 指经过 $ax + b$ 的标记运算后为 $0$, 也就是后缀赋值 $-\frac{b}{a}$.

但是转移 $g$ 时需要用到乘法逆元. 所幸需要用到的值的逆元可以不考虑 $L$ 的限制, 通过一次 DFS 求出. 那么用 “线性求逆元” 的 Trick $O(n)$ 计算就好了.

综上, 得出了时间复杂度为 $O(n)$ 的做法.

代码实现

36 pts 代码.

> 点击显示 / 隐藏

// LOJ #3053
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
#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;

const int MAXN = 1e6 + 5, MAXL = 1e3 + 5, P = 998244353;

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

int n, L, K, ans;
vector<int> f[MAXN], g[MAXN];

namespace Graph {
    vector<int> G[MAXN];

    inline void AddEdge(int from, int to) { G[from].push_back(to); }

    void dfs1(int u, int fa) {
        for (auto v: G[u]) if (v != fa) {
            dfs1(v, u);
            for (int i = 1; i <= L; ++i)
                f[u][i] = 1LL * f[u][i] * (f[v][i-1] + 1) % P;
        }
    }

    void dfs2(int u, int fa) {
        static int p[MAXN], s[MAXN], A[MAXN], nA;
        nA = 0;
        for (auto v: G[u]) if (v != fa) A[++nA] = v;
        p[0] = s[nA + 1] = 1;
        for (int i = 1; i <= L; ++i) {
            if (i >= 2) {
                for (int j = 1; j <= nA; ++j)
                    p[j] = 1LL * p[j-1] * (f[A[j]][i-2] + 1) % P;
                for (int j = nA; j >= 1; --j)
                    s[j] = 1LL * s[j+1] * (f[A[j]][i-2] + 1) % P;
            } else for (int j = 1; j <= nA; ++j) p[j] = s[j] = 1;
            for (int j = 1; j <= nA; ++j)
                g[A[j]][i] = (1LL * g[u][i-1] * p[j-1] % P * s[j+1] % P + 1) % P;
        }
        for (auto v: G[u]) if (v != fa) {
            ans = (ans + fpow(1LL * f[v][L-1] * (g[v][L] - 1) % P, K)) % P;
            dfs2(v, u);
        }
    }

    void solve() {
        dfs1(1, 0), dfs2(1, 0);
        ans = P - ans;
        for (int u = 1; u <= n; ++u)
            ans = (ans + fpow(1LL * f[u][L] * g[u][L] % P, K)) % P;
        printf("%d\n", ans);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(L), read(K);
    for (int u, v, i = 1; i < n; ++i)
        read(u), read(v), Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    // init
    for (int i = 1; i <= n; ++i)
        f[i].resize(L + 1, 1), g[i].resize(L + 1, 1);
    // solve
    Graph::solve();
    return 0;
}

100 pts 代码.

> 点击显示 / 隐藏

1	// 码力尚弱, 码力尚弱.

DepletedPrism's Blog

十二省联考 2019 大赏

「十二省联考 2019」异或粽子

题目链接

解题思路

代码实现

「十二省联考 2019」字符串问题

题目链接

解题思路

代码实现

「十二省联考 2019」骗分过样例

题目链接

解题思路

代码实现

「十二省联考 2019」皮配

题目链接

解题思路

代码实现

「十二省联考 2019」春节十二响

题目链接

解题思路

代码实现

「十二省联考 2019」希望

题目链接

解题思路

代码实现