HAOI 2018 大赏

2020-03-12

先祭上出题人题解.

dy0607 的 HAOI2018 Round1 解题报告

然而没有找到 Round 2 的官方题解 (

「HAOI2018」奇怪的背包

要命的 $\gcd$…

题目链接

https://loj.ac/problem/2523

解题思路

所求即为满足

$\sum_{i \in S} a_i V_i \equiv w \pmod P$

的不同集合 $S$ 个数, 其中 $a_i > 0$, 表示物品选择个数.

写成不定方程的形式, 即

$\sum_{i \in S} a_i V_i + yP = w$

根据裴蜀定理, 该方程有解, 则需满足 $\gcd(V_1, V_2, \ldots, P) \mid w$.

可以发现, 对所有值, 同 $P$ 取 $\gcd$ 并不会影响答案, 那么枚举 $P$ 的约数, 直接 DP 即可.

直接 DP… 令 $d(P)$ 表示 $P$ 的约数个数, 容易得到时间复杂度 $O(nd(P)$ 的做法, 但是可以进一步优化.

枚举 $P$ 的约数, 对于同 $P$ 取 $\gcd$ 相同的 $V_i$, 在 DP 时一起算即可.

具体地, 设 $f(i, j)$ 表示选择 $P$ 前 $i$ 个约数, 得到 $P$ 的第 $j$ 个约数的方案数. 记 $s(i)$ 表示第 $i$ 个约数在 $\gcd(V_j, P)$ 中的出现次数, $d_i$ 表示 $P$ 第 $i$ 个约数. 那么有

$f(i, k) = f(i-1, k) + \sum_{\gcd(d_i, d_j) = d_k} f(i-1, j) \cdot (2 ^ {s(i)} -1)$

由于 $P$ 的约数中可能存在一些整除关系, 最后 $O(d^2(P))$ 枚举一遍把贡献加起来就好了.

时间复杂度 $O(\sqrt{P} + n \log P + d ^ 2(P) \log P)$.

另外祭上某张流传已久的表格…

图源 UOJ 用户群, 至少我是从那里找到的

代码实现

> 点击显示 / 隐藏

// LOJ #2523
// DeP
#include <cmath>
#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;

const int MAXN = 1e6 + 5, MAXD = 2e3 + 5, MOD = 1e9 + 7;

int n, m, q, P, idx;
int id1[MAXN], id2[MAXN], pow2[MAXN];
int fact[MAXD], s[MAXD], f[MAXD][MAXD], g[MAXD];

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

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(q), read(P);
    m = sqrt(P);
    // sovle
    for (int d = 1; d * d <= P; ++d) if (P % d == 0) {
        fact[++idx] = d, id1[d] = idx;
        if (d * d != P) fact[++idx] = P / d, id2[d] = idx;
    }
    for (int v, i = 1; i <= n; ++i)
        read(v), v = gcd(v, P), ++s[(v <= m)? id1[v]: id2[P / v]];
    pow2[0] = 1;
    for (int i = 1; i <= n; ++i) pow2[i] = 2LL * pow2[i-1] % MOD;
    f[0][id2[1]] = 1;
    for (int i = 1; i <= idx; ++i)
        for (int j = 1; j <= idx; ++j) {
            int w = gcd(fact[i], fact[j]), k = (w <= m)? id1[w]: id2[P / w];
            f[i][k] = (f[i][k] + 1LL * f[i-1][j] * (pow2[s[i]] - 1 + MOD) % MOD) % MOD;
            f[i][j] = (f[i][j] + f[i-1][j]) % MOD;
        }
    for (int i = 1; i <= idx; ++i)
        for (int j = 1; j <= idx; ++j)
            if (fact[i] % fact[j] == 0) g[i] = (g[i] + f[idx][j]) % MOD;
    // output
    while (q--) {
        static int w;
        read(w), w = gcd(w, P), printf("%d\n", g[(w <= m)? id1[w]: id2[P / w]]);
    }
    return 0;
}

「HAOI2018」反色游戏

题目链接

https://loj.ac/problem/2524

解题思路

首先有一个简洁的结论, 所求的方案数为 $2^{m - n + p}$, 其中 $m$ 为边数, $n$ 为点数, $p$ 为连通分量个数.

官方题解从图论和线性代数两个角度解释了这个结论, 然而我只能流下学不会线性代数的泪水…

于是从图的连通性入手解释这个结论.

单独考虑每一个连通分量, 如果该连通分量中存在偶数个黑点, 那么一定存在可行方案; 否则不存在.

考虑将该连通分量中的黑点任意两两配对, 由于存在偶数个黑点, 所以没有多余. 可以发现

对于两黑点间的任意一条路径, 不论经过的边数是奇是偶, 总可以构造出一种方案, 使得路径上只有这两个黑点颜色反转.
对于这些路径的交, 每次把边选 / 不选的状态取反, 不会影响到原来的局面.

如果存在奇数个黑点, 则不存在以上性质… 因而不存在合法方案.

同时我们知道了, 配对数和方案数是等价的. 换言之, 每种黑点两两匹配的方案, 唯一对应着一个合法解.

所以对于一个点数为 $n$ 的连通分量, 有解的情况有 $2^{n-1}$ 种 (拿组合数加起来推一推可知), 由于边数为 $m$, 共 $2^m$ 种情况, 所以每种有解的情况下, 解的个数为 $2^{m-n+1}$. 对 $p$ 个连通分量进行推广, 答案即为 $2 ^ {m - n + p}$.

似乎还可以从另一个角度解释? 参见 https://www.cnblogs.com/xjqxjq/p/11781185.html.

知道结论后的做法就很明晰了, 跑 tarjan 求割点, 讨论是否有解, 以及删边后整体边数, 点数, 连通分量个数的变化即可.

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

代码实现

> 点击显示 / 隐藏

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

const int MAXN = 1e5 + 5, P = 1e9 + 7;

int n, m;
int V[MAXN], pow2[MAXN];

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

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

    bool Even[MAXN];
    int cut[MAXN], dfn[MAXN], low[MAXN], dfs_clock;
    int Idx[MAXN], size[MAXN], sub[MAXN], idx;

    void tarjan(int u, int fa) {
        int child = 0;
        Idx[u] = idx, size[u] = V[u];
        low[u] = dfn[u] = ++dfs_clock;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if (!dfn[v = edges[i].to]) {
                tarjan(v, u);
                size[u] += size[v], ++child;
                low[u] = min(low[u], low[v]);
                if (low[v] >= dfn[u])
                    ++cut[u], sub[u] += size[v], Even[u] &= !(size[v] & 1);
            } else if (dfn[v] < dfn[u] && v != fa)
                low[u] = min(low[u], dfn[v]);
        }
        if (!fa) --cut[u];
    }

    inline void solve() {
        // init
        dfs_clock = 0;
        for (int u = 1; u <= n; ++u)
            Even[u] = true, sub[u] = dfn[u] = low[u] = cut[u] = 0;
        // solve
        int p = 0, s = 0;
        for (int u = 1; u <= n; ++u)
            if (!dfn[u]) idx = u, ++p, tarjan(u, 0), s += size[u] & 1;
        // output
        int tot = m - n + p;
        printf("%d ", s > 0? 0: pow2[tot]);
        for (int u = 1; u <= n; ++u) {
            if (!deg[u]) printf("%d", s - size[u] > 0? 0: pow2[tot]);
            else printf("%d", (!Even[u] || s - (size[Idx[u]] & 1) > 0 || ((size[Idx[u]] - V[u] - sub[u]) & 1))?
                    0: pow2[tot - deg[u] + 1 + cut[u]]);
            putchar(" \n"[u == n]);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    pow2[0] = 1;
    for (int i = 1; i < MAXN; ++i) pow2[i] = 2LL * pow2[i-1] % P;
    int Ti;
    scanf("%d", &Ti);
    while (Ti--) {
        // init
        Graph::init();
        // input
        scanf("%d%d", &n, &m);
        for (int u, v, i = 1; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            Graph::AddEdge(u, v), Graph::AddEdge(v, u);
        }
        for (int i = 1; i <= n; ++i) scanf("%1d", V+i);
        // solve
        Graph::solve();
    }
    return 0;
}

「HAOI2018」字串覆盖

题目链接

https://loj.ac/problem/2525

解题思路

出题人称本题算法并不优美… 其实也的确不怎么优美 = =

LOJ 上的题面并没有所有数据点的限制, 可以参考洛谷的题面: https://www.luogu.com.cn/problem/P4493.

观察数据点的限制, 可以发现 $r-l$ 的限制非常独特, 于是分两种情况讨论:

$r-l \ge 2000$

此时串 $P$ 较长, 那么 $P$ 在 $T$ 中匹配次数较小.

考虑覆盖操作, 每次选择位置最靠前, 且未被覆盖的位置去覆盖, 直到单次对答案的贡献 $\le 0$. 此时得到的答案一定是最优的.

设匹配次数为 $p$, 利用 SAM 以及线段树合并维护 $endpos$ 集合的套路, 可以在 $O(p \log n)$ 的时间完成单次询问.

具体地说, 对串 $A$ 建 SAM, 在线段树上维护 $endpos$ 中最靠后位置. 对于串 $P$, 利用倍增找到其在 SAM 上对应节点. 如果可以匹配, 每次在线段树上二分, 找到一个最靠前位置, 累计答案, 并继续匹配.

对于 $50 < r-l < 2000$ 的情况, 数据中限制了该情况的出现次数, 直接按以上方法做即可.
$r-l \le 50$

此时串 $P$ 较短, 那么串 $A$ 中所有长度为 $|P|$ 的子串只有 $n - |P| + 1$ 种. 考虑用倍增处理所有的这些子串.

参考 PhantasmDragon 的思路, 对于串 $A$ 中一个从位置 $i$ 开始的子串 $s$, 设 $\operatorname{nxt}(|s|, i, j)$ 表示后 $2^j$ 个字符同 $s$ 相同的字符串的左端点位置.

同时记录 $f(|s|, i, j)$, 表示此时对答案的贡献.

单次查询时形同上面一种情况, 先找到串 $P$ 对应在 SAM 的节点, 以及第一个匹配位置, 然后倍增统计答案即可.

对于预处理, 枚举每个长度, 对于每个不同的子串, 利用哈希和双端队列维护 $\operatorname{nxt}$. 接着套路倍增即可.

直接预处理似乎不太可行, 可以将所有询问离线, 按串 $P$ 长度排序, 遇到不同长度直接重新计算倍增数组就好了.

单次询问时间复杂度 $O(\log n)$.

代码实现

~~直接自然溢出啥事没有~~

然后流下了只会写双哈希的泪水…

> 点击显示 / 隐藏

// LOJ #2525
// DeP
#include <map>
#include <deque>
#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;

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

struct Ask {
    int idx, s, t, L, R;
    bool operator < (const Ask& rhs) const {
        return R - L < rhs.R - rhs.L;
    }
} Q[MAXN];

int n, K, q;
char A[MAXN], B[MAXN];
int Bpos[MAXN], Blgt[MAXN], rt[MAXM], pre[LOG][MAXM];
LL Ans[MAXN];

namespace SGT {
    struct Node { int lc, rc, pos; } dat[MAXM << 5];
    int nidx;

    inline void maintain(int nd) {
        const int &lc = dat[nd].lc, &rc = dat[nd].rc;
        dat[nd].pos = max(dat[lc].pos, dat[rc].pos);
    }

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

    int Mrg(int x, int y) {
        if (!x || !y) return x + y;
        int nd = ++nidx;
        dat[nd].lc = Mrg(dat[x].lc, dat[y].lc);
        dat[nd].rc = Mrg(dat[x].rc, dat[y].rc);
        return maintain(nd), nd;
    }

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

namespace SAM {
    int ch[MAXM][SIGMA], len[MAXM], lnk[MAXM], nidx, last;
    int cnt[MAXN], idx[MAXM];

    inline void init() { nidx = last = 1; }

    inline void insert(int val, int i) {
        int nd = ++nidx, p = last;
        len[nd] = len[last] + 1, SGT::Mdy(rt[nd] = ++SGT::nidx, 1, n, i);
        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 = ++nidx;
                len[nxt] = 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[nd] = lnk[q] = nxt;
            }
        }
        last = nd;
    }

    void build() {
        // toposort
        for (int i = 1; i <= nidx; ++i) ++cnt[len[i]];
        for (int i = 1; i <= n; ++i) cnt[i] += cnt[i-1];
        for (int i = 1; i <= nidx; ++i) idx[cnt[len[i]]--] = i;
        for (int u, i = nidx; i > 1; --i)
            u = idx[i], rt[lnk[u]] = SGT::Mrg(rt[lnk[u]], rt[u]);
        // multi
        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]];
        // match B
        for (int u = 1, l = 0, i = 1; i <= n; ++i) {
            int val = B[i] - 'a';
            if (ch[u][val]) u = ch[u][val], ++l;
            else {
                while (u && !ch[u][val]) u = lnk[u];
                if (!u) u = 1, l = 0;
                else l = len[u] + 1, u = ch[u][val];
            }
            Bpos[i] = u, Blgt[i] = l;
        }
    }

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

    LL Qry(int s, int t, int L, int R) {
        int lgt = R - L + 1, u = Jump(R, lgt);
        if (!u || SGT::dat[rt[u]].pos < s + lgt - 1) return 0;
        LL ret = 0;
        for (int i = SGT::Qry(rt[u], 1, n, s + lgt - 1); i <= t; i = SGT::Qry(rt[u], 1, n, i + lgt)) {
            if (K - (i - lgt + 1) <= 0) break;
            ret += K - (i - lgt + 1);
            if (SGT::dat[rt[u]].pos < i + lgt) break;
        }
        return ret;
    }
}

