3.2 L5-NOIP训练29 测试题解
码创 Contest #530
（出题人写中文也要句句都打分号吗！！）
A. 老司机的压缩包（数论）
题面
老司机最近得到了一个奇怪的压缩包，听说里面有十分厉害的东西呢！
但是这个压缩包有一个奇怪的密码设定；
首先有这个压缩包有一个数字 \(n\)；
每次压缩包会给出一个数字 \([0,n-1]\) 区间的整数，要求老司机回答这个数在 \(\bmod n\) 下的逆元是多少，如果逆元不存在则视为0即可；
老司机觉得这太简单了，但是因为 \(n\) 很大，老司机并不愿意一个一个输入进去；
所以老司机决定将 \([0,n-1]\) 所有逆元的和输进去，这样也许就直接可以打开了呢；
然而老司机并不会做这个问题，所以就交给你了！
如果你的回答让老司机满意的话，他也许也会给你一个压缩包哦；
题意
给定 \(T\) 个 \(n\)，对于每个 \(n\) 输出 \(\sum i^{-1}\)，其中 \(i\) 为所有小于 \(n\) 且 \(\gcd(i,n)=1\) 的正整数，\(i^{-1}\) 表示 \(i\) 对模 \(n\) 的逆。
\(100\%\) 的数据满足 \(T\le100\)，\(1\le n\le10^9\)。
思路
我们知道，对于任一正整数 \(i<n\) 且 \(\gcd(i,n)=1\)，有且仅有一个 \(i^{-1}<n\) 满足 \(i\cdot i^{-1}\equiv1\pmod n\)（反证法可以证明），并且 \(\gcd(i^{-1},n)=1\)。
因此每一个 \(i^{-1}\) 都对应着一个不同的 \(i\)。于是题目转化为：求 \(\sum\limits_{0<i<n\land(i,n)=1}i\)。
引理（更相减损术） \(\gcd(n,i)=\gcd(n,n-i).\)
证明 设 \(\gcd(n,i)=d\)。令 \(n=ad,i=bd\)，由最大公约数的定义得 \(\gcd(a,b)=1\)。
由于 \(n-i=(a-b)d\)，下面只需证明 \(\gcd(a,a-b)=1\)。
假设 \(a\) 和 \(a-b\) 不互质。设 \(\gcd(a,a-b)=m>1\)。
令 \(a=xm,a-b=ym\)。则 \(b=(x-y)m\)，所以 \(a\) 和 \(b\) 有公约数 \(m>1\)，与 \(\gcd(a,b)=1\) 矛盾。
因此假设不成立，原命题得证。
因此有
\[\begin{aligned} &\sum_{\gcd(i,n)=1}i\\ =&\frac12\left(\sum_{\gcd(i,n)=1}i+\sum_{\gcd(n-i,n)=1}n-i\right)\\ =&\frac12\left(\sum_{\gcd(i,n)=1}i+\sum_{\gcd(i,n)=1}n-i\right)\\ =&\frac12\sum_{\gcd(i,n)=1}n\\ =&\frac{n\cdot\varphi(n)}2. \end{aligned} \]第一个等号处是因为 \(i\) 和 \(n-i\) 是一一对应的关系。
于是可以根据欧拉函数 \(\varphi(n)\) 的定义在 \(O(\sqrt n)\) 时间内求出答案。总复杂度 \(O(T\sqrt n)\)。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define FILENAME "zip"
using namespace std;
typedef long long ll;
int n, tt, phi;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// freopen(FILENAME".in", "r", stdin);
// freopen(FILENAME".out", "w", stdout);
cin >> tt;
while (tt--) {
cin >> n;
ll tmp = n;
phi = n;
for (int i = 2; i <= n / i; ++ i) {
if (!(n % i)) {
while (!(n % i)) n /= i;
phi = phi / i * (i - 1);
}
}
if (n ^ 1) phi = phi / n * (n - 1);
cout << tmp * phi / 2 << '\n';
}
return 0;
}
B. 老司机的彩虹桥（树上 DP）
题面
自从老司机有了好多好多小司姬之后，老司机就造了一个好大好大的房子；
因为老司机非常的 6，这个房子不在地上而在天上！
我们可以将这个房子抽象成 \(n\) 片云朵和 \(n-1\) 条彩虹，每一条彩虹上都住着一个小司姬，当然了，所有云朵是由这些彩虹连通的树哦；
现在老司机想去探望所有老司机的小司姬，但是麻烦的是，他并不能进到小司姬的房间里——也就是不能通过彩虹桥来移动；
所以每次他只能到一个云朵上，然后探望和那个云朵相连的彩虹桥上的小司姬；
老司机想知道，他最少要去多少个云朵上才能探望所有的小司姬；
老司机还想知道，有多少个云朵是在所有的最优方案中他都不会上去的；
老司机还想知道，他究竟有多少种最优方案来探望小司姬们呢？
如果你的回答让老司机满意的话，他也许会邀请你去看小司姬哦；
题意
给定一棵树，选定某个节点处时，视为经过它所连的所有边。
- 求最少要选定多少个节点才能经过所有边；
- 求有多少个节点不会出现在第 1 问的任何最优方案中；
- 求第 1 问一共有多少种最优方案。
思路
设 \(f(u,0/1)\) 表示 不选 / 选 节点 \(u\)，且经过以 \(u\) 为根的子树中的所有边时，选定的最少节点数。
考虑在树上跑 DFS。首先考虑第 1 问。
对于一条边 \((u,v)\)，其中 \(u\) 是 \(v\) 的父亲，需要选节点 \(u\) 和 \(v\) 中的一个或两个。
所以状态转移方程为：
\[\begin{aligned} &f(u,0)=\sum f(v,1),\\ &f(u,1)=\sum\min\{f(v,0),f(v,1)\}. \end{aligned} \]初值：\(f(i,0)=0,f(i,1)=1\)，其中 \(i\) 为所有叶子节点。答案：\(\min\{f(rt,0),f(rt,1)\}\)，其中 \(rt\) 为 DFS 的起点。
发现可以顺便记录第 3 问的方案数。设 \(g(u,0/1)\) 表示 \(f(u,0/1)\) 对应的最优方案数。
状态转移方程（乘法和加法原理）：
\[\begin{aligned} &g(u,0)=\prod g(v,1),\\ &g(u,1)=\prod\begin{cases} g(v,0),&f(v,0)<f(v,1),\\ g(v,1),&f(v,0)>f(v,1),\\ g(v,0)+g(v,1),&f(v,0)=f(v,1). \end{cases} \end{aligned} \]最后一种转移是因为两种情况对于方案数来说是等效的，所以可以分类相加。
初值：\(g(i,0)=g(i,1)=1\)，其中 \(i\) 为所有叶子节点。答案与 \(g(u,1)\) 转移的讨论方法相同。
难点在于第 2 问。
考虑 转化一下问题：如果一个节点一定不被选，那么说明任何一个最优方案都不包含它。于是我们可以 反过来先将这个点选上，然后判断此时的最优解是否等于全局的最优解。这样一来，枚举选定所有点，求出此时的最优解即可。
考虑换根 DP，即在一次 DFS 中就处理出关于“父树”（即整个树 去掉以这个点为根的子树 所形成的树）的所有信息，并且在短时间内就能得到每个点的答案，以避免进行许多次 DFS。
进行第二次 DFS，设 \(F(u,0/1)\) 表示不选 / 选节点 \(u\)，且经过 \(u\) 的父树中（即 \(u\) 上方）的所有边时，选定的最少节点数（不包括 \(u\)）。
设 \(u\) 的父亲为 \(fa\)。我们需要在 \(f(fa,0/1)\) 中去掉 \(u\) 的贡献。于是状态转移方程为：
\[\begin{aligned} &F(u,0)=f(fa,1)-\min\{f(u,0),f(u,1)\}+F(fa,1),\\ &F(u,1)=\min\{F(u,0),F(fa,0)+f(fa,0)-f(u,1)\}. \end{aligned} \]初值为 \(F(rt,0)=F(rt,1)=0\)，其中 \(rt\) 为 DFS 的起点。对于枚举的新根节点 \(u\)，最优解为 \(f(u,1)+F(u,1)\)。当最优解不等于全局最优解时，累加，即为答案。
复杂度为 \(O(n)\)。
代码
#include <cstdio>
#include <vector>
#include <iostream>
#define FILENAME "rainbow"
#define f(x, y, z) for (int x = (y); x <= (z); ++ x)
using namespace std;
typedef long long ll;
int const N = 1e5 + 10;
int const MOD = 5462617;
int n, ans, cnt;
vector<int> edge[N];
int f[N][2]; //f[u][0/1]: 探望子树 u 中所有边, 不选/选 u 的需要的最少云朵数
ll g[N][2]; //方案数
void dfs(int u, int fa) {
f[u][1] = 1;
g[u][0] = g[u][1] = 1;
for (int i = 0; i < (int)edge[u].size(); ++i) {
int v = edge[u][i];
if (v == fa) continue;
dfs(v, u);
f[u][0] += f[v][1];
g[u][0] *= g[v][1];
g[u][0] %= MOD;
if (f[v][0] < f[v][1]) {
f[u][1] += f[v][0];
g[u][1] *= g[v][0];
g[u][1] %= MOD;
} else if (f[v][1] < f[v][0]) {
f[u][1] += f[v][1];
g[u][1] *= g[v][1];
g[u][1] %= MOD;
} else {
f[u][1] += f[v][0];
g[u][1] *= (g[v][0] + g[v][1]) % MOD;
g[u][1] %= MOD;
}
}
}
int F[N][2];
void dfs2(int u, int fa) {
for (int i = 0; i < (int)edge[u].size(); ++i) {
int v = edge[u][i];
if (v == fa) continue;
F[v][0] = f[u][1] - min(f[v][0], f[v][1]) + F[u][1];
F[v][1] = min(F[u][0] + f[u][0] - f[v][1], F[v][0]);
dfs2(v, u);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// freopen(FILENAME".in", "r", stdin);
// freopen(FILENAME".out", "w", stdout);
cin >> n;
f(i, 2, n) {
int x, y;
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1, 0);
dfs2(1, 0);
cout << (ans = min(f[1][0], f[1][1])) << '\n';
f(u, 1, n) if (f[u][1] + F[u][1] != ans) ++cnt;
cout << cnt << '\n';
if (f[1][0] < f[1][1]) cout << g[1][0] << '\n';
else if (f[1][1] < f[1][0]) cout << g[1][1] << '\n';
else cout << (g[1][0] + g[1][1]) % MOD << '\n';
return 0;
}
C. 小司姬的序列（哈希 + 二分）
题面
自从老司机有了好多好多小司姬之后，老司机经常与她们一起玩游戏；
老司机总是喜欢吧小司姬们排成一列又一列的样子，然后向她们提出一些奇怪的问题，当然了，作为一个绅士，他是不会在询问开始之后再排列小司姬们的；
在序列中的每个小司姬都有一个可爱度 \(a_i\)，两个可爱度相同的小司姬视为相同的小司姬；
这一次，老司机提出的问题是这样的，对于两个小司姬序列 \(x,y\)，它们相同的最长的小司姬序列有多长呢？(即查询两个序列的最长公共前缀 LCP)
小司姬们当然会这个问题了，但是因为小司姬们实在是太可爱了，她们就又不会这个问题了，所以小司姬们向你求助，要你来解决这个问题；
如果你的回答让小司姬们满意的话，她们也许会邀请你一起来排队哦；
题意
给出 \(n\) 个只含有非负整数的序列，\(m\) 次询问，每次询问给出 \(x,y\)，求第 \(x\) 个序列和第 \(y\) 个序列的最长公共前缀（LCP）。
\(50\%\) 的数据满足 \(n\le1000\)，\(m\le1000\)，序列总长度 \(\sum l\le100000\)；
其中 \(30\%\) 的数据满足序列元素大小 \(1\le a_i\le26\)；
\(100\%\) 的数据满足 \(n\le100000\)，\(m\le100000\)，序列总长度 \(\sum l\le500000\)，序列元素大小 \(0\le a_i\le10^9\)。
思路
哈希 + 二分。由于前缀相同则前缀的哈希值相同，而前缀的哈希值可以很容易地求出来，所以可以预处理哈希值，然后二分找出两个序列最后一个哈希值相同的位置。
时间复杂度 \(O(\sum l+m\log\max l)\)。
代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define f(x, y, z) for (int x = (y); (x) <= (z); ++(x))
#define FILENAME "girls"
using namespace std;
typedef unsigned long long ull;
const int N = 1e5 + 10;
const int BASE1 = 1e9 + 7;
const int BASE2 = 1e9 + 9;
int n, m, len, x, y;
vector<int> a[N];
vector<pair<ull, ull> > h[N];
signed main() {
freopen(FILENAME".in", "r", stdin);
freopen(FILENAME".out", "w", stdout);
scanf("%d%d", &n, &m);
f(i, 1, n) {
scanf("%d", &len);
a[i].push_back(0);
f(j, 1, len) {
scanf("%d", &x);
a[i].push_back(x);
}
}
f(i, 1, n) {
h[i].emplace_back(0, 0);
f(j, 1, (int)a[i].size() - 1)
h[i].emplace_back(h[i][j - 1].first * BASE1 + a[i][j], h[i][j - 1].second * BASE2 + a[i][j]);
}
while (m--) {
scanf("%d%d", &x, &y);
int l = 0, r = min(h[x].size(), h[y].size());
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (h[x][mid].first == h[y][mid].first && h[x][mid].second == h[y][mid].second)
l = mid;
else r = mid;
}
printf("%d\n", l);
}
return 0;
}