P3761 [TJOI2017]城市

给定一棵带权树，你可以选择断掉任意一条边，然后加上一条边权相同的新边，让城市之间距离的最大值最小。

边数 $n\le 5000$ ，时间限制 $3000\ \text{ms}$ 。

看数据范围，可以用 $\Omicron(n^2)$ 算法。

先枚举断掉哪条边，然后最大值可能是下面这些情况之一：

1. 在同一个树中：求直径即可。
2. 经过新建的边，即一个在第一个树，另一个在第二个树。

考虑情况2，即在两个树中各选一个点，使得距离树中任意点的最大值最小。

dfs ，考虑点 $u$ 到树中任意点的最大值，有两种情况，1是经过父亲走下来，2是在自己的子树中。

1的话从传入一个参数 $d$ ，表示从父亲传下来的最大值，2的话已经在求直径时候求出了。

从 $u$ 转移到 $v$ ，假如 $u$ 的最长链是从 $v$ 接上来的，那么就不能把 $u$ 的最长链计入 $v$ 的 $d$ 中，否则就把 $u$ 的最长链计入 $v$ 的 $d$ 中，即 $d’=w + \max(d, f[u])$ 或者 $d'= w + \max(d,g[u])$ 。

提交记录

P5283 [十二省联考 2019] 异或粽子

给定一个序列 $a$ ，要选出 $k$ 组 $(l,r)$ ，使得 $\sum_{(l, r)} a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$ 最大。

不难发现可以用前缀和，令 $s_i = \sum_{j=0}^i a_i$ ，那么 $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r = s_r \oplus s_{l-1}$ 。

使用可持久化trie在 $\Omicron(\log n)$ 求出 $l\le p\le r$ ，使得 $s_p \oplus x$ 最大。

我们可以这么做（虽然这么做是对的，但我不理解为什么要这么做）：

可以用一个大根堆维护，$(x, j,i,l,r)$ 表示 $x=s_j\oplus x_i$ 所有可以选出的 $j, i$，还有 $j$ 可以选的范围 $[l, r]$ 。

每次取出最大的 $x$ ，计入答案，然后把 $[l, r]$ 分成两个区间 $[l, j-1], [j+1, r]$ ，在这两个区间中分别选出 $j_1, j_2$ 使得 $s_{j_1} \oplus s_i$ 和 $s_{j_2} \oplus s_i$ 最大，然后重新插入大根堆中。

提交记录

P4064 [JXOI2017]加法

给定一个序列 $A$ 和 $m$ 个区间 $[l_i, r_i]$ ，要选择 $k$ 个区间，对于每个区间执行一次区间加 $a$ （每个区间只能选择一次），最大化序列最小值。

最大化序列最小值，考虑用二分最小值，对于比这个值要小的 $A_i$ ，要选择若干个区间加 $a$ ，使之不比 $lim$ 小，那么用哪些区间呢？贪心地用右端点最远的区间覆盖，为什么？一个区间还没有被使用，说明在这个点左边并不需要这个区间，而用右端点最远的区间，有可能覆盖更多需要的 $A_i$ 。

提交记录

P4454 [CQOI2018]破解D-H协议

给定 $g, p, A, B$ ，满足 $A = g^a (\bmod p)$, $B = g^b (\bmod p)$ ，求 $g^{ab} (\bmod p)$ 。

显然求出 $a, b$ 之一即可。

考虑使用 BSGS 算法：

$b^x = n (\bmod p)$ ，已知 $b, n, p$ ，求 $x$ ：

令 $x = it-j$ ，其中 $t = \lceil\sqrt p\rceil, i \in [1, t], j \in [0, t)$ ，

那么

$$\begin{align*} b^x &=& n (\bmod p) \\ b^{it-j} &=& n (\bmod p) \\ (b^t)^i &=& n\cdot b^j (\bmod p) \\ \end{align*}$$

显然预处理出所有的 $n \cdot b^j$ ，存起来，然后枚举 $i$ 就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ll bsgs(ll b, int n)
{
    map<ll, int> mp;
    n %= P;
    ll t = sqrt(P) + 1;
    for (int i = 0; i < t; i++) mp[n * qpow(b, i) % P] = i;
    b = qpow(b, t);
    if (!b) return !n ? 1 : -1;
    for (int i = 1; i <= t; i++) {
        ll x = qpow(b, i);
        int j = mp.count(x) ? mp[x] : -1;
        if (~j && i * t - j >= 0) return i * t - j;
    }
    return -1;
}

提交记录

P4065 [JXOI2017]颜色

给定序列 $a_i$ ，问有多少种方案数使得删去若干种数字后，最后剩下来的序列非空且不断开（例如，对于 $1, 2, 3, 4, 5$ ，删去 $2, 3$ 之后，变成了 $1, \_, \_, 4, 5$ 不合法，若删去 $1$ ，变成 $2, 3, 4, 5$ 是合法方案）。

