A
你有长度为 \(2n\) 的排列,每次操作是:把 \(a_1,a_2,...,a_{2n}\) 变成 \(a_1,a_{n+1},a_2,a_{n+2},...,a_{n},a_{2n}\)。
问多少次操作后序列回到最初的状态。\(n\le 10^{14}\)。
我们先把 \(1\) 开始标号改成 \(0\) 开始。那么操作是这样的:
若 \(x<n\),那么移动到 \(2x\),若 \(x\ge n\),那么移动到 \(2(x-n)+1=2x-(2n-1)\).
我们的操作需要分讨是及其麻烦的,所以我们尝试把操作归为同类。
发现取模 \(2n-1\) 即可,那么现在只需要求 \(2^{t}=1\pmod {2n-1}\) 的最小正整数解。
我们枚举 \(\varphi(2n-1)\) 的约数即可。
B
对于序列 \(A,B\),你可以对序列 \(A\) 进行若干次操作,每次你可以选定一个 \(A_u\),使 \(A_u\gets \otimes_{i=1}^n A_i\)。
问最少多少次操作使得 \(A=B\)。\(n\le 10^5\)。
我们发现每次操作就是交换 \(A_u\) 和异或和。
我们把置换环建出来,如果有相同的权值就合并两个环。每个环的代价是大小 \(+1\)。
我们用并查集维护这个过程。
还要注意的是如果一开始异或和存在于 \(B\) 中,那么答案 \(-1\)。
C
在一棵树上随机黑白染色,问白点的最长距离和黑点的最长距离的最大值的期望。\(n\le 10^5\)。
我们先考虑 \(n\le 10^3\),我们拆贡献枚举这个最大值是多少,设最大值为 \(s\)。
那么距离 \(\le s\) 的点对是可以随便填黑白的,但是 \(>s\) 的点对必须满足颜色不同,这是个二分图染色。
现在考虑正解,由于是最长的距离,我们先把直径拿出来,如果两端颜色相同那么答案就是直径。
我们默认直径两端颜色不同。那么新的最长的距离是多少呢?
根据树的直径的性质,新的最长的距离一定有一个端点是直径的端点。
于是求出 \(f_k\) 表示答案 \(\le k\) 的方案数,那么距离两个端点都 \(\le k\) 的点可以随便填。
答案 \(=k\) 的方案数差分一下即可。
D
在树上你要从 \(1\) 走到 \(n\),移动的方式是拿出一个点 \(u\),并向 \(u\) 的方向移动一步。
问最少经过的点集大小最小是多少。\(n\le 1e5\)。
与绝对众数有关。
标签:10,le,2024.7,28,直径,test,操作,2n,我们 From: https://www.cnblogs.com/Simon-Gao/p/18328891