「比赛总结」洛谷 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; 
}