第六场 1003 Phi Master
题目描述
小 C 在找 npy。
众所周知，找 npy 需要考虑两人之间的默契。经过初步筛选，小 C 列出了一个候选人列表 \(a_1,a_2,\ldots,a_n\)，其中 \(a_i\) 表示第 \(i\) 号候选人的能力值。
如果小 C 的能力值为 \(x\)，那么候选人 \(i\) 和小 C 之间的默契度为 \(\varphi(xa_i)\)，其中 \(\varphi\) 表示欧拉函数。
由于小 C 的能力值未知，小 R 想要你对每个可能的能力值 \(x\)，求出此时的最大默契度。
形式化地，对每组测试数据，给定序列 \(a_1,a_2,\ldots,a_n\)，对所有满足 \(1\le x\le 10^7\) 的整数 \(x\)，定义
\[ F_x=\max_{1\le i\le n}\varphi(xa_i). \]
你需要按照特殊格式输出这些值的压缩结果。
考虑把 \(\varphi(xa_i)\) 拆到 \(x\) 和 \(a_i\) 上，那么会发现 \(\varphi(xa_i) = \varphi(x)\varphi(a_i)\dfrac{\gcd(x, a_i)}{\varphi(\gcd(x, a_i))}\)，必须要引入与 \(\gcd(x, a_i)\) 有关的修正项。
所以以 \(\gcd(x, a_i)\) 为跳板统计 \(a_i\) 的贡献，并贡献到 \(x\) 的答案。
注意到对于 \(g=\gcd(x, a_i)\)，若 \(d|g\)，则 \(\dfrac{d}{\varphi(d)}<\dfrac{g}{\varphi(g)}\)，所以我们可以转而将所有 \(d|a_i \land d|x\) 都作为跳板，这样就把 \(a_i\) 与 \(x\) 的耦合拆开了。
具体来说，我们需要对于所有 \(d\) 统计 \(\text{mx}(d)=\max\limits_{d|a_i}{\varphi(a_i)}\)，然后将 \(\text{mx}(d)\dfrac{d}{\varphi(d)}\) 贡献到 \(\text{ans}(x)(d|x)\)。这可以使用狄利克雷前缀/后缀 max 解决。
狄利克雷前缀 max
考虑我们需要计算 \(f(d) = \max\limits_{d|g} f(g)\)。
那么令 \(t=\dfrac gd\)，我们转而通过 \(t\) 的所有质因子分批次贡献。具体地，我们枚举所有质数 \(p_i\)，倒序枚举 \(x\in [1, \dfrac Vp]\)，将 \(f(px)\) 贡献到 \(f(x)\)，通过类似完全背包的方法可以保证正确性。
后缀 max 类似。
时间复杂度 \(O(V\log \log V)\)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <bits/stdc++.h>
namespace FIO {
const int D = 1 << 23;
char in[D], *I = in, *Iend = in, out[D], *O = out;
char rdc() { return (I == Iend ? Iend = in + fread(I = in, 1, D, stdin) : 0), (I == Iend ? EOF : *I++); }
template<typename T> void read(T &x) {
char c = rdc(), fl = 0;
while(c < '0' || c > '9') fl |= (c == '-'), c = rdc();
for(x = 0; '0' <= c && c <= '9'; c = rdc()) x = x * 10 + (c - '0');
if(fl) x = -x;
}
void wrtc(char c) { (O == out + D ? fwrite(O = out, 1, D, stdout) : 0), *O++ = c; }
template<typename T> void write(T x, char ch = 0) {
static char c[60]; int top = 0;
if(x < 0) wrtc('-'), x = -x;
do c[++top] = x % 10, x /= 10; while(x);
while(top) wrtc(c[top--] + '0');
if(ch) wrtc(ch);
}
void flush() { fwrite(out, 1, O - out, stdout); }
struct Flusher { ~Flusher() { flush(); } } flusher;
}
using FIO::write;
using FIO::read;
typedef long long LL;
const int N = 2e6 + 5;
const int MAXV = 1e7;
const int B = 1000;
int n;
bool isprm[MAXV + 5];
std::vector<int> prime;
int phi[MAXV + 5];
void sieve(int ans) {
for(int i = 2; i <= ans; i++) isprm[i] = true;
phi[1] = 1;
for(int i = 2; i <= ans; i++) {
if(isprm[i]) prime.push_back(i), phi[i] = i - 1;
for(int p : prime) {
if((LL)p * i > ans) break;
isprm[i * p] = false;
if(i % p == 0) {
phi[i * p] = phi[i] * p;
break;
} else phi[i * p] = phi[i] * phi[p];
}
}
}
LL ans[MAXV + 5], out[B + 5];
int main() {
sieve(1e7);
int T; read(T);
while(T--) {
memset(out, 0, sizeof(out));
memset(ans, 0, sizeof(ans));
read(n);
for(int i = 1; i <= n; i++) {
int x;
read(x), ans[x] = phi[x];
}
for(int p : prime)
for(int j = MAXV / p; j >= 1; j--)
ans[j] = std::max(ans[j], ans[j * p]);
for(int i = 1; i <= MAXV; i++) ans[i] = ans[i] / phi[i] * i;
for(int p : prime)
for(int j = 1; (LL)j * p <= MAXV; j++)
ans[j * p] = std::max(ans[j * p], ans[j]);
for(int i = 1; i <= MAXV; i++) out[i % B] ^= ((i + B - 1) / B) * ans[i] * phi[i];
for(int i = 0; i < B; i++) write(out[i], '\n');
}
return 0;
}
|
第七场 1004 今晚吃转转
题目描述
即便是最细小的枝桠也能孕育无限可能。
地脉正在颤动，世界树岌岌可危。 原本的世界树可以被看作一棵包含 \(n\) 个点与 \(n-1\) 条边的无根树 \(Y\) 被绘制在平面上。\(Y\) 中的第 \(i\)（\(1\le i\le n\)）个点在坐标 \(\lparen x_i,y_i\rparen\)（\(x_i,y_i\in\mathbb{R}\)）处，点的坐标两两不同。\(Y\) 的每条边都是连接两个端点的线段，连接后平面上的图形就被称为 \(Y\) 的图像。注意，图像不能进行平移，缩放，旋转，轴对称等任何操作。
由于地脉紊乱，世界树被迫旋转。 现在，平面中出现了一个紊乱点 \(\lparen p,q\rparen\)（\(p,q\in\mathbb{R}\)），使得世界树 \(Y\) 的图像以 \(\lparen p,q\rparen\) 为中心顺时针旋转了 \(\frac{2\pi}{k}\) 弧度，其中 \(k\) 是一个正整数。注意紊乱点坐标是任意的，可以与世界树某一个点重合，也可以落在世界树某一条边上。
作为新生的小吉祥草王，纳西妲只知道世界树 \(Y\) 的形态而不知道它的图像。纳西妲想要知道，对于哪些正整数 \(k\)，存在一个为 \(Y\) 中每个点赋予两两不同的坐标以及选取紊乱点坐标的方式，使得：
- \(Y\) 的图像中，任意两条边对应的线段除公共端点外不相交（包括某一条边的端点落在另一条边上的情况）。
- \(Y\) 的图像旋转后与其旋转前完全重合。
注意，判断重合时不能进行平移，缩放，旋转，轴对称等任何操作。
写这道题的题解是因为题目里有纳西妲。
感性理解发现旋转中心只能在边中点或点上。
然后发现二度点可以在某些情况下退化成一条边。所以我们考虑将所有二度点缩掉，这样问题就变成了子树同构。
再用树哈希解决就好了。
Bonus: 缩二度点后旋转中心只能在树的重心（点或边中点），所以只需要判断一个点就可以，不用换根哈希。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include <bits/stdc++.h>
using std::cin;
using std::cout;
typedef unsigned long long ull;
const int N = 2e5 + 5;
int n;
std::vector<int> to[N];
int rt;
ull random(ull x) {
auto f = [](ull y) -> ull { return (ull)y * y * y * 16810086 + 11335577; };
return f(x) + f(x >> 32);
}
ull f[N], g[N];
int fa[N];
void dfs1(int u) {
f[u] = 1027;
for(int v : to[u]) if(v != fa[u]) {
fa[v] = u;
dfs1(v);
f[u] += random(f[v]);
}
}
void dfs2(int u) {
ull hsh = 1027 + (u == rt ? 0 : random(g[u]));
for(int v : to[u]) if(v != fa[u]) hsh += random(f[v]);
for(int v : to[u]) if(v != fa[u]) {
g[v] = hsh - random(f[v]);
dfs2(v);
}
}
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
bool del[N];
bool ans[N];
int main() {
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T--) {
cin >> n;
for(int i = 1; i <= n; i++) to[i].clear(), ans[i] = false, del[i] = false;
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
to[u].emplace_back(v), to[v].emplace_back(u);
}
for(int i = 1; i <= n; i++) {
int sz = 0, u = 0, v = 0;
for(int d : to[i]) if(!del[d]) sz++, (u == 0 ? u : v) = d;
if(sz != 2) continue;
to[u].emplace_back(v);
to[v].emplace_back(u);
del[i] = true;
}
for(int u = 1; u <= n; u++) {
std::vector<int> tmp;
for(int v : to[u]) if(!del[v]) tmp.emplace_back(v);
to[u].swap(tmp);
}
for(rt = 1; rt <= n; rt++) if(!del[rt]) break;
dfs1(rt), g[rt] = 0, dfs2(rt);
for(int u = 1; u <= n; u++) if(!del[u]) {
std::vector<ull> vct;
for(int v : to[u]) if(v != fa[u]) vct.emplace_back(f[v]);
if(u != rt) vct.emplace_back(g[u]);
std::sort(vct.begin(), vct.end());
ull last = 0; int cnt = 0, gc = 0;
for(ull v : vct)
if(cnt == 0) last = v, cnt++;
else if(last == v) cnt++;
else gc = gcd(cnt, gc), cnt = 1, last = v;
gc = gcd(cnt, gc);
ans[gc] = true;
}
for(int i = 1; i <= n; i++) if(!del[i] && i != rt && f[i] == g[i]) { ans[2] = true; break; }
for(int i = 1; i <= n; i++)
for(int j = i + i; j <= n; j += i)
ans[i] |= ans[j];
int cnt = 0;
for(int i = 1; i <= n; i++) cnt += ans[i];
cout << cnt << '\n';
for(int i = 1; i <= n; i++) if(ans[i]) cout << i << ' ';
cout << '\n';
}
return 0;
}
|
第七场 1010 今晚吃黑子
题目描述
白井黑子喜欢下棋。
她在桌上将 \(n\) 枚棋子（黑子或白子）排成一列，从左到右依次编号为 \(1\) 到 \(n\)。
定义一次操作为：选择一个棋子 \(i\)，满足 \(1<i<n\) 且 \(i-1\) 和 \(i+1\) 处的棋子颜色不同。她会将 \(i-1\) 和 \(i+1\) 处的棋子吃掉，然后移动棋子将空位填上，形成新的一列棋子，并重新从 \(1\) 开始编号。\(n\) 也被重新设定为现在棋子序列的长度。
白井黑子可以进行任意（可以为零）次这样的操作。现在，她想让你求出最后可能得到的棋子序列的个数。两个棋子序列不同，当且仅当它们长度不同，或者某个位置棋子的颜色不同。
由于答案可能很大，请输出其对 \(998\,244\,353\) 取模后的结果。
写这道题的题解不是因为题目里有黑子，因为我没看过。
先来考虑判定性问题，即序列 \(A\) 能否变成序列 \(B\)。
首先一个显然的观察是 \(B\) 的一个棋子对应 \(A\) 的一段区间。所以问题转化为将 \(A\) 分割为若干区间，使得每个区间可以对应转化为 \(B\) 的一个棋子。
然后先来考虑怎样的序列能够变成一个黑子。
一个平凡的必要条件是黑子比白子多一个。另一个显然的限制是，除了单个黑子的序列外，序列中必须存在两个相邻的同色棋子。
手玩会发现这两个条件是充分的。由于存在相邻的同色棋子，所以当前这一步必定能进行一次删除。简单分讨可以得到，删除后若棋子大于一个，则必定会出现下一组同色相邻棋子。由于数量关系保证，最终一定会变成一个黑子。
所以一个序列能变成黑子的充要条件是：
- 黑子比白子多一个
- 序列不能是黑白交替（单个黑子除外）
对于白子也类似。
接下来考虑怎么将一个序列划分为若干个合法（能变成单个黑/白子的）区间。
这里要用到一个性质。从上面的充要条件容易得到，对于一个可以变成黑子的序列，若不是单个黑子，则该序列拼接上一个黑子等于白子的序列仍然可以变成黑子（白子类似）。
因此，我们考虑在 \(A\) 中贪心地尽量选取靠前的区间，使得其能转化为 \(B\) 序列中下一个棋子。容易发现，如果最优答案中，某个棋子对应的区间比贪心更长，找到第一个这样的区间，则一定是在贪心基础上增加了一段黑白子数量相同的区间。那么根据性质，将这段区间拼接到下一个棋子的前面是不劣的。这就保证了贪心的正确性。
但是还有一个问题，如果贪心选取区间时最后剩下了一段区间怎么办。首先这段区间一定是一个黑白数量相等的区间，不然数量上就无解了。然后如果最后一个棋子不是单个棋子，或者这段区间不是黑白交替，则直接将余下区间拼到最后一个棋子上就好了。否则，不妨设是 1，则 \(A\) 的最后形如 1010101，此时可以让最后一个 1 对应 \(B\) 的最后一个棋子，那么这段连续的黑白交替序列被移动到了最后一个棋子前面，可以递归的尝试将其合并到倒数第二个棋子上。如果合并到第一个棋子都不行，说明 \(A\) 与 \(B\) 均是黑白交替。此时答案为 \(1\)，直接特判即可。
现在可以考虑计数了。我们将每个 \(B\) 序列映射成在 \(A\) 中贪心选区间的方案。那么我们要做的就是对于每个位置预处理出从这个地方开始能转化成黑子/白子的最短区间，然后 DP 即可。
时间复杂度 \(O(n)\)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
typedef long long LL;
const int N = 1e5 + 5;
const LL MOD = 998244353;
int n;
char s[N];
int sum[N];
void mod(LL &x) { if(x >= MOD) x -= MOD; }
LL f[N];
int nxt[N], last[N];
int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%s", s + 1);
n = strlen(s + 1);
bool flag = true;
for(int i = 2; i <= n; i++) flag &= (s[i] != s[i - 1]);
if(flag) { puts("1"); continue; }
for(int i = 0; i <= n + 1; i++) last[i] = 0;
sum[n + 1] = 0;
for(int i = n; i >= 1; i--) sum[i] = sum[i + 1] + (s[i] == '1' ? 1 : -1);
int mn = *std::min_element(sum + 1, sum + n + 2);
for(int i = 1; i <= n + 1; i++) sum[i] -= mn - 1;
for(int i = n, j = n + 1; i >= 1; i--) {
if(i <= n - 1 && s[i] == s[i + 1]) {
while(j >= i + 2) last[sum[j]] = j, j--;
}
if(s[i] == '1') nxt[i - 1] = last[sum[i] + 1] - 1;
else nxt[i - 1] = last[sum[i] - 1] - 1;
}
f[0] = 1;
for(int i = 1; i <= n; i++) f[i] = 0;
for(int i = 0; i < n; i++) {
mod(f[i + 1] += f[i]);
if(nxt[i] > 0) mod(f[nxt[i]] += f[i]);
}
LL ans = 0;
for(int i = 1; i <= n; i++) if(sum[i + 1] == sum[n + 1]) ans += f[i];
printf("%lld\n", ans % MOD);
}
return 0;
}
|