Codeforces Round 998 (Div. 3)

E

原题链接
思路：
题目要求对于 G 中存在路径的两个点，在 F 中也必须存在路径，不是两个点存在直连的边。
两个点存在路径，说明俩个点在同一个连通块。我们用并查集来维护图的连通块。
最终的要求就是把 F 的并查集通过修改，变成和 G 的并查集一样。
我们先枚举 F 的边，如果连接的两个点在 G 中属于不同的连通块，那么我们要删除这条边；
同理我们枚举 G 的每条边，如果连接的两个点在 F 中属于不同的联通块，那么我们需要添加这条边，记得在并查集中合并。

#include <bits/stdc++.h>#define dbg(a) std::cout << #a << '=' << a << '\n'
#define cc(x) std::cout << fixed << setprecision(x)using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using ld = long double;const ld PI = acos(-1);
const ld EPS = 1e-7;
const ld INF = 1E18;struct DSU {std::vector<int> p, sz;DSU(int n) : p(n + 1), sz(n + 1, 1){ iota(p.begin(), p.end(), 0); }int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}bool same(int x, int y) { return find(x) == find(y); }bool merge(int x, int y){x = find(x), y = find(y);if (x == y) return false;if (sz[x] < sz[y]) std::swap(x, y);sz[x] += sz[y];p[y] = x;return true;}int size(int x) { return sz[find(x)];}
};void solve() {int n, m1, m2;std::cin >> n >> m1 >> m2;DSU d1(n + 1), d2(n + 1);std::vector<std::pair<int, int>> e1(m1), e2(m2);for (int i = 0; i < m1; i++) {int x, y;std::cin >> x >> y;e1[i] = {x, y};}for (int i = 0; i < m2; i++) {int x, y;std::cin >> x >> y;e2[i] = {x, y};d2.merge(x, y);}int ans = 0;std::vector<std::pair<int, int>> t;t.reserve(m1);for (auto &[x, y] : e1) {if (!d2.same(x, y)) ans++;else t.emplace_back(x, y);}for (auto &[x, y] : t) d1.merge(x, y);for (auto &[x, y] : e2) {if (!d1.same(x, y)) {ans++;d1.merge(x, y);}}std::cout << ans << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int  t = 1;std::cin >> t;while (t--) {solve();}return 0;
}

F

原题链接
思路：
$2^{31}$ 大约在 2e9 左右。用计算机算发现 $2^{17}>10^5$，因此构造的数组当中非 1 的元素的个数最多为16 个。
动态规划：
dp[num][j] 表示数组中 j 个非1元素位置乘积为 num 的方案数。
状态转移方程：
$$dp[num][j]=\sum _{k|num}dp[k][j-1]$$
对于每个数 num ，可以构造的数组长度也需要枚举。
因此对于 num 的结果为：
$$an{s}_{num}=\sum _{i=1}^n\sum _{j=1}^{16}\left(\genfrac{}{}{0ex}{}{i}{j}\right)dp[num][j]=\sum _{i=1}^{16}dp[num][j]\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{i}{j}\right)=\sum _{i=1}^{16}dp[num][j]\left(\genfrac{}{}{0ex}{}{n+1}{j+1}\right)$$
最后一步使用了曲棍球恒等式。

#include <bits/stdc++.h>#define dbg(a) std::cout << #a << '=' << a << '\n'
#define cc(x) std::cout << fixed << setprecision(x)using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using ld = long double;const ld PI = acos(-1);
const ld EPS = 1e-7;
const ld INF = 1E18;template<class T>
constexpr T power(T a, i64 b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;
}constexpr i64 mul(i64 a, i64 b, i64 p) {i64 res = a * b - i64(1.L * a * b / p) * p;res %= p;if (res < 0) {res += p;}return res;
}
template<i64 P>
struct MLong {i64 x;constexpr MLong() : x{} {}constexpr MLong(i64 x) : x{norm(x % getMod())} {}static i64 Mod;constexpr static i64 getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(i64 Mod_) {Mod = Mod_;}constexpr i64 norm(i64 x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr i64 val() const {return x;}explicit constexpr operator i64() const {return x;}constexpr MLong operator-() const {MLong res;res.x = norm(getMod() - x);return res;}constexpr MLong inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MLong &operator*=(MLong rhs) & {x = mul(x, rhs.x, getMod());return *this;}constexpr MLong &operator+=(MLong rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLong &operator-=(MLong rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLong &operator/=(MLong rhs) & {return *this *= rhs.inv();}friend constexpr MLong operator*(MLong lhs, MLong rhs) {MLong res = lhs;res *= rhs;return res;}friend constexpr MLong operator+(MLong lhs, MLong rhs) {MLong res = lhs;res += rhs;return res;}friend constexpr MLong operator-(MLong lhs, MLong rhs) {MLong res = lhs;res -= rhs;return res;}friend constexpr MLong operator/(MLong lhs, MLong rhs) {MLong res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {i64 v;is >> v;a = MLong(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {return os << a.val();}friend constexpr bool operator==(MLong lhs, MLong rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MLong lhs, MLong rhs) {return lhs.val() != rhs.val();}
};template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;template<int P>
struct MInt {int x;constexpr MInt() : x{} {}constexpr MInt(i64 x) : x{norm(x % getMod())} {}static int Mod;constexpr static int getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(int Mod_) {Mod = Mod_;}constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr int val() const {return x;}explicit constexpr operator int() const {return x;}constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this;}constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this;}constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;return res;}friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {i64 v;is >> v;a = MInt(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}
};template<>
int MInt<0>::Mod = 998244353;template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();constexpr int P = 998244353;
using Z = MInt<P>;void solve() {i64 n, k;std::cin >> k >> n;// std::cerr << k << ' ' << n << '\n';std::vector<std::array<Z, 17>> dp(k + 1);dp[2][1] = 1;for (int i = 3; i <= k; i++) {std::vector<int> prime;for (int num = 2; num <= i / num; num++) {if (i % num == 0) {prime.emplace_back(num);if (i / num != num) prime.emplace_back(i / num);}}dp[i][1] = 1;for (int j = 2; j < 17; j++) {for (auto &pri : prime) dp[i][j] += dp[pri][j - 1];}}std::vector<Z> C(18);C[0] = 1;for (int i = 1; i <= 17 && i <= n + 1; i++) C[i] = C[i - 1] * (n + 2 - i) / i;std::cout << n << " \n"[n == 1];for (int i = 2; i <= k; i++) {Z ans = 0;for (int j = 1; j < 17; j++) {ans += dp[i][j] * C[j + 1];}std::cout << ans << " \n"[i == k];}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int  t = 1;std::cin >> t;while (t--) {solve();}return 0;
}