显然要在原序列中选择非空的一段，使得这段中的所有数字仅在这段中出现过。有两种解法。

解法一：

对于每个位置，赋一个随机的值 $b_i$，并且使得所有同个数字位置上的值的和为 $0$ （$\sum_{a_i=x} b_i = 0$） ，然后对于 $b_i$ 做前缀和 $s_i$，到每个位置 $i$ 统计之前有多少个 $j$ 有 $s_i = s_j$ ，加起来即可。

一种可能的赋值方案是：设 $c_x = \langle 1 \le i \le n: a_i=x \rangle$ ，那么 $1 \le j \lt |c_x|,\ b_i = \operatorname{rand}(), b_{|c_x|} = -\sum_{1\le j \lt |c_x|} b_j$ 。

解法二：

先枚举右端点，然后考虑有多少个合法的左端点。设颜色 $x$ 最小的位置为 $mn_x$ ，最大的位置为 $mx_x$ 。先考虑段中的所有颜色不能在左端点之左：枚举到颜色 $x$ 的 $mx_x$ 时，把线段树上 $mn_x+1 \cdots mx_x$ 设为 $1$ ，表示这些点不能成为左端点。再考虑段中的颜色不能再右端点之右，即若 $mx_x \gt r$ ，那么 $x$ 一定不能被选中，用栈维护所有的 $mx_x > r$ 的点，从左至右把每个的$i$ 压入栈，然后弹出所有 $mx_{a_i} \le r$ 的 $i$ ，然后此时的栈顶就是不能取到的左端点，即此时的左端点为 $l=\operatorname{top()} + 1$ ，答案为 $r-l+1-seg.\operatorname{query}(l\cdots r)$ 。

提交记录

P4782 【模板】2-SAT 问题

要解决一个 2-SAT 问题：有 $n$ 个布尔变量，$x_1 \cdots x_n$ ，和 $m$ 个条件，每个条件要求 $x_i=a \lor x_j = b$ ，问是否存在一种取值使得满足所有条件，求一种可能取值，或报告无解。

一个 k-SAT 问题就是有若干个布尔变量 $x_i$ ，和若干个条件，每个条件形如 $x_{a_1}=b_1 \lor \cdots \lor x_{a_k}=b_k$ ，问是否存在一组解满足所有条件。

若 $k \gt 2$ ，这问题已经被证明是 NP 完全的了，不存在多项式时间内的算法，但若 $k=2$ ，则有一种特殊的算法可以在 $\Omicron(n+m)$ 内解决。

考虑建出一个无向图，每条边都代表这一个「蕴含」限制，即若存在一条边从 $x$ 连向 $y$ ，那么就表示 $x\rarr y$ ，其的真值表如下：

不难发现，就是要求当 $x$ 为 1 时，$y$ 也要为 1 。

然后就是对这张图填 0 或 1，问是否存在方案，但你可能会说了：全填 0 或者全填 1 不久可以了吗，不要着急，接下来会介绍一些条件，有若干对点必须有且仅有一个点填 1。

我们把一个变量 $x$ 拆开来，变成 $\lnot x$ 和 $x$ ，对于限制 $a \lor b$ ，可以被拆成 $(\lnot a \rarr b )\land (\lnot b \rarr a)$ 。（正确性不难用真值表证明，此处略去）。

建成这张图后，进行缩点，显然在一个强连通分量内的点必须同选 0 或者 1，若 $\lnot x$ 和 $x$ 在同一个强连通分量内，就无解。

否则，一定有解，考虑对缩点后的图进行拓扑排序，若 $\lnot x$ 所在的强连通分量的拓扑序小于 $x$ 所在的强连通分量的拓扑序，则 $x=0$ ，否则 $x=1$ 。

你可能会问，假如出现这样的情况：$a \rarr \lnot a \rarr b \rarr \lnot b$ ，上面的方案不久不合法了吗？

实际上这种情况不会出现，$\lnot a \rarr b$ 原来是 $a \lor b$ ，还有一条边 $\lnot b \rarr a$ ，形成了一个强连通分量，不合法，类似情况同理可以证明不会出现。

实现细节：可以不用跑拓扑序，直接用 Tarjan 跑出来的强连通分量编号，其大的，拓扑序反而小。

提交记录

P4151 [WC2011]最大XOR和路径

给定一张无向图，有边权，求一条从 $1$ 到 $n$ 的路径，使得其边权异或和最大。

