2024--梦熊&太戈--NOIP十三连测 #7【订正】 - 比赛 - 梦熊联盟 (mna.wang)

总结

T1 基本和 CF1245F 相同。很快就写完了。

T2 题意特别难懂，模拟了很长时间后题意还是有些晕，就先放弃了。

T3 相较于 T2 看上去简单的多，先冲 T3。

特殊性质 \(A\) 有 \(50\) 分，这可能是正解的关键。尝试打表找规律无果。\(50\) 分实在是太多就意味着它和正解的难度是接近的。

这期间写了 \(n \le 2\) 的，本来想拿 \(10\) 分，结果 \(30\) 分？？？？？？？

T4 看起来也可做，打了 \(n \le 500\) 的，这是一个预处理前后缀的简单技巧。不知道 \(a_i \le 20\) 咋做。

给 T2 时间只有 20 分钟，感觉 \(30\) 分写不出来了，就没写。

总结：

1. 你没有做出 \(3\) 题或 \(4\) 题的实力。如果这两道题中存在一个部分分的分值很大（比如 T3 的 \(50\) 分）就不要死磕这档分。因为这实在太难。
2. 如果一个题的题意很复杂，先写根据题意写一个暴力（比如 T2 的 \(30\) 分）。写暴力的时候可以帮助你理解题意，而且写完之后关掉题面，照着暴力代码思考优化，可能会更方便些。
3. 非正解（部分分）的找规律时间不要太长。

A. pair

题意

求 \(\sum_{x=0}^N\sum_{y=0}^N [x\mid y = x \oplus y]\)。

\(N \le 2^{10^6}\)。

做法

注意到 \(x\mid y = x \oplus y\) 等价于 \(x \operatorname{and} y = 0\)。于是 CF1245F。

B. tree

不会。

C. mod

题意

给定长度为 \(n\) 的正整数序列 \(a\)，梦梦给出了以下函数：

void mod(int x){
	for(int i=1;i<=n;i++) a[i]=a[i]%x;
}

你可以执行这个函数任意次，且每次调用函数的参数可以任意指定，但要求调用的参数 \(x\) 为正整数，请问最终可以得到多少种不同的 \(a\) 序列。模 \(998244353\)。

性质 \(A\) 思路

每次操作选择的 \(x\) 一定越来越小。

对于初始的两个相邻的数 \(k,k+1\)，将它们模 \(x\) 后，它们要么仍相差 \(1\)（即变成 \(k \bmod x, k \bmod x + 1\)），或变成 \(x-1,0\)。

若再模一个 \(y\)，有可能仍相差 \(1\)，有可能变成 \(k \bmod x \bmod y,0\)。

也就是说如果最终能得到序列 \(a\)，且最后一次操作的数是 \(x\)，等价于：

• \(\forall 1 \le i \le n\)，\(0 \le a_i < x\)。

• \(a_1=1,a_2=2,\dots,a_{x-1}=x-1,a_x = 0\)；

• \(\forall x + 1 \le i \le n\)，\(a_i = 0\) 或 \(a_i = a_{i-1}+1\)。

枚举 \(x\)。然后 DP 即可。设 \(f(i, j)\) 表示考虑前 \(i\) 个位置且 \(a_i = j\) 的方案，转移极易。

此时你发现输出答案比标准答案少 \(1\)。这是因为你少考虑了一次操作都不进行的情况。

正解

不会。

D. divide

\(n \le 500\) 可以预处理前后缀的 DP 的答案。我的实现里预处理 \(n^2\)，求答案 \(n^3\)。

\(a_i \le 20\) 直接优化上一个 DP。因为长度 \(\ge 20\) 的区间一定合法。代码不太好写。

正解是神秘 cdq 优化 DP。不会。