namespace 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 || (H1 == rhs.H1 && H2 < rhs.H2);
        }
    } P[MAXN], hA[MAXN];
    LL f[LOG][MAXM];
    int nxt[LOG][MAXN];

    void init() {
        P[0] = Hash(1, 1);
        for (int i = 1; i <= n; ++i) {
            P[i] = P[i-1] * Hash(Hash::B, Hash::B);
            hA[i] = hA[i-1], hA[i].insert(A[i]);
        }
    }

    void build(int lgt) {
        map<Hash, deque<int> > Q;
        memset(nxt, 0, sizeof nxt);
        for (int i = 1; i <= n - lgt + 1; ++i) {
            Hash h = hA[i + lgt - 1] - hA[i-1] * P[lgt];
            while (!Q[h].empty() && Q[h].front() <= i - lgt)
                nxt[0][Q[h].front()] = i, Q[h].pop_front();
            Q[h].push_back(i), f[0][i] = K - i;
        }
        for (int j = 1; j < LOG; ++j)
            for (int i = 1; i <= n - lgt + 1; ++i)
                nxt[j][i] = nxt[j-1][nxt[j-1][i]], f[j][i] = f[j-1][i] + f[j-1][nxt[j-1][i]];
    }

    LL Qry(int s, int t, int L, int R) {
        int lgt = R - L + 1, u = SAM::Jump(R, lgt);
        if (!u || SGT::dat[rt[u]].pos < s + lgt - 1) return 0;
        int st = SGT::Qry(rt[u], 1, n, s + lgt - 1) - lgt + 1, ed = t - lgt + 1;
        if (st > ed) return 0;
        LL ret = 0;
        for (int j = LOG-1; j >= 0; --j)
            if (nxt[j][st] && nxt[j][st] <= ed) ret += f[j][st], st = nxt[j][st];
        return ret + f[0][st];
        // nxt[j][st] 不行, 不代表我 st 不行了 (
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    SAM::init();
    // input
    scanf("%d%d%s%s", &n, &K, A+1, B+1);
    read(q);
    for (int s, t, L, R, i = 1; i <= q; ++i) {
        read(s), read(t), read(L), read(R);
        Q[i] = (Ask){ i, s, t, L, R };
    }
    // solve
    Hash::init();
    for (int i = 1; i <= n; ++i) SAM::insert(A[i] - 'a', i);
    SAM::build();
    sort(Q+1, Q+1+q);
    for (int i = 1; i <= q; ++i) {
        if (Q[i].R - Q[i].L > 50) Ans[Q[i].idx] = SAM::Qry(Q[i].s, Q[i].t, Q[i].L, Q[i].R);
        else {
            if (i == 1 || Q[i].R - Q[i].L != Q[i-1].R - Q[i-1].L)
                Hash::build(Q[i].R - Q[i].L + 1);
            Ans[Q[i].idx] = Hash::Qry(Q[i].s, Q[i].t, Q[i].L, Q[i].R);
        }
    }
    // output
    for (int i = 1; i <= q; ++i) printf("%lld\n", Ans[i]);
    return 0;
}