由于异或操作的良好性质，我们先钦定一条从 $1$ 到 $n$ 的路径，然后考虑往路径上面加环，显然我们从路径上某个点，走到环上的某个点，绕完整个环，再沿着同样的路走回来，只有那个环上的路径异或和会被计入答案，任意一条可能的路径都可以被表示为这样的形式。然后用线性基处理所有环异或起来的最大值即可。正确性可能不显然，感性理解一下。

提交记录

P3991 [BJOI2017]喷式水战改

有一个序列，初始为空，有若干个操作，会在序列中第 $p_i$ 个元素个元素后插入 $x_i$ 个第 $i$ 种元素，第 $i$ 种元素有属性 $a_i, b_i, c_i$ ，每次求这个序列的最大价值。

定义这种序列的价值是，你要这个序列分成四段子序列，每个子序列可能为空，第 1 个子序列和第 4 个子序列的价值是所有元素的 $a_i$ 之和，第 2 个子序列是 $b_i$ 之和，第 3 个子序列是 $c_i$ 之和，然后求和。

见到插入操作，考虑用平衡树维护，每个节点维护一段连续的相同种类的元素。

显然，对于每段连续的元素，因为每段可以为空，所以划分到一个子序列中是不劣的。

令 $f_u[i][j]$ 为以 $u$ 为根的节点，整棵子树代表的区间，左分到了第 $i$ （$0\cdots 3$） 个子序列，右分到了第 $j$ 个子序列的最大值，转移方程可以参照代码，每次 split 和 merge ，左右儿子变更时要更新一下。

另外，插入一个新的段的时候，有可能把原来的一段拆成了两端，具体实现较为繁琐。

提交记录

P4577 [FJOI2018] 领导集团问题

给定一棵树，求树上满足如下条件的大小最大的点集：

对于任意点集中的点 $i, j \in S, i \not= j$ ，若在原树中 $u$ 是 $v$ 的祖先，则 $w_u \le w_v$ 。

考虑序列上的LIS的做法，我们也可以叫这道题“树上LIS”。

对于每个节点 $u$ 维护一个序列 $f[u]$ ，其中 $f[u][i]$ 代表着在 $u$ 为根的子树内，所有选取 $i$ 个节点的方案 $T$ 中，$\min_{j\in T} w_j$ 的最大值。

节点 $u$ 的答案就是最大 $i$ ，使得 $f[u][i]$ 合法。

考虑合并所有的 $v \in son_u$ ，显然子树中的答案互相不影响，对于一个 $i$ ，可以贪心地选择出最大 $i$ 个。

考虑加入 $w_u$ ，仿照LIS的做法，从 $f[u]$ 中找出最小的 $i$ 使得 $w_i \ge w_u$ ，显然把 $w_i$ 换成 $w_u$ 不会使得答案更劣，即 $f[u][i] = w_u$ （正确性不太好理解）。

由于 $f[u]$ 有单调型，用 multiset 维护 $f[u]$ ，合并 $u$ 的儿子时启发式合并即可，用 lower_bound 找到 $w_i \ge w_u$ ，答案就是 $|f[1]|$ 。

提交记录

P4591 [TJOI2018]碱基序列

给定一个字符串 $s$ ，和若干组字符串 $t_{ij}$ ，问有多少组方案，从每组字符串中选择一个，首位拼接，能形成了 $s$ 的子串。

用 $f[i][j]$ 表示获得了匹配到 $s_i$ ，用了前 $j$ 组字符串的方案数。

$$f[i][j] = \sum_{1 \le k \le a_j, l} f[l-1][j-1]\cdot (s[l \cdots i] = t_{jk})$$

可以用哈希判断 $s[l\cdots i] = t_{jk}$ 。

提交记录

P3762 [TJOI2017]龙舟

给定 $b_i$ 和 $a_{ij}$ ，多次询问，给定 $x, M$ ，求 $\frac {b_1\times \cdots \times b_m} {a_{x1}\times \cdots \times a_{xm}} \bmod M$ ，不保证 $M \in \mathbb{P}$ 。

$M, a_{ij}, b_i \lt 2\times 10^{18}, m \le 10000, 询问数 \le 50$

先介绍两个科技算法：

一：$\mathcal{Miller\ Rabin}$ 素数判定。

对于一个很大的数 $n \lt 2\times 10^{18}$ ，判断是否是质数。

先筛掉唯一一个偶素数 $n = 2$ 。

首先会想到费马小定理，若 $n \in P$ ，对于任意的 $a \in [1, n-1]$ ，有：

$$a^{n-1} = 1 (\bmod n)$$

但是也有一些合数满足这个等式，我们需要更强的限制。

考虑二次探测，若 $n\in P, x < n$ ：

$$x^2 = 1 (\bmod p) \rArr x\in \{1,n-1\}$$

结合费马小定理：

$$a^{n-1} = (a^{\frac{n-1}2})^2 = 1(\bmod n) \Rarr a^{\frac{n-1}2}\in\{1,n-1\}$$

