「比赛总结」洛谷 10 月赛
洛谷 2020 年 10 月 月赛 有两道期望题分数拿的还不错 .
Pro. A
给出一张无向图，从任意一点出发，规定每条边只能经过一次（正向 反向都算一次）。求最长的合法路径长度。
考虑每次经过一个点 x ，就会使点 x 的可用度数减 2 。如果走到一个合法度数为 0 的点，那么路径终止。要求是求最长路径长度，那么显然应该以此减少每个点的可用度数。每个点的初始度数为 n - 1。特殊考虑有偶数个点的完全图，初始度数为奇数，那么最后一次仍然可以走一步到达一个点。 \[\begin{equation*}\frac{n-1}{2} \times n + [n\ \texttt{mod}\ 2\ =\ 0]\end{equation*}\]
code
# python3
T = int(input())
for i in range(T):
now = int(input())
print((now - 1) // 2 * now + ((now & 1) ^ 1))Pro. B
总共有 \(n\) 条带 「圣盾」的「胖头鱼」和 \(m\) 条不带圣盾的胖头鱼，每次等概率对一条存活的胖头鱼造成「剧毒」伤害。 现在 Amazing John 想知道，期望造成多少次伤害可以杀死全部胖头鱼？
答案对 \(998244353\) 取模。
- 「圣盾」：当拥有圣盾的胖头鱼受到伤害时，免疫这条鱼所受到的本次伤害。免疫伤害后，圣盾被破坏。
- 「胖头鱼」：在一条胖头鱼的圣盾被破坏后，给予其他所有没有死亡且没有圣盾的胖头鱼圣盾。
- 「剧毒」：立即杀死没有圣盾的胖头鱼。
本题共有 \(20\) 个数据点，数据点从 \(1\) 到 \(20\) 编号。对于一个子任务，只有通过其中所有数据点才能获得该子任务的分数。
| 子任务 | 数据点 | 数据范围 | 分数 |
|---|---|---|---|
| \(1\) | \(1\sim3\) | \(n,m≤5×10^3\) | \(15\) |
| \(2\) | \(4\sim5\) | \(n≤10^6，m=0\) | \(10\) |
| \(3\) | \(6\sim10\) | \(n,m≤10^6\) | \(25\) |
| \(4\) | \(11\sim14\) | \(n≤10^{14}，m=0\) | \(20\) |
| \(5\) | \(15\sim20\) | \(n≤10^{14}，m≤10^6\) | \(30\) |
为描述方便，使用 0 代表无圣盾的胖头鱼， 1 代表有圣盾的胖头鱼。即，局面可以使用一串 0-1 串表示。
考虑一个局面：有 n 个 0 ， m 个 1（000000000000011111111）。 - 如果一次操作作用在 0 上，那么会使其死亡 局面变成有（n - 1）个 0， m 个 1。其概率为 \(\frac{n}{n + m}\)。 - 如果一次操作作用在 1 上，那么会使其死亡 局面变成有 1 个 0， (n + m) 个 1。其概率为 \(\frac{m}{n + m}\)。 设: 一个局面的期望结束操作步数函数为 \(f(n, m)\) 。特殊的，设 有 n 个 1 的局面的期望奇数操作步数函数\(\operatorname{g}(n) = \operatorname{f}(0, n)\)
易知： \[\operatorname{f}(n, m) = 1 + \frac{n}{n + m}\times\operatorname{f}(n - 1, m) + \frac{m}{n + m}\times[\ \operatorname{g}(n + m) - 1\ ]\]
\[\operatorname{g}(n) = 2 + \frac{1}{n}\times\operatorname{g}(n - 1) + \frac{n - 1}{n}\times[\ \operatorname{g}(n) - 1\ ]\]
化简得
\[\operatorname{g}(n) = \frac{n \times (n + 1)}{2} + n\]
最后答案就是 \(\operatorname{f}(n, m)\), 递归求解即可。
code
#define int long long
int inv(int x) { x %= MOD; int a = x, b = MOD - 2, ans = 1; while(b) { if(b & 1) ans = (ans *1ll* a) % MOD; a = (a *1ll* a) % MOD; b >>= 1; } return ans; }
int f(int n) { n %= MOD; return ((n) *1ll* (n + 1) % MOD * inv(2) % MOD + n) % MOD; }
int g(int n) { return (f(n) - 1 + MOD )% MOD; }
int doit(int n, int m){
if(m <= 0) return f(n);
return (((n % MOD) * inv(n + m) % MOD) * g(n + m) % MOD + (m *1ll* inv(n + m) % MOD) * doit(n, m - 1) % MOD + 1)% MOD;
}
signed main(){
int n = read(), m = read();
printf("%lld\n", doit(n, m));
return 0;
}Pro. C
给出一个长度为 \(n\) 的序列（保证\(A_i \in [1, 2]\)）， \(m\) 次操作。 - 询问操作格式为 A s，表示询问是否有一种散步方案使得美丽值之和为 \(s\)。 - 修改操作格式为 C i val，表示将第 \(i\) 朵花的美丽值改成 \(val(val=1\) 或 \(2)\)。
对于每一个询问，若有合法的方案，输出这个方案的左右端点位置（多种方案时输出左端点最小的方案），否则输出 none。
\(\operatorname{Subtask\ 1}\ (20pts)\)：对于数据点 \(1\sim 5\)，满足 \(1\leq n,m\leq 1000\)。
\(\operatorname{Subtask\ 2}\ (30pts)\)：对于数据点 \(6\sim 10\)，满足 \(1\leq n,m\leq 2.5\times 10^5\)。
\(\operatorname{Subtask\ 3}\ (50pts)\)：对于数据点 \(11\sim 15\)，满足 \(1\leq n,m\leq 2\times 10^6\)。
对于 \(100\%\) 的数据，有 \(1\leq n,m\leq 2\times 10^6,0\leq s\leq 2^{31}-1\)。每次修改操作时 \(i\in[1,n],val\in\{1,2\}\)。
对于所有数据点，时间限制 \(2000\operatorname{ms}\)，空间限制 \(256\operatorname{MB}\)。
留坑！
Pro. D
有一个无限大的棋盘来下马棋。
有一个马最开始在 \((0,0)\)，它的每一步可以走一个 \(a\times b\) 的矩形（ 即能够从\((x,y)\)到达 \((x\pm a,y\pm b)\) 或 \((x\pm b,y\pm a)\) ）。
若马通过上述移动方式可以到达棋盘中任意一个点，那么 \(p(a,b)=1\)，否则 \(p(a,b)=0\)。
现在 Amazing John 给你 \(T\) 组询问，每组询问他会给出一个正整数 \(n\)，他想知道
\[\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}\]
的值。
本题开启Subtask
| 子任务 | 数据点 | 数据范围 | 分数 |
|---|---|---|---|
| \(1\) | \(1\) | \(n\leq 10,T\leq5\) | \(5\) |
| \(2\) | \(2\sim 5\) | \(n\leq 3000,T\leq5\) | \(15\) |
| \(3\) | \(6\sim 10\) | \(n\leq 10^5,T\leq 5\) | \(15\) |
| \(4\) | \(11\sim 15\) | \(n\leq 10^7,T\leq5\) | \(15\) |
| \(5\) | \(16\sim 18\) | \(n\leq10^9,T\leq 5\) | \(15\) |
| \(6\) | \(19\sim 25\) | \(n\times T\leq 10^{11},T\leq 5\) | \(35\) |
注 1：对于 \(n\times T\geq 5*10^{10}\) 的数据点，时限为 4s ，其余均为 2.5s 。且对于所有数据点，空间限制为 500MB 。
注 2：输出答案 \(\bmod\ 2^{64}\) 即对 64位无符号整数 自然溢出。
通过打表可知：其中的函数 \(\operatorname{p}\)， \(\operatorname{p}(a, b) = [a \perp b]\ [(a - b) \ \operatorname{mod} \ 2\ = \ 1]\)
考虑每个数字的贡献，因为 \(a\) \(b\) 的差为奇数 所以\(a\) \(b\) 的奇偶性不同。 - 对于偶数 \(x\) 贡献为 \(\varphi(x)\) - 对于奇数 \(x\) 贡献为 \(\frac{\varphi(x)}{2}\)，即 与 \(x\) 互质的偶数个数。
答案就是： \[2\times[\ \sum_{i=1}^{n}\limits{[i\ \operatorname{mod} \ 2\ = 1]\frac{\varphi(i)}{2}} + \sum_{i=1}^{n}\limits{[i\ \operatorname{mod} \ 2\ = 0]\varphi(i)}\ ]\]
50pts 不知道怎么杜教筛降复杂度。
code
// 线性筛 phi
#define ULL unsigned long long
void doit(){
int n = read();
ULL ans = 0;
for(int i = 1; i <= n; i++){
ans += (i & 1) ? (phi[i] >> 1) : phi[i];
}
printf("%llu\n", ans << 1);
}
int main(){
int T = read(); euler(1e7 + 2); while(T--) doit(); return 0;
}