「HAOI2018」苹果树

题目链接

https://loj.ac/problem/2526

解题思路

先吐槽出题人不把模数的限制写详细一点…

不过不怎么影响做题来着.

首先可以发现, 期望再乘 $n!$ 就是大忽悠 = =, 所求即为所有节点数为 $n$ 的二叉树, 两两距离之和的和.

有一个性质, 一条边 $(i, j)$ 被经过的次数为 $s (n - s)$, 其中 $s$ 为 $j$ 对应子树大小. 考虑到 $n \le 2000$, 可以枚举一个点, 以及对应这个点对应子树大小来计算答案.

设当前枚举到第 $i$ 个点, 前 $i$ 个点的位置都确定了, 且节点 $i$ 某一个儿子的子树大小为 $j$.

$\sum_{i=1}^n i! \sum_{j=1}^{n-i} j(n-j) \cdot 2\ \binom{n-i}{j} j! \cdot \prod_{k=i}^{n-j-1}k$

再稍微解释一下, 前 $i$ 个点的选择顺序是一个排列, $i$ 到其某一个儿子的边被经过 $j(n-j)$ 次.

考虑大小为 $j$ 子树的内节点排布情况, 也就是在剩余 $n-i$ 个节点中挑出 $j$ 个节点做一个排列, 由于是二叉树, 方案数 $\times 2$.

