专栏文章

梦熊省选模拟赛 5 题解

PPurslaneM2GA
生活·游记参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqp422l
此快照首次捕获于
2025/12/04 08:26
3 个月前
此快照最后确认于
2025/12/04 08:26
3 个月前
查看原文
做了好几场，这场质量最高！
因为各种原因 rnk 1/2→rnk 9\rm rnk \ 1 / 2 \to rnk \ 9，真幽默。

A

题意：维护一个序列 aa，有两种操作
  • 1 l r v，表示 ∀l≤i≤r\forall l \le i \le r，ai←aiva_i \leftarrow a_i v。
  • 2 l r，求把 ll 到 rr 中所有数选若干个出来乘在一起（可以重复），模 pp 有多少种可能。
pp 是质数，保证没有 aia_i 是 pp 的倍数。
容易发现，设 aia_i 对 pp 的阶为 xix_i，我们只需要求 gcd⁡l≤i≤r{p−1xi}\gcd_{l \le i \le r}\{\dfrac{p-1}{x_i}\}，即 lcml≤i≤r{xi}\text{lcm}_{l \le i \le r}\{x_i\}。
这个东西显然可以转化为：xlx_l、xl+1xl\dfrac{x_{l+1}}{x_l}、⋯\cdots、xrxr−1\dfrac{x_r}{x_{r-1}} 的阶的 lcm\rm lcm。
单次修改只会对 O(1)O(1) 个位置产生贡献，直接线段树维护即可。

B

题意：有两个 Floyd 算法：
CPP
void Oldfloyd(int n){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++) if(G[i][k]){
			for(int j=1;j<=n;j++) if(G[k][j]){
				G[i][j]=1;
			}
		}
	}
}
和
CPP
void Newfloyd(int n,int m){
	for(int k=1;k<=m;k++){
		for(int i=1;i<=n;i++) if(G[i][k]){
			for(int j=1;j<=n;j++) if(G[k][j]){
				G[i][j]=1;
			}
		}
	}
}
给定 nn 和 mm，在所有 2n(n−1)22^{\frac{n(n-1)}{2}} 种图中，求出有多少个两个算法跑出来的结果相同。
不是哥们，我怕 TLE 把所有输入先读进去，这样可以稳小数据不寄（卡了常之后其实已经只有 1 s1 \rm \ s 稳过了）。但是我把输入数组开小了，直接挂成了零蛋。
考虑把点分为 ≤m\le m 和 >m> m 两种，集合分别是 AA 和 BB。
性质：
  1. 任何 BB 中的点，最多与 AA 中一个连通块相连。
  2. 如果 BB 不和 AA 的任何一个连通块相连，那么它所在的整体连通块必定是一个悬在海外的完全图。
这样设 dpi,jdp_{i,j} 为 AA 中放了 ii 个点，BB 中放了 jj 个点的方案数，转移的时候乘上一些组合数就行了。
复杂度 O(n4)O(n^4)，会被卡常。你少写一些取模就能过。
不知为啥题解写的好复杂。

C

题意：第一行有 nn 个格子，第二行有 mm 个格子。要在里面放一些 [0,2k)[0,2^k) 的数，使得所有行和列都互不相同，且异或和为 00，求方案数。
这个真有 T3 难度吗。
考虑钦定 nn 和 mm，钦定两行有 ii 个数相同。
子问题 1：求从 [0,2k)[0,2^k) 个数中选 xx 个互不相同的数使得他们异或和为 00 的方案数。
这个瞎容斥即可。
子问题 2：将两行适当排列，使得对应列没有相同元素。
系数其实就是
n!∑t=0i(−1)t(it)(m−t)!n! \sum_{t=0}^i (-1)^t \dbinom{i}{t} (m-t)!
场上由于只有 30 min30 \ \rm min 写这道题（T2 卡常卡了 INF 年），所以就根据这个胡了个 O(Tmin⁡{n,m}2)O(T \min\{n,m\}^2) 的做法，直接获得了 6868 分，感觉很划来。
考虑这个东西拆成 (−1)ti!(m−t)!t!(i−t)!(-1)^t \dfrac{i!(m-t)!}{t!(i-t)!}，发现可以写成 fj=(−1)j(m−j)!j!f_j = (-1)^j \dfrac{(m-j)!}{j!} 和 gj=1j!g_j = \dfrac{1}{j!} 的卷积，所以用任意模数 NTT\rm NTT 就能做到 O(nlog⁡n)O(n \log n)，写的好看应该有 8888 分（rnk 1\rm rnk \ 1 就是这么写的）
当时试图从网上贺板子，但是家里鼠标不给力，无法锁定代码，导致最后手忙脚乱没贺成。
现在还不会线性做法，别急。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...