[ARC171] A~D 题解
A. No Attacking
最优策略是车隔行放，分讨一下就可以了。
if(n < a) cout << "No\n";
else {
if(a * 2 < n) b -= (a + 1) * (n - a);
else {
b -= (n - a) * (n - a);
if(b <= 0) cout << "Yes\n";
else cout << "No\n";
return ;
}
n -= a;
if(b <= 0) cout << "Yes\n";
else if(b <= (n - a - 1) / 2 * n) cout << "Yes\n";
else cout << "No\n";
}
B. Chmax
手玩一下发现排列之间有关系，往图论想，发现最终可以建出一张图，所有 \(a_i > i\) 的位置沿着图走一定会到达 \(a_i = i\) 的位置，并且只能走向下一个 \(a_j = a_i\) 的位置 \(j\)，因为不能回头，而最后那些 \(a_i = i\) 的位置则可以指向所有还没有入度的位置，而每个没有入度的位置一定是一块的开头，于是记录一下到现在位置有多少个块的开头可以被选择，每次碰到一个终点位置算一下贡献即可。
坑点：如果 \(a_i < i\) 必不可能，如果 \(a_i\ne a_{a_i}\) 必不可能，因为你既然你可以到 \(a_i\)，那你的 \(a\) 肯定至少有 \(a_{a_i}\)，结合上一个条件就是不等号。
// Problem: B - Chmax
// Contest: AtCoder - AtCoder Regular Contest 171
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-02-04 23:17:18
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
int n, a[N];
bool st[N], in[N], out[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
if(!st[a[i]]) in[i] = 1, st[a[i]] = 1;
}
for(int i = 1; i <= n; i ++) {
if(a[i] < i || (a[i] != a[a[i]])) {
cout << 0 << '\n';
return 0;
}
}
memset(st, 0, sizeof st);
for(int i = n; i; i --)
if(!st[a[i]]) out[i] = 1, st[a[i]] = 1;
int ans = 1;
for(int i = 1, cnt = 0; i <= n; i ++) {
cnt += in[i];
if(out[i]) ans = 1ll * ans * cnt % mod, cnt --;
}
cout << ans << '\n';
return 0;
}
C. Swap on Tree
两个操作序列得到的 \(a\) 相同当且仅当所有选择的边都一样，并且对于一个点，它四周的边选择的顺序也一样。
根据这个我们可以做一个 DP，用 \(f_{i, j, 0/1}\) 表示 \(i\) 的子树内，与 \(i\) 相连的边选择了 \(j\) 个，是否选择了父边的方案数。
\[f_{i, j, x} = f_{i, j, x}\times\sum_{k = 0}^{deg_v} f_{v, k, 0}+f_{i, j - 1, x}\times \sum_{k = 0}^{deg_v}f_{v, k, 1}\times j \]树上背包类型的转移，分讨儿子边是否选择，如果选择就需要在前面 \(j - 1\) 条已选择的边里面确定一个顺序，所以要乘 \(j\)，和式可以预处理。
时间复杂度：\(O(n^2)\)。
// Problem: [ARC171C] Swap on Tree
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-02-06 11:24:52
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 3e3 + 10, mod = 998244353;
int n, f[N][N][2], sz[N], s[N][2];
vector<int> g[N];
void dfs(int u, int fa) {
sz[u] = 1, f[u][0][0] = 1, f[u][1][1] = (u > 1); // 注意根节点没有父边
int d = g[u].size();
for(auto v : g[u]) {
if(v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
for(int j = d; j >= 0; j --)
for(int x = 0; x < 2; x ++)
f[u][j][x] = (f[u][j][x] * s[v][0] % mod + (j ? f[u][j - 1][x] * j % mod * s[v][1] % mod : 0)) % mod;
}
for(int j = 0; j <= d; j ++)
for(int x = 0; x < 2; x ++)
(s[u][x] += f[u][j][x]) %= mod;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1, a, b; i < n; i ++) {
cin >> a >> b;
g[a].push_back(b), g[b].push_back(a);
}
dfs(1, 1);
cout << s[1][0] << '\n';
return 0;
}
D. Rolling Hash
不妨把原式书写为：
\[\displaystyle \mathrm{hash}(X) = \left(\sum_{i=1}^n x_i B^{i}\right) \bmod P \]由对称性可知这样是等价的。
这样一来，区间的哈希值就等于 \((h_r - h_{l - 1}) / {B^{r - l + 1}}\)，这意味着题目中给定的若干条约束等价于 \(h_r\ne h_{l - 1}\)。
这种关系可以从图论的角度思考，建图之后我们需要解决这个子问题：
给定一张无向图，请判断是否存在一种染色方案使得所有相邻的点颜色不同，且颜色数 \(\le P\)。
这个是经典问题，可以用状压解决，具体而言，\(f_s\) 表示已经对 \(s\) 集合染色，最少颜色数，可以枚举子集，并且子集的点两两无边，转移。
时间复杂度：\(O(3^n)\)。
// Problem: D - Rolling Hash
// Contest: AtCoder - AtCoder Regular Contest 171
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-02-05 22:08:52
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
using namespace std;
const int N = 17;
int n, m, p;
int b[N], f[(1 << N)], disj[(1 << N)];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> p >> n >> n >> m;
for(int i = 1, l, r; i <= m; i ++) {
cin >> l >> r;
b[l - 1] |= (1 << r), b[r] |= (1 << (l - 1));
}
n ++;
for(int s = 0; s < (1 << n); s ++) {
disj[s] = 1;
for(int i = 0; i < n; i ++)
if(s >> i & 1) if(s & b[i]) {
disj[s] = 0;
break;
}
}
memset(f, 0x3f, sizeof f), f[0] = 0;
for(int s = 0; s < (1 << n); s ++)
for(int t = s; t; t = (t - 1) & s)
if(disj[t]) f[s] = min(f[s], f[t ^ s] + 1);
cout << (f[(1 << n) - 1] <= p ? "Yes" : "No") << '\n';
return 0;
}