再考虑该子树外的情况, 对于剩下的 $n - j - i$ 个节点, 不能挂在该子树内, 依次有 $i, i+1, \ldots, n-j-1$ 种选择 (因为每次都新加了一个节点), 由乘法原理乘起来就好了.

似乎做完了, 其实已经做完了, 后面的累乘预处理一下就好了.

其实后面的累乘化简一下就消掉了, 也就是

$2\sum_{i=1}^n i!(n-i)! \sum_{j=1}^{n-i} j(n-j) \binom{n-j-1}{i-1}$

总感觉这个式子有着什么高妙的组合意义.

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

代码实现

代码中使用了 1 式.

2 式代码也交在 loj 上了, 常数小了一倍…

> 点击显示 / 隐藏

// LOJ #2526
// DeP
#include <cstdio>

const int MAXN = 2005;

int n, Mod;
int fac[MAXN], C[MAXN][MAXN], f[MAXN][MAXN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d", &n, &Mod);
    // init
    C[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % Mod;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) f[i][j] = 1;
        for (int j = i; j <= n; ++j) f[i][j] = 1LL * f[i][j-1] * j % Mod;
    }
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1LL * fac[i-1] * i % Mod;
    // solve
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int now = 0;
        for (int j = 1; j <= n - i; ++j) {
            int s1 = 1LL * j * (n-j) % Mod;
            int s2 = 2LL * C[n-i][j] * fac[j] % Mod;
            now = (now + 1LL * s1 * s2 % Mod * f[i][n - j - 1] % Mod) % Mod;
        }
        ans = (ans + 1LL * fac[i] * now % Mod) % Mod;
    }
    // output
    printf("%d\n", ans);
    return 0;
}

