梦熊省选模拟赛 5 题解
Purslane
·
·
生活·游记
做了好几场，这场质量最高！
因为各种原因 \rm rnk \ 1 / 2 \to rnk \ 9，真幽默。
A
题意：维护一个序列 a，有两种操作
1 l r v，表示 \forall l \le i \le r，a_i \leftarrow a_i v。2 l r，求把 l 到 r 中所有数选若干个出来乘在一起（可以重复），模 p 有多少种可能。
-----
容易发现，设 $a_i$ 对 $p$ 的阶为 $x_i$，我们只需要求 $\gcd_{l \le i \le r}\{\dfrac{p-1}{x_i}\}$，即 $\text{lcm}_{l \le i \le r}\{x_i\}$。
这个东西显然可以转化为：$x_l$、$\dfrac{x_{l+1}}{x_l}$、$\cdots$、$\dfrac{x_r}{x_{r-1}}$ 的阶的 $\rm lcm$。
单次修改只会对 $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;
}
}
}
}
```
给定 $n$ 和 $m$，在所有 $2^{\frac{n(n-1)}{2}}$ 种图中，求出有多少个两个算法跑出来的结果相同。
------
不是哥们，我怕 TLE 把所有输入先读进去，这样可以稳小数据不寄（卡了常之后其实已经只有 $1 \rm \ s$ 稳过了）。但是我把**输入数组开小了**，直接挂成了零蛋。
考虑把点分为 $\le m$ 和 $> m$ 两种，集合分别是 $A$ 和 $B$。
性质：
1. 任何 $B$ 中的点，最多与 $A$ 中一个连通块相连。
2. 如果 $B$ 不和 $A$ 的任何一个连通块相连，那么它所在的整体连通块必定是一个悬在海外的完全图。
这样设 $dp_{i,j}$ 为 $A$ 中放了 $i$ 个点，$B$ 中放了 $j$ 个点的方案数，转移的时候乘上一些组合数就行了。
复杂度 $O(n^4)$，会被卡常。你少写一些取模就能过。
不知为啥题解写的好复杂。
# C
题意：第一行有 $n$ 个格子，第二行有 $m$ 个格子。要在里面放一些 $[0,2^k)$ 的数，使得所有行和列都互不相同，且异或和为 $0$，求方案数。
-------
这个真有 T3 难度吗。
考虑钦定 $n$ 和 $m$，钦定两行有 $i$ 个数相同。
子问题 1：求从 $[0,2^k)$ 个数中选 $x$ 个互不相同的数使得他们异或和为 $0$ 的方案数。
这个瞎容斥即可。
子问题 2：将两行适当排列，使得对应列没有相同元素。
系数其实就是
$$
n! \sum_{t=0}^i (-1)^t \dbinom{i}{t} (m-t)!
$$
场上由于只有 $30 \ \rm min$ 写这道题（T2 卡常卡了 INF 年），所以就根据这个胡了个 $O(T \min\{n,m\}^2)$ 的做法，直接获得了 $68$ 分，感觉很划来。
考虑这个东西拆成 $(-1)^t \dfrac{i!(m-t)!}{t!(i-t)!}$，发现可以写成 $f_j = (-1)^j \dfrac{(m-j)!}{j!}$ 和 $g_j = \dfrac{1}{j!}$ 的卷积，所以用任意模数 $\rm NTT$ 就能做到 $O(n \log n)$，写的好看应该有 $88$ 分（$\rm rnk \ 1$ 就是这么写的）
~~当时试图从网上贺板子，但是家里鼠标不给力，无法锁定代码，导致最后手忙脚乱没贺成。~~
现在还不会线性做法，别急。