本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-29 20:27:41

P2371 为例。

我们可以取一个数 $m \in A$，然后设 $f(k)$ 表示模 $m$ 为 $k$ 时整个式子最小值。

明显有 $x$ 可以转移到 $(x + a_i) \bmod m$，权是 $a_i$。由于有后效性，我们不能直接转移，考虑最短路就可以跑出来。

然后我们可以把 $[l, r]$ 差分成 $[1, r] \cap [1, l - 1]$ 来统计答案。考虑怎么统计 $[1, x]$ 的答案。如果 $f(i) \le x$，那么我们可以把 $f(i)$ 加上任意个 $x$。所以解的数量就是 $\dfrac{x - f(i) + 1}{x} + 1$。

然后统计就行了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-30 09:33:16

我们考虑到当序列中数互不相同时，交换任意两个数都会使逆序对的奇偶性变化。若 $a_i \lt a_j, i\lt j$ 交换，那么交换后逆序对数量加一；否则，逆序对数量会减一。

因此我们可以考虑把操作一和二转化为交换操作。

二操作其实可以转化为交换区间 $[l, r]$ 和 $[r + 1, k]$。

我们考虑一操作。

我们发现，$[l_1, r_2]$ 以外的部分，是不会受到影响的，因为只是这个区间之内的相对位置发生了改变。

具体来说，$[l_1, r_1]$，$[r_1 + 1, l_2 - 1]$ 和 $[l_2, r_2]$ 内部的逆序对也没有变化。

因此，实际上我们进行的操作就是把这几个区间之内的数按序交换。交换的总数是 $L_1L_2 + L_1L_3 + L_2L_3$，其中 $L$ 是每个区间的长度。

三四操作是显然的。

因此我们判断它的奇偶性，这个题就做完了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-31 20:15:28

还是非常有意思的组合题。

我们知道一条路径的长度是不大于 $\log n$ 的，也就是说这条路径上有最多 $\log n$ 个点。

由于这是一个伪二分查找，所以说每个点上的数与要找的 $x$ 的关系是确定的。不妨设 $L$ 表示小于 $x$ 的数的数，也即向右拐，$R$ 是向左拐的数量，以及 $E$ 是相等的数量，显然 $E$ 不大于一（这里直接搬了题解的符号）。

我们考虑确定的 $L$、$R$ 和 $E$ 对应多少个序列，也就是算一个固定的 $y$ 对答案的贡献。

考虑 $y \lt x$，因为 $y \gt x$ 的情况是对称的。（越来越像题解了）

首先 $y$ 有 $L$ 种选法，然后剩下的 $L - 1$ 个链上的位置有 $x - 2\choose L - 1$，并乘上排列；同样的，$R$ 的方案是 $n - x\choose R$，同样乘排列。剩下的位置任选，乘上排列是 $(n - L - R - E)!$。最终，一个 $y\lt x$ 对答案的贡献是

$$ yL {x - 2\choose L - 1} \bigg(L-1\bigg)! {n - x\choose R} R!\bigg(n - L - R - E\bigg)! $$

对于 $y\gt x$，贡献是

$$ yR {n-x-1\choose R-1}\bigg(R-1\bigg)!{x-1\choose L}L!\bigg(n - L - R - E\bigg)! $$

对于 $y = x$，贡献是

$$ xn{x-1\choose L}L!{n-x\choose R}R!(n-L-R-E-1)! $$

（好像是吧）。

确定了 $x$、$L$、$R$ 和 $E$，这串东西就可以 $O(1)$ 出。

$x$ 是询问给出的，我们现在的目的就是怎么快速得出后三者。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-01 21:24:40

首先发现这个过程很类似埃筛，每个数把它的所有倍数筛掉。

然后可以知道，有的数字是不能被其他数字筛掉的，比如任何质数都不可能被其他数筛掉。当然，这只是个充分不必要条件。

可以把这些不能被别的数筛掉的数，叫做唐数。

然后发现 $t(p)$ 本质上就是 $p$ 排列中最后面的那个唐数的位置。

我们可以考虑枚举这个最后的位置，然后来算贡献。

设 $w$ 表示唐数的数量，这可以用类似筛法的东西 $O(n\lg\lg n)$ 预处理出来。

