本文章由 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$ 子树上头。如果这个子树是满的，我们就暴力合并；否则，就要打标记。

留着之后写吧。

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

普通的莫队需要我们支持两个操作：加入或删除某点，同时计算贡献。通常，这两个操作的时间是常数或者对数的。

但是有的情况下，我们没法在比较好的时间内同时维护两个操作的贡献。比如说要用莫队求区间的最大值。加点是简单的，删点时我们发现没法知道新的最大值该是多少。

这时候我们就可以用回滚莫队来解决。

我们将询问离线，按照左端点的块编号为第一关键字，右端点升序为第二关键字来排序。此时我们的询问分为：

• 在一个块之内的。这种询问的块长小于等于 $B$，可以直接暴力

• 跨越多个块。由于左端点块编号相同，因此右端点单增。因此，对于右端点我们可以一直加点。但是左端点不一定单调，但是变化量是小于 $B$ 的。因此我们可以暴力把 $L$ 先移动到左端点，然后再回滚。

这里头我们第二个 $L$ 移动时，贡献单独来算，不影响整个的贡献。这样，我们就能快速实现回滚。

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

找了一堆关于 Finger tree 的 blog，但是根本看不下去，只看懂了大概的方法。于是我来说一下。

我们如果要维护一个数据结构，支持以下操作：

• 在头尾加入元素
• 求第 k 个元素

怎么快速做？

如果只有操作一，显然可以用双向链表完成。但是操作二就没法快速做了，寄！

平衡树！我们可以拿下标当主键，头尾加入相当于加入新数，操作二相当于第 k 大…… 然而平衡树常数太大，我卡你常！

那我们就要考虑考虑了……

想一想能不能用倍增做。

我们维护 prv 和 nxt，指向当前位置前后的第 $2^i$ 个位置。如果它们可以维护，操作二就可以对数做。

考虑在头加入，不会更改它后面任意的 nxt，只会更改 pre。一个数的 pre 如果是新头，就意味着它到新头的距离是 $2^i$。我们用旧头的 nxt 去跳，然后来更新。同时，我们可以简单地更新 nxt。

在尾加入是同理的。

于是我们就有了一个基于倍增的，常数应该小得多的实现。

…… 很好！但是，deque 做这些操作是 $O(1)$ 的！

所以我们要想办法做任意位置插入。

Finger tree 还是不会……但是感觉常数应该比这个大罢（心虚）。

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

A. 归回

题意

求 $x^2 - y^2 = m$ 的一组非负整数解，或判定无解。

解析

考虑到某个数的平方模四一定为 $0$ 或 $1$，那么两个数的平方差就一定是 $0, 1, 3$ 中其中一个，即不可能是 $2$。因此，$m\equiv 2 \pmod 4$ 时无解。

考虑接下来怎么构造解。首先，原式即 $(x + y)(x - y) = m$，即 $pq = m$，其中 $2\mid p + q$。

当 $2\nmid m$ 时，不难注意到一组合法解 $p = 1, q = n$，对应原始解 $x = (n + 1) / 2, y = (n - 1) / 2$。

当 $2\mid m$，即 $4\mid m$ 时（由前面无解限制），可以构造 $p = 2, q = n / 2$，因为 $2 \mid n / 2$。此时对应原始解 $x = n/4 + 1, y = n / 4 - 1$。

本题是二潘初等数论上搬下来的练习题，也用了一些处理平方的常用技巧（如模 $4$）。

预估难度：黄

标程

#include <iostream>
using namespace std;

int main (void)
{
	int t;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> t;
	while (t--) {
		long long n;
		
		cin >> n;
		if (n % 4 == 2) cout << "-1\n";
		else if (n % 2) cout << (n - 1) \/ 2 << ' ' << (n + 1) \/ 2 << '\n';
		else if (n % 4 == 0) cout << n \/ 4 + 1 << ' ' << n \/ 4 - 1 << '\n';
	}
	return 0;
}

B. 连续

题意

给定一个只包含 $1$ 和 $2$ 的序列，询问一个 $k$，求构造一个区间使得区间和为 $k$。

解析

只有 $1$ 和 $2$ 两个数是核心。若有一个区间和为 $k$ 且 $k\gt 2$，那么一定存在一个区间和为 $k - 2$。这是好构造的。如果这个和为 $k$ 的区间有一个端点值为 $2$，那么删掉它；否则，由于 $k\gt 2$，知两端点值均为 $1$，删掉它俩，得到和为 $k - 2$ 的区间。

于是我们就可以找出和为奇数和和为偶数的最大两区间，然后进行模拟，并预处理出答案。

无解当且仅当 $k$ 大于与 $k$ 奇偶性相同的最大区间和。

标程

#include <iostream>
using namespace std;
const int N = 1e6 + 10, K = 2 * N;
int f[2], z[N], sum[N], l[K], r[K];