「HAOI2018」染色

题目链接

https://loj.ac/problem/2527

解题思路

如果想到了二项式反演, 那么这道题还算套路吧…

~~可惜没有, 溜了溜了, 还在化卷积上浪费时间, 退役稳了~~

设 $f(x)$ 表示钦定 $x$ 种颜色出现 $S$ 次, $g(x)$ 表示恰好 $x$ 种颜色出现 $S$ 次.

记 $N = \min \{ m, \lfloor \dfrac{n}{S} \rfloor \}$, 那么答案即为

$\sum_{k=0}^N W_k \cdot g(k)$

先考虑如何计算 $f(x)$, 也就是在 $m$ 种颜色中挑出 $x$ 种出现 $S$ 次, 任意排列, 且不管其余位置的颜色, 那么可以得到

$f(x) = \binom{m}{x} \cdot \frac{n!}{(S!)^x \cdot (n-Sx)!} \cdot (m-x)^{n-Sx}$

(中间部分是一个多重集合的排列数, 为了方便就拆开了)

对于 $f(x)$ 和 $g(x)$, 有

$f(x) = \sum_{i=x}^N \binom{i}{x} g(i)$

二项式反演一通之后可以得到

$g(x) = \sum_{i=x}^N (-1) ^ {i-x} \binom{i}{x} f(i)$

