MOCK quasi-PTS 20221214 日志

NOIP+？准省选难度？已经到了能力的边缘么？

但有点奇怪的是，这三道题的思考方向全部正确，T1 甚至只差临门一脚了；可惜部分分给得不那么让人舒服。

另外，这种“为了卡常而卡常”的时间限制着实令人不适；尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。

简略题解

A – 种花

易得 $\newcommand\bigO{\operatorname{O}}\bigO(n)$ 计数 DP：记 $f(x)$ 表示以 $x$ 作为最后一个正方形的右边界的权值总和。则 $$f(x)=\begin{cases}0,&\text{if }x\text{ is banned}\\\sum_{y=0}^{x-1}f(y)(x-y)^2&\text{otherwise}\end{cases}$$

但其贡献并非线性，不能处理 $n$ 过大的情况。考虑其组合意义：令由边界 $x_1,x_2\ (0\leq x_1<x_2\leq n)$ 划分出的正方形占领了 $(x_1,x_2]$ 内的整点。则对于一个确定的划分方案，我们在每个正方形占领的区间内择取有序点对 $\langle a, b\rangle$，权值和就是择取方案乘积。那么有以下计数方式：设 $g(x,b)\ (b\in\{0,1,2\})$ 为考虑了点 $0\sim x$，且第 $x+1$ 个点所在的正方形已经择取有序点对中的 $b$ 个元素的方案数。易得转移是线性的，用矩阵快速幂优化即可。单次询问可以做到 $\bigO(27\log n)$。

（以上计数方式和 ABC277G – Random Walk to Millionaire 的组合解法如出一辙。）

常数优化

• 矩乘循环展开，非必要不取模。对于 $n$ 阶矩阵的乘法（$n$ 为常数），在每一层循环前使用 #pragma GCC unroll n ，编译器帮你展开，减少代码量。
• 采用 $\bigO(1)$ 光速幂。具体地，我们将指数 $b$ 拆分成 $aGQ+bQ+c\ (0\leq b\le G,0\leq c\le Q)$ 的形式，预处理出 $\mathbf{B}^{k},\mathbf{B}^{kQ},\mathbf{B}^{kGQ}$ 即可。于是总时间复杂度 $\bigO(3\times 27n)$。
• 至于为什么要拆成三个系数——考虑 L1, L2 高速缓存只有不到 $512 \text{KB}$。如果采用 $\bigO(\sqrt{n})$ 的分块，难以卡进；采用 $Q=G=1024$ 更快。

B – 喵了个喵

为什么输入法有本题名称的自动补全？！

通过 $a_i\in \{1,2\}$ 可以发现，如果在该限制条件下，我们能够快速判定一段区间能否只留下 $2$，那么可以用 $\bigO(\log n)$ 的代价将原问题转化为判定性问题：二分答案 $\text{mid}$，$a_i$ 大于其则为 $2$，反之为 $1$。

具体的判定方法和简要证明在这里（是为 AGC022E – Median Replace 的题解）。

题解所述的栈的状态转化具有结合律，故而我们整体二分，每一轮维护线段树作扫描线，按 $a_i$ 从小到大的顺序转换“转化数组”并回答询问即可。

常数优化

• 循环展开。
• 使用 zkw 线段树。
• 使用模拟链表而非 vector，尤其是开设 $\bigO(n)$ 个 vector 且每次用基于范围的 for 循环遍历的懒人操作。迭代器的操作没有我们想象的快；用完的空间也不会自动释放，可能造成严重的内存碎片化。

C – 建造军营

好题？屌题！ AGC058D – Yet Another ABC String

式子如此晦涩、限制如此复杂。它所谓的“组合意义”是遥不可及的幻光，可感而不可知，可遇而不可求。除非灵光乍现、思如泉涌，还是不要强求为好。

而做“代数推导”酷似在雾气氤氲中横渡巨江。纵使波涛汹涌、寒气入骨，总显得真切可感、坚定笃实。即便轻舟慢桨，也能徐徐摇到彼岸。

当然，我能够翻到的所有题解全是一句“考虑它的组合意义……”发语，然后寥寥数语收尾，代码的晦涩却又跟语言的简洁成鲜明的对比。我可没有这么做的资质。

AtCoder AGC058D – Yet Another ABC String – 题解

常数优化

从宋佳兴学长的代码学来的。

• 使用无符号数。
• 将上述式子拆分成阶乘、阶乘的逆和 $-2$ 的 $t$ 次方之积的形式，除 $(2n-3t)$ 以外全部预处理。使用指针遍历数组，不需要每次计算地址。
• 减少取模次数。不难想到使用 __uint128_t，计算的中间过程可只取一次模（$2^{128}\geq 3.4\times 10^{38}$），但千万注意它作为一个非原生数据类型，取余是非常非常慢的。故而我们只用其累加答案，任何取模操作都应强转成 uint64_t 进行。最优解决方案之一是将上式转化成 $6$ 个因数之积，中间在 uint64_t 意义下取 $2$ 次模，累加到 __uint128_t 上时为 $10^{36}$ 级别；随后每 $340$ 次对其取模。

结果是非常震撼的：我们进行 $6\times 10^8$ 次取余操作，（开启 O2 时）在 CWOI 上只用了 $\text{800ms}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

#define inl __always_inline
using ull = unsigned long long;
using ulll = __uint128_t;
using uint = unsigned;

constexpr uint N = 1e6 + 10, G = 3e6 + 10, P = 998244353, inv2 = P+1>>1;
uint a, b, c, lmt, n, T;
uint tco[N], fact[G], finv[N], powm2[N]; ulll ans;

inl ull fpow (ull a, ull b, int mod = P) {
	ull res = 1; a %= mod;
	for (; b; b >>= 1) {
		if (b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
	}
	return res;
}
inl void calc_inv () {
	fact[0] = powm2[0] = 1;
	for (ull x = 1; x < G; ++x)
		fact[x] = fact[x-1] * x % P;
	for (ull x = 1; x < N; ++x)
		powm2[x] = powm2[x-1] * (P-2ull) % P;
	finv[N-1] = fpow (fact[N-1], P - 2);
	for (uint x = N-2; ~x; --x)
		finv[x] = finv[x+1] * (x + 1ull) % P;
	for (ull x = 0, powm2 = 1; x < N; ++x, (powm2 *= P-2) %= P)
		tco[x] = finv[x] * powm2 % P;
}

int main () {
	/*  */
calc_inv (); scanf ("%u", &T);
while (T--) {
	scanf ("%u%u%u", &a, &b, &c); ans = 0;
	lmt = min ({ a, b, c }) + 1, n = a + b + c;
	ull t = 0, co = n<<1;
	const uint *pt1 = fact + n-1, *pt3 = tco,
		*pt4 = finv + a, *pt5 = finv + b, *pt6 = finv + c;
	while (t <= lmt) {
		uint cnt = min (lmt-t+1ull, 340ull);
		while (cnt--)
			ans += (ulll) ((ull) *pt1 * *pt6) * (co
				* *pt3 % P) * ((ull) *pt4 * *pt5 % P),
			++t, pt1 -= 2, ++pt3, --pt4, --pt5, --pt6, co -= 3;
		ans %= P;
	}
	printf ("%llu\n", (ull) ans % P * inv2 % P);
}

	return 0;
}