若 $a^{\frac{n-1}2}=1$ ，继续考虑 $a^{\frac{n-1}4},a^{\frac{n-1}8},\ldots$ 直到 $\frac {n-1} {2^k}$ 为奇数。

若有一个判断未通过，就肯定不是质数了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

typedef __int128_t lll;
lll Miller_Rabin(lll n)
{
    if (n == 2) return true;
    static const int TEST_TIME = 10;
    uniform_int_distribution<uint64_t> d(2, n - 1);
    for (int _ = 1; _ <= TEST_TIME; _++) {
        lll a = d(eng);
        if (qpow(a, n - 1, n) != 1) return false;
        lll p = n - 1;
        for (; !(p & 1); p /= 2) {
            lll x = qpow(a, p, n);
            if (x * x % n == 1 && x != 1 && x != n - 1) return false;
        }
    }
    return true;
}

二：$\mathcal{Pollar\ Rho}$ 算法：

Pollar Rho 算法就是快速找到大整数的一个非 1，非自己的因数算法。

先介绍生日悖论：若有23个人，他们的出生日期均匀分布，那么存在两个人生日相同的概率超过一半（这不难证明 $\frac{365}{365} \times \frac{364}{365} \times \cdots \frac{365-22}{365} \lt 1/2$ ）。

推广一下，若在 $[1, N]$ 之间均匀生成数，那么期望 $\Omicron(\sqrt n)$ 次后会生成重复的数。

考虑 $n$ 的最小因子 $1 \lt p \le \sqrt n$ ，期望随机生成 $\Omicron(n^{1/4})$ 个数后会出现模 $p$ 意义下相同的数，那么这两个数的差的绝对值 $d$ 满足 $\gcd(d, n) > 1$ ，可以直接返回 $\gcd(d, n)$ 。

但假如暴力判断的话，复杂度又回到 $\Omicron(n^{1/4}\ \log n)$ 的了。所以我们设计一种特殊的伪随机数生成器：

$$\langle 0, f(0), f(f(0))), f^3(0), \ldots\rangle,\ \text{let } f(x) = (x^2+c)\bmod N， c = \operatorname{randint}(1 \cdots n-1)$$

首先这个生成器会有一个问题，就是可能跳入一个循环出不来了，这时候我们需要换一个 $c$ 。

这里采用 Floyd 判环算法，伪代码如下：

$$\begin{align*} 1\ \ & x = f(0),\ y = f(f(0)) \\ 2\ \ & \operatorname{while}\ x \not= y \\ 3\ \ & \ \ \ \ \ \ \ \ \text{(Do something.)} \\ 4\ \ & \ \ \ \ \ \ \ \ x = f(x),\ y = f(f(y)) \\ 5\ \ & \operatorname{endwhile} \end{align*}$$

假如走到了一个环，$y$ 比 $x$ 更快，肯定会在环上某处相遇。

这样有什么好处呢？

$$|i - j| = 0 (\bmod p) \rArr |f(i)-f(j)| = |i^2-j^2| = |i-j|\cdot |i+j| = 0 (\bmod p)$$

说明

$$\exist i,\ j = f^d(i) \rarr |i-j| = 0 (\bmod p) \\ \Darr \\ \forall i,\ j = f^d(i) \rarr |i-j| = 0 (\bmod p) \\$$

我们每次可以验证所有「距离」为 $d$ 的点对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

lll Pollard_Rho(lll n)
{
    if (Miller_Rabin(n)) return -1;
    if (n == 4) return 2;
    uniform_int_distribution<uint64_t> d(1, n - 1);
    while (true) {
        lll c = d(eng);
        auto f = [c, n](lll y) { return (y * y % n + c) % n; };
        lll x = f(0), y = f(f(0));
        while (x != y) {
            lll z = gcd(abs(x - y), n);
            if (z > 1) return z;
            x = f(x), y = f(f(y));
        }
    }
}

为了表示方便，令 $c_i = a_{xi}$

由于一些取模的神秘原因（我不会，但不这么做不对），对于要处理的 $b_i$ 和 $c_i$ ，先消去共同的 $M$ 的质因数。

为了方便，对于 $x = t\cdot y^k$ ，定义 $\operatorname{cnt}(x,y)=k, \operatorname{left}(x,y)=t$ 。

