T1
本题考察了数论的相关知识。
30pts
暴力枚举每次洗牌的情况，时间复杂度为 \(O(n^2)\)。
60pts
首先卡牌 \(1\) 和 \(2n\) 一直不动，可以不用考虑这两张牌。
将位置和剩下的牌上的数字全减 \(1\)，那么数字为 \(k\) 的牌操作一次后就会到 \(2k\bmod (2n-1)\) 的位置。
那么问题相当于找最小的 \(k\) 使得 \(\forall t,t\times 2^{k}\equiv t\pmod {(2n-1)}\)，显然只需要考虑 \(2^{k}\equiv 1\pmod {(2n-1)}\) 就行了，\(O(n)\) 暴力检验即可。
100pts
根据欧拉定理，\(k\) 必然是 \(\varphi(2n-1)\) 的因数，而 \(10^{18}\) 范围内的正整数的约数个数大约只有 \(10^6\) 级别，直接暴力快速幂判定就能过了。
输入的数会有点大。快读，开__int128
#include <bits/stdc++.h>
using namespace std;
#define int __int128
int n, m, p, t, e;
int T;
template<typename type>
inline void read(type &x)
{
x=0;static bool flag(0);char ch=getchar();
while(!isdigit(ch)) flag=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1)//0为空格，1为换行
{
x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10; while(x);
while(top) putchar(Stack[top--]|48);
mode?putchar('\n'):putchar(' ');
}
int phi(int x) {
int _p = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
_p -= _p / i;
while (x % i == 0) x /= i;
}
}
if (x > 1)
_p -= _p / x;
return _p;
}
int ksm(int x, int y, int mod) {
int a = x % mod;
int ans = 1;
while (y) {
if (y & 1)
ans *= a, ans %= mod;
a *= a, a %= mod;
y >>= 1;
}
return ans;
}
signed main() {
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
read(T);
while (T--) {
read(n);
n = n - 1;
m = 2 * n + 1;
p = phi(m);
t = p;
e = sqrt((long long) p);
for (int i = 1; i <= e; i++) {
if(p%i!=0)continue;
if (ksm(2, i, m) == 1) {
t = i;
break;
}
else {
if (ksm(2, p / i, m) == 1)
t = p / i;
}
}
write(t);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
T2
本题考察了图论的相关知识。
30pts
直接爆搜每次的情况并进行去重，时间复杂度为 \(O(n!)\)，后续会给出具体证明。
+30pts
令初始的异或和为 \(x\)，拿在手中，相当于每次用手中的数把 \(a\) 中的一个值顶掉，然后把原来的值拿在手里，这也间接说明了状态数是 \(n!\) 量级的。
此档分会发现 \(a_i\) 和所有 \(a_i\) 异或后的权值两两不同，我们考虑一个过程，用 \(x\) 替换了 \(a_p\)，然后用 \(a_p\) 替换了 \(a_q\)，循环下去。
其实最终一定是要用 \(b_i\) 替换 \(a_i\) 的，而上面的过程又是从 \(x\) 出发走了一条路，按如上方式建图找出环的个数即可统计答案。
100pts
我们从 \(b_i\) 向 \(a_i\) 连边（不同位置上相同的数值对应同一个点），然后尝试从 \(x\) 出发遍历每条边。
注意如果图是一个包含 \(x\) 的连通块，则一定可以找到一条欧拉路径（不一定是回路）覆盖所有边。
如果图不连通，或 \(x\) 在连通块内（\(x\) 不是孤立点），则答案就是边数再加上连通块数再减去 \(1\)（如果 \(x\) 是孤立点就不用减 \(1\)）。
时间复杂度为 \(O(n)\)。
T3
本题考察了树的直径，二分图的相关知识。
10pts
爆搜所有 \(2^n\) 种情况，求最远点对距离即可。
40pts
考虑把 \(O(n^2)\) 对点对依次取出排好序，考虑如果答案 \(<x\)，意味着所有点对距离 \(\geq x\) 的点对颜色必须两两不同，把这些约束取出，相当于一个二分图染色的问题，于是我们可以很方便的算出 \(<x\) 的答案，利用差分即可算出 \(=x\) 的答案。
100pts
先求出一条直径，若直径的两个端点颜色相同，则最长距离一定为直径。否则，令两个端点分别为 \(x,y\)，并钦定 \(x,y\) 不同色。枚举答案 \(d\)，所有到 \(x\) 距离 \(>d\) 的点颜色必须与 \(y\) 一样，所有到 \(y\) 距离 \(>d\) 的点颜色必须和 \(x\) 一样。由于 \(x,y\) 是直径的两个端点，可以发现，若一个点 \(z\) 到 \(x,y\) 的距离都不超过 \(d\)，则其到任何一个点的距离不超过 \(d\)，所以 \(z\) 的颜色并不会对答案产生影响。
所以，定义 \(cnt_i\) 表示到直径两端的距离不超过 \(i\) 的点数。定义 \(f_d\) 表示答案不超过 \(d\) 的树的形态数，\(g_d\) 表示答案为 \(d\) 的树的形态数，\(dis_{1/2}\) 表示从直径的两端点出发到其他点的距离。定义 \(L=\max(\min(dis_{1i}, dis_{2i}))\)。此处 \(L\) 的意义为，在所有形态的树中，最小的答案（同色点对最大距离）。对于每个点取到直径两端点近的那个颜色即可。
最终的总权值为 \(\sum_{i=L}^{S} g_i \times i\)。
容易得到 \(f_d = 2^{cnt_d}\)。但是我们想要答案等于 \(d\) 的树的形态数 \(g_i\)。很明显，只需要容斥减去 \(f_{d-1}\) 即可，也就是 \(g_d = f_d - f_{d-1}\)。
注意 \(x,y\) 共有 2 种颜色分配方案。
T4
本题考察了贪心的相关知识。
40pts
显然最终经过了 \(2k+dis(1,n)\) 条边，因此 \(n≡dis(1,n)( \bmod2)\) 就合法，否则不合法。
先考虑最小值，即只经过 \(path(1,n)\) 的方案。
那么对于路径上第 \(i\) 个点 \(c_i\)，设他在路径外的子树大小为 \(siz(c_i)\)。
我们发现很多操作都要在折返中抵消，那么我们只要钦定链上哪些操作最终有用，剩下的操作形成若干跨子树的匹配，那么我们一定能构造一个合法的 \(p\)。
根据经典结论，那么我们要求剩下的操作中不存在绝对众数。
找到最大的 \(siz(c_i)\)，那么我们至多在他的子树里钦定 \(i\) 个没被抵消。
因此这种情况的充要条件就是 \(siz(c_i)−i≤2n−dis(1,n)\)，显然这样的 \(i\) 至多一个，因此我们能构造出一个合法的匹配。
否则找到不合法的这棵子树，枚举一个连通块 \(S\)，记每个连通块内节点 \(u\) 在连通块外的子树大小为 \(siz(u)\)。
那么我们依然要求 \(siz(u)−i≤2n−dis(1,n)\)，证明大致同上。
那么我们要在这个基础上保留尽可能少的节点是的所有 \(siz(u)\) 不超过 \(k=2n−dis(1,n)+i\)。
问题就变成：给一棵 \(n\) 顶点的树，可以断掉若干的边，要求断掉的边连通且连通块包含 \(1\) 节点。要求剩下每个连通块大小不超过 \(k\)，求最小分割数，可以进行树形DP求解这个值，时间复杂度为 \(O(n^2)\)。
+10pts
考虑整张图为菊花图，所以除了 \(1\) 号点以外的地位相同，可以把除 \(n\) 号点的以外的点两两抵消，按照 \(n\) 的奇偶性进行分类讨论即可。
100pts
注意到 \(siz(c_i)≤n−dis(1,n)≤2k\)，因此不合法的所有点构成一条链，对于每个点贪心地割掉若干个最大的子树即可。
时间复杂度 \(O(n \log n)\)，如果利用桶排序，时间复杂度为 \(O(n)\)。
标签：连通,int,题解,复杂度,siz,梦熊,2n,第三场,dis From： https://www.cnblogs.com/-y-0-x-0-h-/p/18329403