枚举这个最后的位置 $x$：

它本身肯定要选一个唐数，方案数是 $w$；

后面一个唐数也不能选，也就是把剩下的 $n - w$ 个不同的数分配给 $n - w$ 个位置，所以方案数是 ${n-x\choose n-w} (n-w)!$；

前面是任意选的，方案数是 $(x - 1)!$

所以一个 $x$ 的贡献是

$$xw{n-x\choose n-w}(n-w)!(x-1)!$$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 14:26:58

很难不设状态 $f(i, j)$ 表示前 $i$ 个数，已经选的和是 $j$ 的最少代价，那么很难不注意到显然的转移

$$f(i, j) = \min\limits_{k=0}^j f(i - 1, j - k) + w(k)$$

其中，$w(k)$ 是比 $k$ 大的数的数量。很难不做到 $O(nm^2)$

然后考虑优化。

很难发现

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 16:03:14

要求一堆形如

$$x \equiv k_i\pmod {p_i}$$

的同余方程的解。

设 $P = \prod p$，则

$$x = \sum k_i \dfrac P {p_i} (\dfrac P {p_i})^{-1} \bmod P$$

其中这里的逆元是模 $p_i$ 意义下的。

考虑为什么。

不难发现，对于第 $i$ 个同余方程，对于 $i \ne j$ 都有 $P/p_j \equiv 0 \pmod {p_i}$，因为里头本来就有个 $p_i$。

于是式子就剩下了当前这一项。而 $P/p_i$ 乘上其模 $p_i$ 意义下的逆元本身就是一，于是就剩下了 $k_i$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 20:51:14

exCRT 的核心就是合并两个同余方程的解。

考虑

$$ \begin{cases} x \equiv w_i \pmod {p_i} \ x \equiv w_j \pmod {p_j} \end{cases} $$

那么有

$$x = p_ik_i + w_i = p_jk_j + w_j$$

这时候可以用扩欧解出来 $k_i$ 和 $k_j$，以此还原出 $x$，然后继续合并。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-03 19:27:33

首先如果没有第一个限制，方案数是 $n + k - 1\choose n$，也就是隔板法。

然后考虑第二个限制。实际上，就是要求 $a_{n-1} + a_n \le k + 1$。

考虑固定 $a_n$。这时 $a_{n-1}$ 最多选 $\min(a_n, k + 1 - a_{n})$。于是方案数用隔板可以算，不写了。

然后我们的组合数有一个性质，即

$$ \sum\limits_{i=l}^r {i\choose k} = {r+1\choose k + 1} - {l\choose k + 1} $$

我不太会证。。。

然后套下就出来了。比较厉害。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-06 19:08:23

题解里头似乎没有离线的做法。实际上，用离线来做，不仅更快，而且更好写。

题意即求

$$ \begin{cases} x-\dfrac yz = n!\ \dfrac {x-y} z = (n-1)! \ x\ge 0, z \ge 1 \end{cases} $$

的 $(x, y, z)$ 数量。

前两式相减，消去 $\dfrac y z$，得到

$$ \dfrac {x(z-1)}z = (n-1)!(n-1) $$

当 $z = 1$ 时，代入原式发现 $n! = (n-1)!$，即 $n = 1$，于是 $n = 1$ 时有无数解。

当 $z \gt 1$ 时，

$$ x = (n-1)!(n-1) \dfrac z{z-1} $$

于是 $z - 1$ 是 $(n-1)!(n-1)$ 的因子。由于这个条件是充要的，所以原方程的解数就是右式的因子数。

显然这玩意儿没法直接算。但我们知道，一个数的因子数，就是它唯一分解后质因子指数的任意组合，也即 $\prod (\lpha_i+1)$。

于是现在的问题，就转化为怎么快速做出 $T$ 个 $n$ 的 $(n - 1)!(n-1)$ 的每个质因子的指数。

对于单个 $n$，我们可以枚举 $i$ 从 $2$ 到 $n - 1$，动态维护一个答案 $p$，表示从 $1$ 到 $i - 1$ 的 $\prod (\lpha_i + 1)$。显然的，我们分解出 $i$ 后，它对于 $p$ 的贡献是 $\dfrac {\lpha'_i+\lpha_i+1}{\lpha'_i+1}$（其中 $\lpha'_i$ 表示前 $i - 1$ 个数分解出来的这一位上的指数）。由于是模意义，除法改用逆元。