$$x \in \mathbb{P} \land x|M,\ f_x = \sum_i \operatorname{cnt}(b_i, x) - \sum_i \operatorname{cnt}(a'_i, x) \\ \forall x \in \mathbb{P} \land x|M,\ b_i \larr \operatorname{left}(b_i, x) \\ \forall x \in \mathbb{P} \land x|M,\ c_i \larr \operatorname{left}(c_i, x) \\$$

若有 $f_x \lt 0$ ，那么无解。

然后答案就是

$$\frac {\prod_i b_i} {\prod_i c_i} \prod_i x^{f_x}$$

求逆元需要用欧拉定理算 $\varphi(M)$ 。

提交记录

P5304 [GXOI/GZOI2019]旅行者

给定一张有向图图，有若干个关键点，求所有关键点中距离最短的一对的距离。

$n, m \le 10^5$

每次选取两个点集 $A$ 和 $B$ ，以 $A$ 为起点，跑一边最短路，则 $\min_{b \in B} dis[B]$ 为 $\min_{a \in A, b \in B} \operatorname{dis}(a, b)$ 。

考虑目标点对 $a \not= b$ ， $a$ 中的一位二进制和 $b$ 中的一位二进制不相同，所以每次通过二进制上的某一位划分 $A$ 和 $B$ ，跑 $\log n$ 次最短路即可。

注意有向图，每次要从 $A$ 跑一次，从 $B$ 跑一次

提交记录

P3248 [HNOI2016]树

有一棵「模板树」，下称 树A 。

有一棵「大树」，下称 树B 。

最初，树B和树A是一样的。

每次操作，把树A中以某个点为根的子树复制到树B的某个点下（树A中的那个点成为新的树B的儿子），然后按在原树中的编号大小顺序重新标号。

然后若干次询问，每次询问两个点之间的距离。

询问树上的距离，常用的操作是lca+深度，这里也这么做。

考虑每次操作，形成一个新的「块」，所有的块构成了一棵树，我们维护这棵树上的深度和lca。

重新标号用主席树处理（以 $u$ 为根的子树中编号第 $i$ 小的节点，或者以 $u$ 为根的子树中 $x$ 第几小），在 $dfn$ 序列上做区间第 $k$ 小即可。

树A中的编号与树B中的编号极容易弄混，需要认真对待。

提交记录 (loj Ofast+少爷机就是好)

$n, m \le 10^5$

P3267 [JLOI2016/SHOI2016]侦察守卫

给定一棵树和若干个树上的点，每次可以在 $u$ 用 $w_u$ 的代价覆盖距离 $u$ 小于等于 $d$ 的点，求覆盖所有的关键点需要的最小代价。

对于每个点，设 $f[u][i]$ 表示还要满足还要向下覆盖 $i$ 层最小代价， $g[u][i]$ 表示可以向上覆盖 $i$ 层最小代价。

那么有，初始化

$g[u][0] = w[u]\cdot \operatorname{Important?}(u)$

$i\gt 1, g[u][i]=w[u]$

转移

$$f[u][i] = f'[u][i] + f[v][i - 1]\\ g[u][i] = \min(g[u][i] + f[v][i], f'[u][i + 1] + g[v][i+1])\\ g[u][i] = \min_{j>i}(g[u][i], g[u][j]\\ f[u][i] = \min_{j<i}(f[u][i], f[u][j]\\ f[0] = g[0]$$

（关于 $g[u][i] \leftarrow f'[u][i+1] + g[v][i+1]$ 的转移解释）

1
2
3
4
5
6
7
8
9
10

U 还能向上  D 还能向下

[u] (U i D i)
 +--------------------+          --- (Total: i+1)
 |                    |           |
[v] (U i+1)          [w] (D i-1)  |
                      .           |
                      .           |
                      .           |
                                 ---

提交记录

P3687 [ZJOI2017]仙人掌 题解

有一张图，问有多少种加边方案，使得加边后的图是一个仙人掌（一条边至多在一个简单环中）。

若最初的图不是仙人掌，返回 0 。

否则删去所有的环边，得到一个森林，考虑每棵树的情况。

对于每棵子树，强制选择其中的一个点可以向上连边（不连的情况就是其向它的父亲连一条重边），设为 $f[u]$

对于点 $u$ 考虑儿子 $v$ 中的所有向上连边的点，他们有两种方案：

1. 连向 $u$；
2. 连向其他的 $v$ 中的向上连边的点。

我们用 $h[i]$ 表示 $i$ 个点按以上方案连边的的方案数：

$$\begin{align*} h[i] &=& h[i-1] &\ \ \text{这个点连向} u \\ &+& (i-1)h[i-2] &\ \ \text{从剩下} i-1 \text{个点中选一个} \end{align*}$$

所以有

$$\begin{align*} f[u] &=& h[deg[u]] \prod_{v \in son[u]} f[v] & \ \ \text{选择} u \text{作为向上连边的点} \\ &+& \sum_{v} h[deg[u] - 1]\ f[v] \prod_{w \in son[u], w \not= v} f[w] & \ \ \text{选择} v \text{作为向上连边的点} \\ &=& h[deg[u] + 1] \prod_{v \in son[u]} f[v] \\ \end{align*}$$

但是对于根，由于不能选择其作为向上连边的点（为什么？仔细想一下，其不能向上连边，向下的情况都已经计算过了）。

所以

$$f[root] = h[deg[root]] \prod_{v \in son[root]} f[v]$$

提交记录

P3643 [APIO2016] 划艇

有若干个篮子，每个篮子要么不放东西，要么放 $[a_i, b_i]$ 个东西，且要大于之前所有篮子放东西的个数。

$n \le 500, a_i \le b_i \le 10^9$

由于 $a_i, b_i$ 非常大，考虑离散化，形成若干个区间 $[a'_i, b'_i)$ 。

考虑 $i$ 在区间 $j$ 内选择，$k$ 是第一个在区间 $j$ 之前选择的， $k+1 \cdots i$ 都在区间 $j$ 内选择，$1 \cdots k$ 都在区间 $1 \cdots j$ 内选择

令其的方案数为 $f[i][j]$ （强制 $i$ 选择， $k \lt i$ 随意）。

那么有 $f[i][j] = \sum_{k=0}^{i-1} \sum_{l\lt j} f[k][j]\ sum(k + 1, i)$

其中 $sum(k + 1, i)$ 为从 $k+1$ 到 $i$ 中，在区间 $j$ 内选择的方案数（如果无法满足就不选， $i$ 必须选）。

令 $c = cnt(j, k+1 \cdots i)$ ，即 $k + 1\cdots i$ 中可以取到区间 $j$ 的方案数，那么 $sum(k + 1, i) = {b'[j] - a'[j] + c - 1 \choose c}$

提交记录

P4139 上帝与集合的正确用法

求 $2^{2^{2^\cdots}} \bmod p$

有扩展欧拉定理，对于任意 $b \ge \varphi(p)$

$$a^b = a^{(b\ \bmod \varphi(p)) + \varphi(p)} (\bmod p)$$

显然 $2^{2^{2^\cdots}} >> \varphi(p)$

$$f(p) = \begin{cases} 0 & p=1 \\ 2^{f(\varphi(p)) + \varphi(p)}\ \bmod\ p & \text{otherwise} \end{cases}$$

P3750 [六省联考 2017] 分手是祝愿

给定一个 01 串，每次操作，给定一个 $i$ 翻转所有 $1 \le j \le i, j | i$ ，要让全为 $0$ 。

若当前能在 $k$ 步之内完成操作，则进行这个操作，否则随机进行一个操作，求期望。

$n \le 10^5$

首先考虑初始状态的最优策略，由于一个 $i$ 不会被 $j \lt i$ 修改，所以可以从大到小进行贪心操作，设这时的最少操作次数为 $c$ ，操作的顺序无关紧要。

考虑 dp ，令 $f[i]$ 表示当前可以最少恰好 $i$ 步完成操作的期望。

那么对于 $i \le k$ ，有 $f[i] = i$ 。

否则 $f[i] = \frac i n f[i-1] + \frac {n-i} n f[i + 1] + 1$ ，有 $\frac i n$ 的概率进行正确的操作，剩下 $\frac {n-i} n$ 的概率进行错误的操作，可以证明，至少需要再操作一次（按回来）。

对于 $f[i]$ 的转移，推式子，令 $f[i] = f[i-1]+b[i]$ :

$$\begin{align*} f[i] &=& \frac i n (f[i] - b[i]) + \frac {n-i} n (f[i] + b[i+1]) + 1 \\ 0 &=& -\frac i n b[i] + \frac {n-i} n b[i+1] + 1 \\ b[i] &=& \frac {(n-i)b[i+1] + n} i \\ \end{align*}$$

提交记录

P3270 [JLOI2016] 成绩比较

有 $n$ 个人，$m$ 门课 ，和一个人 $\mathcal{B 神}$ ，有 $k$ 个人的每门课的成绩都比B神低（小于等于），同时每门课有最高分 $U_i$ 最低分 $1$，B神的排名是 $R_i$ （有且仅有 $R_i - 1$ 个人分数大于B神），求满足以上情形的方案数。

考虑 dp 。

设 $f[i][j]$ 为考虑前 $i$ 个人，有 $j$ 个人每门课的分数都比 B 神低，那么有如下转移

$$f[i][j] = \sum_{k = j}^{n-1} f[i-1][k] {k \choose k-j} {n-k-1 \choose R_{i}-1-(k-j)} g[i]$$

其中 $g[i]$ 为对于第 $i$ 门课，选定有谁分数大于B神的情况下的方案数。

考虑这门课有谁的分数比 B神高，那么他就被从“比B神低”中除名了。

考虑上一次有 $k$ 个人，那么 $k \choose k-j$ 为从其中选出有多少人分数第一次比B神高，由于一共需要 $R_i - 1$ 个人，所以还要从已经比B神高的 $n-k-1$ 个人中选 $R_i - 1 - (k-j)$ 个人。

考虑怎么求 $g[i]$ ，枚举B神的分数 $j$ ，$R_i -1$ 个人分数在 $j+1 \cdots U_i$ 中，剩下 $n - R_i$ 个人分数在 $1 \cdots j$ 中：

$$g[i] = \sum_{j=1}^{U_i} (U_i - j)^{R_i - 1}\ j^{n - R_i}$$

因为 $U_i$ 很大，不能暴力求，发现 $g[i]$ 是一个关于 $U_i$ 的 $n$ 次（ $\sum x^n$ 为 $n+1$ 次多项式）多项式，即：

$$G(x) = \sum_{j = 1}^x (U_i - j)^{R_i - 1}\ j^{n - R_i}$$

用拉格朗日插值即可。

提交记录

P3746 [六省联考 2017] 组合数问题

求 $\sum_{i = 0}^\infin {nk \choose ik + r}$ ，其中 $n \le 10^9, r \lt k \le 50$ 。

也就是求 $\sum_{i\ \bmod\ k = r} {nk \choose i}$ 。

考虑二项式定理 ${nk \choose i} = [x^i](\sum_{i} {nk \choose i} x^i) = [x^i](1 + x)^{nk}$ 。

也就是要求 $\sum_{i\ \bmod\ k = r} [x^i](1 + x)^{nk}$ ，考虑使用循环卷积，把超过 $k$ 的项卷回去，即 $H(x) = \sum_{i = 0}^{k-1} \sum_{j = 0}^{k-1} [x^i]F(x)\cdot [x^j]G(x)\cdot x^{i+j \ \bmod \ k}$

对 $(1+x)^{nk}$ 使用循环卷积快速幂即可，最后答案就是求出来的 $x^r$ 的系数，时间复杂度 $\Omicron(k^2(\log nk))$

（注意当 $k = 1$ 时，初值是 $2$ ，不是 $1+x$ ）

提交记录

P4099 [HEOI2013]SAO

有 $n$ 个点，$n-1$ 个限制，对于每个限制，要求第 $i$ 个点要排在第 $j$ 个点之前或者之后，保证不存在两个点不相关（不能划分为两个点集 $A$, $B$, $\forall a \in A, b \in B, \text{无限制} (a, b)$ ），求排列方案数。

不考虑限制的顺序的话，这就是一棵树，我们考虑用树形 dp 来求。

令 $f[u][i]$ 为 $u$ 在已经处理的 $u$ 的子树内，排名为 $i$ 的方案数，每次就是要把 $f[v][k]$ 合并到 $f[u][i]$ 上。

先考虑 $v$ 要在 $u$ 之前求。

考虑 $v$ 中有 $j$ 个点要被放在 $u$ 之前，有 $j \ge k$ ，即必须让 $v$ 放在 $u$ 之前。（有一些问题，稍后讨论），

即

$$i = 1 \cdots siz[u], j = 0 \cdots siz[v] \\ f[u][i+j] \larr f'[u][i] {i + j - 1\choose j} {siz[u]-i + siz[v]-j \choose siz[v]-j} (\sum_{k=1}^j f[v][k])$$

其中 $siz[u]$ 为 $u$ 已经处理过的点数，$siz[v]$ 为 $v$ 的点数，${i + j - 1\choose j}$ 就是选前 $j$ 个要被放在哪些地方，$siz[u]-i + siz[v]-j \choose siz[v]-j$ 就是选后 $siz[v] - j$ 个要被放在哪些地方。

最后要 $siz[u] += siz[v]$ 。

假如 $v$ 要放在 $u$ 之后，也是同理：

$$f[u][i+j] \larr f'[u][i] {i + j - 1\choose j} {siz[u]-i + siz[v]-j \choose siz[v]-j} (\sum_{k=j+1}^{siz[v]} f[v][k])$$

现在有一个问题，为什么这么讨论是正确的：

每次插入时，$u$ 原先的排列和 $v$ 原先的排列中的相对顺序并没有改变，所以可以保证符合题目要求，同时也可以枚举到所有的相对位置的可能性（？？？我也不太懂，感性理解一下）。

（说一个可能会疑惑的点，考虑如下的：

1
2
3

v -> u
w -> v
w -> t

考虑 wtv 和 u ，这种情况是不能转移到 wvut 的，但是 wvut 是可以从 wvt 转移过去的）

提交记录

P1975[国家集训队]排队

给定一个数字串，每次交换两个位置，然后求逆序对个数。

设 $gt(l, r, x)$ 为 $l \cdots r$ 中大于 $x$ 的数的个数，$lt(l,r,x)$ 同理。

考虑交换 $l \lt r$ ，那么对于在 $l$ 之前或者 $r$ 之后的位置没有影响，而中间的贡献是 $-gt(l+1,r-1, a_r) + gt(l+1,r-1,a_l) - lt(l + 1, r - 1, a[l]) + gt(l + 1, r-1, a[r]) - [a_l > a_r] + [a_r > a_l]$ 。

考虑维护 $gt$ 和 $lt$ ，用线段树套平衡树，即线段树每个节点维护一个 FHQTreap 即可。

提交记录

P3702[SDOI2017]序列计数

求长为 $n$ ，每个数在 $1 \cdots m$ ，和为 $p$ 的倍数，且有一个数为质数的数列的方案数。

$n \le 10^9, m \le 2\times10^7,p\le100$

考虑使用模 $p$ 下的多项式，和容斥。

令 $[x^i]F_l(x)$ 为用 $1 \cdots m$ 组成长度为 $l$ ，和模 $p$ 为 $i$ 的方案数，$[x^i]G_l(x)$ 为用 $1 \cdots m$ 中的合数组成长度为 $l$ ，和模 $p$ 为 $i$ 的方案数。

那么答案就是 $[x^0]F_n(x) - [x^0]G_n(x)$ 。

考虑如何求 $F_l(x)$ 和 $G_l(x)$ 。

若 $l=1$ :

$$i\in [0, p-1], [x^i]F_l(x) = \sum_{j \in [1, m], j\ \bmod\ p = i} 1 \\ i\in [0, p-1], [x^i]G_l(x) = \sum_{j \in [1, m], j\ \bmod\ p = i, j \not \in \mathbb P} 1$$

否则，合并两个长度为 $a$ 和 $b$ 的数列，显然可以从两边选择任意一个数列，然后和相加即可。

考虑循环卷积，令 $l = a + b, a, b \lt l$：

$$F_l(x) = \sum_{i \in [0, p-1]} \sum_{j \in [0, p-1]} [x^i]F_a(x)\ [x^j]F_b(x)\ x^{(i + j)\ \bmod\ p}$$

然后用快速幂即可。

提交记录

P3760 [TJOI2017] 异或和

有一个序列 $a_i$ ，求

$$i, j \in [1, n], i \le j,\ \operatorname{xor} (\sum a[i \cdots j])$$

考虑计算所有可能的 $a[i \cdots j]$ 的个数，然后答案就是所有出现奇数次的数的异或和。

令 $f_x$ 为所有可能的 $a[i \cdots j]$ 中，$x$ 的出现次数。

令 $g_x$ 为前缀和 $a[1 \cdots i]$ 中 $x$ 的出现次数。

由于有 $a[i \cdots j] = a[1 \cdots j] - a[1 \cdots (j - 1)]$ ，所以有 $f_i = \sum_{j=0}^{m-i} g_jg_{i+j}$ 。( $m = a[1 \cdots n]$ )

考虑进行变换

$$\begin{align*} f_i &=& \sum_{j=0}^{m-i} g_jg_{i+j} & \\ f_{m-i'} &=& \sum_{j=0}^{i'} g_jg_{j+m-i'} & i \larr m - i'\\ f_{m-i'} &=& \sum_{j=0}^{i'} g_jg'_{i'-j} & g'_i \larr g_{m-i}\\ f_{i'} &=& \sum_{j=0}^{i'} g_jg'_{i'-j} & f'_i \larr f_{m-i}\\ \end{align*}$$

就可以卷积了。

提交记录

P3763[TJOI2017] DNA

有两个字符串 $S$ 和 $T$ ，问 $S$ 有多少个子串更改不超过 $3$ 个字符（长度不变）能和 $T$ 相同，其中 $S$ 和 $T$ 都由 A, T, C, G 四个字符组成。

分别考虑四个字符：

令上文中的 $S$ 为 $S^{(0)}$ ，$T$ 为 $T^{(0)}$ 。

设当前考虑的字符是 $ch$ ，那么 $S_i = [S^{(0)}_i = ch], T_i = [T^{(0)}_i = ch]$

令 $P_i$ 为 $S$ 以 $i$ 结尾，长度 $|T|$ 的子串只考虑这个字符的情况下的匹配个数：

$$\begin{align*} P_i &=& \sum_{j=0}^{m-1}T_j\ S_{i-(m-1)+j} &\\ P_i &=& \sum_{j=0}^{m-1}T'_{m-1-j}\ S_{i-(m-1)+j} & T_j = T'_{m-1-j}\\ P_i &=& \sum_{k+l=i} T'_l\ S_k & l = m-1-j,\ k = i+(m-1)+j,\ 并且不用考虑范围\\ \end{align*}$$