目录
Contest InfoSolutions A. Distinct DigitsB. Filling the GridC. Primes and MultiplicationD. Complete TripartiteE. Another Filling the GridPractice Link
SolvedABCDEF5/6OOOOØ- O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试签到。
签到。
题意： 定义\(prime(x)\)为\(x\)的所有质因子构成的集合。 定义\(g(x, p)\)为最大的\(p^k\)满足\(p^k \;|\; x\)， 定义\(f(x, y)\)为：\[ \begin{eqnarray*} \prod\limits_{p \in prime(x)} g(y, p) \end{eqnarray*} \]
现在给出\(x, n\)，要求计算：\[ \prod\limits_{i = 1}^n f(x, i) \bmod (10^9 + 7) \]
思路： 枚举\(x\)的每个质因子，再从高到低枚举每个质因子的幂次，考虑对于一个质因子\(p\)，用\(f[i]\)表示\([1, n]\)中有多少个\(p^i\)的倍数，且不是\(p^j (j > i)\)的倍数，那么个数是\(\left\lfloor n / p^i \right\rfloor - \left\lfloor n / p^{i + 1} \right\rfloor\)
代码：view code
#include <bits/stdc++.h> using namespace std; #define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); } #define fi first #define se second #define endl "\n" using ll = long long; using pII = pair <int, int>; using pLL = pair <ll, ll>; using VI = vector <int>; using VL = vector <ll>; constexpr int mod = 1e9 + 7; template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; } template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; } inline int rd() { int x; cin >> x; return x; } template <class T> inline void rd(T &x) { cin >> x; } template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; } template <class T> inline void out(T s) { cout << s << "\n"; } template <class T> inline void out(vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; } constexpr int N = 1e5 + 10; ll x, n, bit[110]; inline ll ceil(ll x, ll y) { return (x + y - 1) / y; } void run() { vector <int> fac; for (ll i = 2; i * i <= x; ++i) { if (x % i == 0) fac.push_back(i); while (x % i == 0) x /= i; } if (x != 1) fac.push_back(x); ll res = 1; for (auto &it : fac) { if (it > n) continue; int k = 1; bit[1] = it; for (int i = 2; ; ++i) { if (bit[i - 1] > ceil(n, it)) { k = i - 1; break; } bit[i] = bit[i - 1] * it; } ll tot = 0; for (int i = k; i >= 1; --i) { ll p = n / bit[i]; p -= tot; res = res * qpow(bit[i] % mod, p % (mod - 1)) % mod; tot += p; } } out(res); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(20); while (cin >> x >> n) run(); return 0; }题意： 现在给出一张\(n\)个点\(m\)条边的无向图，没有自环和重边， 问能否将点分成三个集合，使得集合内部的点之间没有边相连，但任意两个点(他们分属不同的集合)有边相连。 如果可以，输出方案。
思路： 考虑同一点集里所有的点连出去的边都是相同的，那么根据这个\(Hash\)，如果刚好有三种\(Hash\)值，那么按\(Hash\)值分类即可
代码：view code
#include <bits/stdc++.h> using namespace std; #define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); } #define fi first #define se second #define endl "\n" using ll = long long; using ull = unsigned long long; using pII = pair <int, int>; using pLL = pair <ll, ll>; using VI = vector <int>; using VL = vector <ll>; constexpr int mod = 1e9 + 7; template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; } template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; } inline int rd() { int x; cin >> x; return x; } template <class T> inline void rd(T &x) { cin >> x; } template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; } template <class T> inline void out(T s) { cout << s << "\n"; } template <class T> inline void out(vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; } constexpr int N = 3e5 + 10; int n, m, ans[N]; mt19937 rnd(time(0)); ull f[N], g[N]; map <ull, vector<int>> mp; void run() { for (int i = 1; i <= n; ++i) f[i] = rnd(); memset(g, 0, sizeof g); mp.clear(); for (int i = 1, u, v; i <= m; ++i) { cin >> u >> v; g[u] ^= f[v]; g[v] ^= f[u]; } for (int i = 1; i <= n; ++i) { mp[g[i]].push_back(i); if (mp.size() > 3) return out(-1); } if (mp.size() != 3) return out(-1); int cnt = 0; for (auto &it : mp) { ++cnt; for (auto &u : it.second) { ans[u] = cnt; } } for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(20); while (cin >> n >> m) run(); return 0; }题意： 给出一个\(n \cdot n\)的矩形，每个位置可以填\([1, k]\)。 现在要求每一行至少有一个\(1\)，每一列至少有一个\(1\)，问填数的方案数。
思路一： 考虑\(f[i][j]\)表示考虑前\(i\)行有\(j\)列有\(1\)，转移的时候注意每一行至少有一个\(1\)。 时间复杂度\(O(n^3)\)
代码一：view code
#include <bits/stdc++.h> using namespace std; #define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); } #define fi first #define se second #define endl "\n" using ll = long long; using pII = pair <int, int>; using pLL = pair <ll, ll>; using VI = vector <int>; using VL = vector <ll>; constexpr int mod = 1e9 + 7; template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; } template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; } inline int rd() { int x; cin >> x; return x; } template <class T> inline void rd(T &x) { cin >> x; } template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; } template <class T> inline void out(T s) { cout << s << "\n"; } template <class T> inline void out(vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; } constexpr int N = 300 + 10; int n, K; ll f[N][N], C[N][N]; void run() { if (n == 1 || K == 1) return out(1); memset(f, 0, sizeof f); for (int i = 1; i <= n; ++i) { f[1][i] = C[n][i] * qpow(K - 1, n - i) % mod; } for (int i = 2; i <= n; ++i) { for (int j = 1; j <= n; ++j) { ll p = qpow(K, j); for (int k = j; k <= n; ++k) { if (k == j) chadd(f[i][k], f[i - 1][j] * (p + mod - qpow(K - 1, j)) % mod * qpow(K - 1, n - k) % mod); else chadd(f[i][k], f[i - 1][j] * p % mod * C[n - j][k - j] % mod * qpow(K - 1, n - k) % mod); } } } out(f[n][n]); } int main() { memset(C, 0, sizeof C); C[0][0] = 1; for (int i = 1; i < N; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(20); while (cin >> n >> K) run(); return 0; }思路二： 考虑枚举有\(i\)行\(j\)列没有\(1\)，然后根据\((i + j)\)的奇偶性容斥。 时间复杂度\(O(n^2)\)
代码二：view code
#include <bits/stdc++.h> using namespace std; #define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); } #define fi first #define se second #define endl "\n" using ll = long long; using pII = pair <int, int>; using pLL = pair <ll, ll>; using VI = vector <int>; using VL = vector <ll>; constexpr int mod = 1e9 + 7; template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; } template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; } inline int rd() { int x; cin >> x; return x; } template <class T> inline void rd(T &x) { cin >> x; } template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; } template <class T> inline void out(T s) { cout << s << "\n"; } template <class T> inline void out(vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; } constexpr int N = 300 + 10; int n, K; ll f[N][N], C[N][N]; void run() { if (n == 1 || K == 1) return out(1); ll ans = 0; //枚举有i行，j列没有1，容斥 for (int i = 0; i <= n; ++i) { for (int j = 0; j <= n; ++j) { ll ch = i * n + j * n - i * j; ll ex = n * n - ch; ll now = C[n][i] * C[n][j] % mod * qpow(K - 1, ch) % mod * qpow(K, ex) % mod; if ((i + j) & 1) chadd(ans, mod - now); else chadd(ans, now); } } out(ans); } int main() { C[0][0] = 1; for (int i = 1; i < N; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(20); while (cin >> n >> K) run(); return 0; }思路三： 考虑枚举有\(i\)行没有\(1\)，那么保证每一列都至少有一个\(1\)，那么答案就是：\[ \begin{eqnarray*} \sum\limits_{i = 0}^{n - 1} (-1)^i{n \choose i}(k - 1)^{in}f^n(n - i) \end{eqnarray*} \] 其中\(f[i]\)表示有\(i\)个数，至少有一个\(1\)的方案数，显然有：\[ \begin{eqnarray*} f[i] = k^{i} - (k - 1)^i \end{eqnarray*} \] 时间复杂度\(O(nlogk)\)
代码三：view code
#include <bits/stdc++.h> using namespace std; #define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); } #define fi first #define se second #define endl "\n" using ll = long long; using pII = pair <int, int>; using pLL = pair <ll, ll>; using VI = vector <int>; using VL = vector <ll>; constexpr int mod = 1e9 + 7; template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; } template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; } inline int rd() { int x; cin >> x; return x; } template <class T> inline void rd(T &x) { cin >> x; } template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; } template <class T> inline void out(T s) { cout << s << "\n"; } template <class T> inline void out(vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; } constexpr int N = 300 + 10; int n, K; ll f[N], C[N][N]; void run() { if (n == 1 || K == 1) return out(1); ll ans = 0; //枚举有i行没有1，然后保证每列至少有一个1，容斥 for (int i = 0; i < n; ++i) { ll f = (qpow(K, n - i) - qpow(K - 1, n - i) + mod) % mod; ll now = qpow(f, n) * C[n][i] % mod * qpow(K - 1, n * i) % mod; if (i & 1) chadd(ans, -now); else chadd(ans, now); } out(ans); } int main() { C[0][0] = 1; for (int i = 1; i < N; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(20); while (cin >> n >> K) run(); return 0; }转载于:https://www.cnblogs.com/Dup4/p/11610878.html
