Educational Codeforces Round 142 (Rated for Div. 2)_野指针*

网络投稿 02-07 4764

题意:给定n*n乘法表和m=m1*m2,求乘法表中出现多少个m的约数,最早出现的行数分别是多少.

对m1,m2分解质因数,然后dfs搜出所有m的约数,然后子集dp,设f[i]为小于m最大的约数,初始化f[i]=i,(i <=m),转移f[i] = max(f[i], f[i / p]),最后判断i / f[i]是否小于等于m即可.

#include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(false), cin.tie(0) #define ll long long // #define double long double #define ull unsigned long long #define PII pair<int, int> #define PDI pair<double, int> #define PDD pair<double, double> #define debug(a) cout << #a << " = " << a << endl #define point(n) cout << fixed << setprecision(n) #define all(x) (x).begin(), (x).end() #define mem(x, y) memset((x), (y), sizeof(x)) #define lbt(x) (x & (-x)) #define SZ(x) ((x).size()) #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f // namespace nqio { const unsigned R = 4e5, W = 4e5; char* a, * b, i[R], o[W], * c = o, * d = o + W, h[40], * p = h, y; bool s; struct q { void r(char& x) { x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++; } void f() { fwrite(o, 1, c - o, stdout); c = o; } ~q() { f(); }void w(char x) { *c = x; if (++c == d) f(); } q& operator >>(char& x) { do r(x); while (x <= 32); return *this; } q& operator >>(char* x) { do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this; } template<typename t> q& operator>>(t& x) { for (r(y), s = 0; !isdigit(y); r(y)) s |= y == 45; if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this; } q& operator <<(char x) { w(x); return *this; }q& operator<< (char* x) { while (*x) w(*x++); return *this; }q& operator <<(const char* x) { while (*x) w(*x++); return *this; }template<typename t> q& operator<< (t x) { if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p); return *this; } }qio; }using nqio::qio; using namespace std; const int N = 2e5 + 10; int n, m1, m2, primes[N], c; map<int, int> fac; vector<int> s; void dec(int x) { int t = x; for (int i = 2; i <= x / i; ++i) { if (x % i) continue; while (x % i == 0) { ++fac[i]; x /= i; } } if (x > 1) ++fac[x]; } void dfs(int x, int now) { if (x == c + 1) { s.emplace_back(now); return; } for (int i = 1, t = 1; i <= fac[primes[x]] + 1; ++i) { dfs(x + 1, now * t); t *= primes[x]; } } void solve() { fac.clear(); s.clear(); c = 0; cin >> n >> m1 >> m2; dec(m1), dec(m2); for (auto [x, y] : fac) { primes[++c] = x; } dfs(1, 1); sort(all(s)); vector<int> f(s.size() + 1, 0); int ans1 = 0, ans2 = 0; for (int i = 0; i < s.size(); ++i) { int x = s[i]; if (x <= n) { f[i] = x; }else { f[i] = 0; for (int j = 1; j <= c; ++j) { int p = primes[j], pre = lower_bound(all(s), x / p) - s.begin(); if (x % p == 0 && f[pre] && x / f[pre] <= n) f[i] = max(f[i], f[pre]); } } if (f[i]) { ++ans1, ans2 ^= (x / f[i]); } } cout << ans1 << " " << ans2 << "\n"; } signed main() { IOS; int T; cin >> T; while (T--) solve(); } F1.

题意:有n阶完全图,对图中的边进行红蓝染色,要求该图要么只是红联通,要么只是蓝联通,求合法的染色方案数,并且两种颜色都至少被用到一次.

引理:任何一个不联通图的补图都联通.证明:对于不联通图中的两个联通分量,补图会将这两个分量的每个点互相配对,形成一个联通块,归纳可得整个图都会联通.

所以所有合法方案可以分成两种情况,红不联通或者蓝不联通(即满足蓝不联通的前提下红联通).我们计算红不联通,即一个图的红联通块数大于等于2的所有情况.设A[n]为n个节点的合法染色方案数,那么就包含了大于等于两个红联通块的所有方案,和只有一个红联通块的部分方案(合法方案,即蓝不联通).设B[n]为n个节点只有一个红联通块的合法方案,枚举1号点所在的红联通块大小(1~n-1),B[n] = ∑(k=1~n-1)C(n-1,k-1)B(k)*A(n-k),拿1号点红联通块去链接其他点红联通块,由于我们想要确保连边方案是唯一的,由上面的定义我们拿蓝边去链接这两个联通块的所有点,这样两个红联通块一定不会联通,所以形成的图一定是蓝联通的,等于B[n].初始化A[1] = B[1] = 1, A[n] = 2 * B[n](n >= 2).最后得到A[n]为了满足题意,减去两种全蓝和全红的方案.

#include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(false), cin.tie(0) #define ll long long // #define double long double #define ull unsigned long long #define PII pair<int, int> #define PDI pair<double, int> #define PDD pair<double, double> #define debug(a) cout << #a << " = " << a << endl #define point(n) cout << fixed << setprecision(n) #define all(x) (x).begin(), (x).end() #define mem(x, y) memset((x), (y), sizeof(x)) #define lbt(x) (x & (-x)) #define SZ(x) ((x).size()) #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f // namespace nqio { const unsigned R = 4e5, W = 4e5; char* a, * b, i[R], o[W], * c = o, * d = o + W, h[40], * p = h, y; bool s; struct q { void r(char& x) { x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++; } void f() { fwrite(o, 1, c - o, stdout); c = o; } ~q() { f(); }void w(char x) { *c = x; if (++c == d) f(); } q& operator >>(char& x) { do r(x); while (x <= 32); return *this; } q& operator >>(char* x) { do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this; } template<typename t> q& operator>>(t& x) { for (r(y), s = 0; !isdigit(y); r(y)) s |= y == 45; if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this; } q& operator <<(char x) { w(x); return *this; }q& operator<< (char* x) { while (*x) w(*x++); return *this; }q& operator <<(const char* x) { while (*x) w(*x++); return *this; }template<typename t> q& operator<< (t x) { if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p); return *this; } }qio; }using nqio::qio; using namespace std; const int N = 2e5 + 10, mod = 998244353; int B[N]; int fact[N], infact[N], inv[N]; void init (int n) { fact[0] = infact[0] = inv[0] = inv[1] = 1; for (int i = 2; i <= n; ++ i) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; for (int i = 1; i <= n; ++ i) { fact[i] = 1ll * fact[i - 1] * i % mod; infact[i] = 1ll * infact[i - 1] * inv[i] % mod; } } int C(int n, int m) { if(n < m) return 0; if(m == 0 || n == m) return 1; return 1ll * fact[n] * infact[m] % mod * infact[n - m] % mod; } int dfs(int n) { if (B[n] != -1) { return B[n]; } if (n <= 2) { return B[n] = 1; } int res = 0; for (int k = 1; k <= n - 1; ++k) { (res += dfs(n - k) * dfs(k) % mod * C(n - 1, k - 1) % mod * 2 % mod * (k == n - 1 ? (mod + 1) / 2 : 1) % mod) %= mod; } return B[n] = res; } void solve() { int n; cin >> n; cout << 2 * (dfs(n) - 1) % mod << "\n"; } signed main() { IOS; init(N - 10); mem(B, -1); int T = 1; // cin >> T; while (T--) solve(); }