但本题单单是根号分解就已经过不去了。

可以考虑线性筛筛出每个数的最小质因子，然后从最小质因子开始做分解；于是，复杂度从根号降到对数。

这样，我们就知道了怎么在 $O(n\log n)$ 时间内算出一个 $n$ 的答案。

下面考虑对于 $T$ 个 $n$，怎么快速进行计算。

非常显然地，对于 $n \le m$，那么对 $n$ 进行的计算，是被包含在对 $m$ 进行的计算中的。也就是说，如果我们暴力按刚才的方法，以 $O(Tn\log n)$ 时间来算，实际上会进行许多无用功。

于是我们可以考虑离线，然后排序，这样就可以消除无用的计算。维护一个 $u$ 表示下一个要分解的数，于是就可以 $n + T\log n$ 计算出所有询问的答案。

代码实现很简单。

#include <iostream>
#include <algorithm>
#include <bitset>
#define fi first
#define se second
#define int long long
using namespace std;
using pi = pair<int, int>;
const int N = 1e6 + 10, P = 998244353;
int mn[N], primes[N], res[N], s[N], inv[N], nr = 0;
pi z[N];

\/\/ 线性筛求最小质因子
void sieve (int n)
{
	for (int i = 2; i <= n; i++) {
		if (!mn[i]) ++nr, mn[primes[nr] = i] = nr;
		for (int j = 1; primes[j] * i <= n; j++) {
			mn[i * primes[j]] = j;
			if (i % primes[j] == 0) break;
		}
	}
}

signed main (void)
{
	int m;
	
	cin.tie (0)->sync_with_stdio (false);
	\/\/ 离线并开筛
	cin >> m;
	for (int i = 1; i <= m; i++) cin >> z[i].fi, --z[i].fi, z[i].se = i;
	sort (z + 1, z + m + 1), sieve (z[m].fi);
	
	\/\/ 线性预处理逆元
	inv[1] = 1;
	for (int i = 2; i <= z[m].fi; i++) inv[i] = (P - P \/ i) * inv[P % i] % P;
	
	int i = 1, ans = 1;
	
	\/\/ 特判无解情况
	while (!z[i].fi && i <= m) res[z[i++].se] = -1;
	for (int u = 2; i <= m; i++) {
		\/\/ 筛掉 (n - 1)! 中的质因子，并动态维护 ans
		for (; u <= z[i].fi; u++) {
			int v = u;
			while (v > 1) {
				int w = mn[v], cnt = 0;
				while (v % primes[w] == 0) v \/= primes[w], cnt++;
				ans = ans * inv[s[w] + 1] % P * (s[w] + cnt + 1) % P, s[w] += cnt;
			}
		}
		
		\/\/ 筛 (n - 1) 项，更新到当前询问的 ans 上
		int prod = ans, val = z[i].fi;
		while (val > 1) {
			int w = mn[val], cnt = 0;
			while (val % primes[w] == 0) val \/= primes[w], cnt++;
			prod = prod * inv[s[w] + 1] % P * (s[w] + cnt + 1) % P;
		}
		res[z[i].se] = prod;
	}
	
	for (int i = 1; i <= m; i++)
		if (res[i] == -1) cout << "inf\n";
		else cout << res[i] << '\n';
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-11 20:34:46

我们考虑异或操作怎么做。

显然的，放到 Trie 上头按位考虑，那么实际上就是交换了每一个 $x$ 为一的位对应的子树，打标记就可以了。

这个标记需要存储的是所异或的 $x$，并且在每次 push_down 时，要一直下放整条链。

注意到 $A$ 与 $B$，等于 $\overline A$ 或上 $\overline B$ 的补，也就是只要有一个位置为零，这一位就是零。所以我们就解决或操作就好了。

或上 $x$，就是说如果某一位 $x$ 为一，这一位对应的 $0$ 子树就要合并到 $1$ 子树上头。如果这个子树是满的，我们就暴力合并；否则，就要打标记。

留着之后写吧。