void dfs (int x)
{
    if (x <= 2) return;
    if (z[l[x]] == 1 && z[r[x]] == 1) l[x - 2] = l[x] + 1, r[x - 2] = r[x] - 1, dfs (x - 2);
    else if (z[l[x]] == 2) l[x - 2] = l[x] + 1, r[x - 2] = r[x], dfs (x - 2);
    else l[x - 2] = l[x], r[x - 2] = r[x] - 1, dfs (x - 2);
}

int main (void)
{
    int n, q, lfi, rfi;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> z[i];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + z[i];
    for (lfi = 1; lfi <= n && z[lfi] == 2; lfi++);
    for (rfi = n; rfi >= 0 && z[rfi] == 2; rfi--);
    f[sum[n] & 1] = sum[n], l[sum[n]] = 1, r[sum[n]] = n;
    if (sum[n] - sum[lfi] > sum[rfi]) l[f[sum[n] & 1 ^ 1] = sum[n] - sum[lfi]] = lfi + 1, r[f[sum[n] & 1 ^ 1]] = n;
    else l[f[sum[n] & 1 ^ 1] = sum[rfi - 1]] = 1, r[f[sum[n] & 1 ^ 1]] = rfi - 1;
    dfs (f[0]), dfs (f[1]);
    while (q--) {
    	int k;
    	cin >> k;
    	if (k > f[k & 1]) cout << "-1 -1\n";
    	else cout << l[k] << ' ' << r[k] << '\n';
    }
    return 0;
}

C. 平方

题意

对于 $[l, r]$ 上每个数 $x$，求与它最近的完全平方数 $y$。若 $y$ 为奇，答案加上 $x$；否则答案减去 $x$。求最后答案。

解析

首先没有无解情况，因为两个相邻的完全平方数差为奇数。$(n + 1)^2 - n^2 = 2n + 1$。

我们将 $[n^2, (n+1)^2)$ 设做一个大区间。不难发现，$[n, n(n + 1)]$ 是离 $n^2$ 更近的，$(n(n+1), (n+1)^2)$ 是离 $(n+1)^2$ 更近的。如果从 $n = 1$ 开始划分区间，那么 $n^2$ 是奇数，$(n+1)^2$ 是偶数，如此交错。因而 $[n, n(n+1)]$ 区间贡献负，$(n(n+1),(n+1)^2)$ 贡献正。

巧妙之处在于，很难不注意到，每一个大区间的贡献抵消了。

现在我们就知道了怎么 $O(1)$ 算 $[1, x]$ 区间的答案。然后差分即可。

标程

#include <iostream>
#include <cmath>
using namespace std;
using i128 = __int128_t;
const i128 P = 1e9 + 7, i2 = (P + 1) \/ 2;

i128 solve (i128 x)
{
	i128 k = sqrtl (x), d = k * (k + 1), sign = k * k % 2 ? 1 : P - 1, s = min (x, d);
	i128 res = (k * k % P + s) % P * (s - k * k % P + 1) % P * i2 % P * sign % P;
	if (x <= d) return res;
	return (res + P - (d + 1 + x) % P * (x - d) % P * i2 % P * sign % P) % P;
}

signed main (void)
{
	int t;
	long long l, r;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> t;
	while (t--) {
		cin >> l >> r;
		cout << (long long) ((solve (r) + P - solve (l - 1)) % P) << '\n';
	}
	return 0;
}

D. 密码

题意

给定一系列由小写字母构成的字符串。设密钥为一个未知的小写字母的排列，定义加密过程表示在一个字符串上将每个字符替换为密钥中对应位置的字符。现已知每个字符串加密后的字典序排名，求构造一个可能的密钥。

解析

比较板的一道题。我们发现两个字符串字典序偏序，当且仅当其第一个不相同的字符偏序。那么就可以用拓扑排序构造出每个字符之间的关系。

这样建图有 $n^2$ 条边。我们考虑到，图上关系是传递的，因此我们可以只连接两个相邻字符串首个不同字母。

求 LCP 可以用哈希，没卡。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define fi first
#define se second
using namespace std;
using u64 = unsigned long long;
const int N = 1e6, S = 1e7;
const u64 base = 37, P = 1e9 + 7;
vector<u64> z[N];
string s[N];
char res[30];
int p[N], w[N], id[30], deg[30];
vector<int> e[30];

int lcp (int x, int y)
{
	int l = 0, r = min (s[x].length (), s[y].length ()), k = 0;
	while (l <= r) {
		int mid = (l + r) \/ 2;
		if (z[x][mid] == z[y][mid]) l = (k = mid) + 1;
		else r = mid - 1;
	}
	return k;
}