把组合数展开, 得

$g(x) \cdot x! = \sum_{i=x}^N \frac{(-1)^{i-x}}{(i-x)!}\ i! \cdot f(i)$

接下来, 卷积登场. 记 $h(x) = \frac{(-1)^{N-x}}{(N-x)!}$, 那么

$g(x) \cdot x! = \sum_{i=x}^N h(N+x-i)\ i!\cdot f(i)$

用 NTT 优化计算即可. 时间复杂度 $O(n \log n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #2527
// DeP
#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;

const int MAXL = 1e7 + 5, MAXN = 1 << 19 | 1;
const int P = 1004535809, G = 3, iG = 334845270;

int fac[MAXL], ifac[MAXL];

inline int C(int n, int m) {
    return (n < m)? 0: 1LL * fac[n] * ifac[n-m] % P * ifac[m] % P;
}

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;
}

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 NTT(int* f, const int& Lim, const 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) {
            int unit = fpow(type > 0? G: iG, (P - 1) / (Mid << 1));
            for (int i = 0; i < Lim; i += Mid << 1) {
                int w = 1;
                for (int j = 0; j < Mid; ++j, w = 1LL * w * unit % P) {
                    int f0 = f[i+j], f1 = 1LL * w * f[i+j+Mid] % P;
                    f[i+j] = (f0 + f1) % P, f[i+j+Mid] = (f0 - f1 + P) % P;
                }
            }
        }
        if (type < 0) {
            int inv = fpow(Lim, P-2);
            for (int i = 0; i < Lim; ++i) f[i] = 1LL * f[i] * inv % P;
        }
    }
}

int n, m, S;
int A[MAXN], f[MAXN], g[MAXN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m), read(S);
    for (int i = 0; i <= m; ++i) read(A[i]);
    // init
    int N = max(max(n, m), S);
    ifac[0] = fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = 1LL * fac[i-1] * i % P;
    ifac[N] = fpow(fac[N], P-2);
    for (int i = N; i; --i) ifac[i-1] = 1LL * ifac[i] * i % P;
    // solve
    N = min(m, n / S);
    for (int i = 0; i <= N; ++i) {
        int s1 = 1LL * fac[n] * fpow(ifac[S], i) % P * ifac[n - S * i] % P;
        int s2 = 1LL * fpow(m - i, n - S * i) * fac[i] % P;
        f[i] = 1LL * C(m, i) * s1 % P * s2 % P;
    }
    for (int i = 0; i <= N; ++i) {
        g[i] = ifac[N - i];
        if ((N - i) & 1) g[i] = P - g[i];
    }
    int Lim = 1, L = 0;
    while (Lim <= N + N) Lim <<= 1, ++L;
    Poly::init(Lim, L), Poly::NTT(f, Lim, 1), Poly::NTT(g, Lim, 1);
    for (int i = 0; i < Lim; ++i) g[i] = 1LL * g[i] * f[i] % P;
    Poly::NTT(g, Lim, -1);
    // output
    int ans = 0;
    for (int i = 0; i <= N; ++i) ans = (ans + 1LL * g[i+N] * ifac[i] % P * A[i] % P) % P;
    printf("%d\n", ans);
    return 0;
}

DepletedPrism's Blog

HAOI 2018 大赏

「HAOI2018」奇怪的背包

题目链接

解题思路

代码实现

「HAOI2018」反色游戏

题目链接

解题思路

代码实现

「HAOI2018」字串覆盖

题目链接

解题思路

代码实现

「HAOI2018」苹果树

题目链接

解题思路

代码实现

「HAOI2018」染色

题目链接

解题思路

代码实现