int main (void)
{
	int n, tst = 0;
	queue<int> q;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		int m = s[i].length ();
		z[i].reserve (m + 1);
		for (int j = 1; j <= m; j++) z[i][j] = (z[i][j - 1] * base + s[i][j - 1] - 'a' + 1) % P;
	}
	
	for (int i = 1; i <= n; i++) cin >> w[i], p[i] = i;
	sort (p + 1, p + n + 1, [](int x, int y) { return w[x] < w[y]; });
	for (int i = 2; i <= n; i++) {
		int k = lcp (p[i], p[i - 1]);
		if (k == s[p[i - 1]].length ()) continue;
		int c = s[p[i]][k] - 'a' + 1;
		e[s[p[i - 1]][k] - 'a' + 1].push_back (c), deg[c]++;
	}
	for (int i = 1; i <= 26; i++) if (!deg[i]) q.push (i);
	while (!q.empty ()) {
		int u = q.front (); q.pop ();
		id[++tst] = u;
		for (auto v : e[u]) if (!--deg[v]) q.push (v);
	}
	
	for (int i = 1; i <= 26; i++) res[id[i]] = 'a' + i - 1;
	puts (res + 1);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-13 19:41:42

本来是非常简单非常板子的题。。没想出来。希望是因为感冒的原因。。。

考虑某条链的情况，那么实际就是数距离某个点距离为 $k$ 的前后两个位置所有的点数。

考虑树上其实是一样的。某个点 $x$ 上头的答案，就是满足 $u$ 是起点或者终点，使得 $u$ 到 $x$ 的长度为 $w_x$，同时 $u$ 到另一个端点的路径必须包含 $x$。

考虑既然经过了 $u$，那么要么是起点在 $u$ 子树内，要么是终点。两种情况的贡献式都好推。这时候我们发现样例一都过不了，因为重了。什么情况会重？起点和终点都在 $x$ 的子树内，但是由于路径并不经过 $x$，或者是恰好对称，在 $x$ 处算了两次。这时候可以差分掉。对两个贡献，在 LCA 上减去一个，LCA 父亲上再减去一个，就好了。操你妈的我是超级无敌大唐氏。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-08 12:43:04

B

我们在 $(a, b), (a + k, b + k)$ 上加的同时会在 $(a, b + k), (a + k, b)$ 上加上二，也就是在模三的意义下减去一。

考虑差矩阵；那么问题就变成了让这个矩阵转化为零矩阵。由上面知道操作不会改变一行或者一列的和，所以我们检查和模三是否都为零即可。

C

很明显，我们如果已经从某点开始选，那么选到最近的满足和大于 $s$ 的最优，否则会浪费空间。

但是选择的顺序是不一定的。所以我们枚举一个排列，然后从头开始选一定最优。如果都不可行，就无解。

场上写出来了，但是输出方案那里纠结了一会（当时太久没写代码唐完了）结果最后写 B 去了，到最后也没再写，不然 $\Pi$ 不至于掉那么大。

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

如果质因数数量非常少，比如 $n \le 30$，那么我们就可以直接状压，把质因数是否出现压起来。设 $f(i, S, T)$ 表示前 $i$ 个人，一个选了状态 $j$，另一个选了 $k$ 的方案数。

很难不注意到刷表转移

$$ \begin{aligned} f(i, S \cup K_i, T) \gets f(i, S, T) \iff S\cup K_i \cap T = \arnothing \ f(i, S, T \cup K_i) \gets f(i, S, T) \iff T\cup K_i \cap S = \arnothing \end{aligned} $$

但是问题来了，$n \le 500$，我们连这玩意儿压都压不起来。

很难不注意到，一个数 $x$ 大于 $\sqrt x$ 的质因数最多只有一个。我们要让两个集合所选的质因数交空，实际上就是保证小因子交空的前提下，让大因子不同。

我们可以把每一个数分解，然后按大因子排序，也就是把相同的一段放在了一起。

这个大因子只有三种可能：给 $S$，给 $T$ 和都不给。

设 $g(i, S, T)$ 表示这个大因子不在 $T$ 中的方案数，也就是可以在 $S$ 中的方案数，那么 $g$ 的转移是类似的；同理，我们可以算出可能在 $T$ 中的方案数。

合并解时候，要容斥掉一个 $f(i, S, T)$，因为 $g$ 和 $h$ 都可以表示都不给的情况。

之前想过质因子状压的 idea，但是正是因为会让值域太小而没想到解决方案。这题真的不错。

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

很多数数题听是听懂了，写也写完了，但是自己想是绝对想不出来的。

所以整理一下

错排

考虑 $f(i)$ 表示 $1$ 到 $n$ 的排列中错排的数量，那么对于第 $i$ 个数，我们要把它插入到前面 $1$ 到 $i - 1$ 个数中。

可以把它放到 $f(i - 1)$ 中的里，这是 $(i - 1) f(i - 1)$ 种方案；

也可以把它放到一个缺一错排里，也就是只有一个 $i$ 满足 $a_i = i$，这个的方案数是 $(i - 1)f(i - 2)$。

最终的转移就是 $f(i) = (i - 1)(f(i - 1) + f(i - 2))$。