int64_t a, b, p; void _main() { cin >> a >> b >> p; uint64_t c = (uint64_t) a * b - (uint64_t) (1.0L * a / p * b + 0.5L) * p; cout << (c < uint64_t(p) ? c : c + p); }
形式化一下题意,题意即为 ∄a,b∈S,a≡b(modp)。根据同余的差性质,等价为 $\nexists i \in \mathbb{N}^+, pi \mid (a-b) $。所以考虑 O(n2) 求出所有 si−sj 并标记。
仍然暴力枚举 k,再枚举 k 的倍数 ik,只要判断 ik 是否标记即可。复杂度 O(n2+klogk) 可以通过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
constint N = 5e3 + 5, M = 1e6 + 5; int n, a[N]; bool tag[M << 1];
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) tag[abs(a[i] - a[j])] = true; } for (int i = 1; i < M; i++) { if (tag[i]) continue; bool flag = true; for (int j = i; j < M; j += i) { if (tag[j]) {flag = false; break;} } if (flag) return cout << i, void(); } }
using ull = unsignedlonglong; ull n; const ull mod = 998244353; ull power(ull a, ull b){ ull res = 1; for (a %= mod; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
void _main() { cin >> n; ull b = 1; while (b <= n) b *= 10; cout << n % mod * (power(b, n) - 1) % mod * power(b - 1, mod - 2) % mod; }
法二:如果 10d−1 没有逆元,一个想法就是广义快速幂。定义 a×a 表示将 a 和 a 首尾拼接所得的数,求出 an 即可。复杂度 O(log2n)。
constint N = 2e5 + 5 int n, a[N], p[N], b[N]; longlong k; voidmul(int *a){ for (int i = 1; i <= n; i++) b[i] = a[p[i]]; copy(b + 1, b + n + 1, a + 1); }
void _main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> p[i]; for (int i = 1; i <= n; i++) cin >> a[i]; for (; k; k >>= 1) { if (k & 1) mul(a); mul(p); } for (int i = 1; i <= n; i++) cout << a[i] << ' '; }
2. 质数
定义一个正整数 p 为质数,即它不存在 1 和 p 以外的约数。1 不是质数。
2.1 质数分布
定义 π(n) 表示 [1,n] 中的质数数目,那么有 π(n)=O(lognn)。
这个规律在枚举质数的题目中用处很大。它说明了质数每隔 O(logn) 个数出现一次。
2.2 质数的判定
2.2.1 枚举法
可以枚举 [1,n] 中的整数,判定其是否为 p 的约数。因为 a∣p 时 ap∣p,所以无需枚举到 n。复杂度为 O(n)。
这里给出一个 61 常数的实现,筛掉 2 和 3 的倍数:
1 2 3 4 5 6 7 8 9
inlineboolisprime(int x){ if (x <= 1) returnfalse; if (x == 2 || x == 3) returntrue; if (x % 6 != 1 && x % 6 != 5) returnfalse; for (int i = 5; i * i <= x; i += 6) { if (x % i == 0 || x % (i + 2) == 0) returnfalse; } returntrue; }
*2.2.2 Miller-Rabin 法
先引入二次探测定理,即:若 p 为奇质数,则 x2≡1(modp) 的解为 x≡1 或 x≡p−1。
简证:由 x2≡1(modp) 得 (x−1)(x+1)≡0(modp),即可得出。
接下来使用费马小定理:若 p 为质数且 gcd(a,p)=1,则 ap−1≡1(modp)。这个结论的讲解可到文章下部。
设 p−1=u×2t,随机一个 a 值并求得 v=aumodp,然后执行 t 次 v←v2modp,检查是否满足 ap−1≡1(modp)。
在 long long 范围内,只需选取 a∈{2,325,9375,28178,450775,9780504,1795265022} 即可保证正确性。复杂度 O(logn)。这里给出一个比较科技的写法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
inlinelonglongpower(longlong a, longlong b, longlong p){ longlong res = 1; for (a %= p; b; b >>= 1) { if (b & 1) res = (__int128) res * a % p; a = (__int128) a * a % p; } return res; }
constlonglong BASE[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; inlineboolmiller_rabin(longlong n){ if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3; longlong s = __builtin_ctzll(n - 1), d = n >> s; for (longlong a : BASE) { longlong p = power(a, d, n), i = s; while (p != 1 && p != n - 1 && a % n && i--) p = (__int128) p * p % n; if (p != n - 1 && i != s) returnfalse; } returntrue; }
2.3 威尔逊定理
若 p 为质数,则
(p−1)!≡−1(modp)
其逆定理也成立。即若 (p−1)!≡−1(modp),则 p 为质数。
2.4 算术基本定理
任何一个合数 n 可以唯一分解成有限个质数的乘积。
存在性:用反证法,假设 n 是最小的不能被分解的合数,则存在 n=ab,若 a,b 都可分解,则 n 可以被分解;若 a,b 有不可分解的数,则 a,b 才是最小的数,矛盾。
唯一性:用反证法,假设 n 是最小的存在两种分解的合数,如果 n 存在两种分解 n=p1a1p2a2⋯=q1b1q2b2⋯,则 p1∣q1b1q2b2⋯,也就是 q1b1q2b2⋯ 中有一个 qibi 可以整除 p1,故 p1=qi,同除 p1,则 ${p_2}^{a_2} \cdots $ 也是存在两种分解的合数,矛盾。
int p[N], c[N]; intdecompose(int n){ int m = 0; for (int i = 2; i * i <= n; i++) { if (n % i) continue; p[++m] = i, c[m] = 0; while (n % i == 0) n /= i, c[m]++; } if (n > 1) p[++m] = n, c[m] = 1; return m; }
需要注意的是,如果知道 n 的值域,可以先用下面的质数筛打出一个质数表。根据质数分布规律,单次试除的复杂度降为 O(lognn)。
intsolve(int x){ int res = 0; for (int i = 1; i <= tot; i++) { if (x % p[i]) return INT_MAX; int cnt = 0; while (x % p[i] == 0) x /= p[i], cnt++; res = max(res, c[i] / cnt + (c[i] % cnt != 0)); } return res; }
void _main() { cin >> n >> m1 >> m2; for (int i = 1; i <= n; i++) cin >> a[i]; tot = decompose(m1); for (int i = 1; i <= tot; i++) c[i] *= m2; int res = INT_MAX; for (int i = 1; i <= n; i++) res = min(res, solve(a[i])); cout << (res == INT_MAX ? -1 : res); }
#define int long long constint N = 1e7 + 5; int l, r; bitset<N> s, p;
voidsolve(int a, int b){ s.set(), p.set(); int z = (int) sqrt(b) + 1; for (int i = 2; i < z; i++) { for (int j = 2; i * j < z; j++) s[i * j] = false; } for (int i = 2; i * i <= b; i++) { if (!s[i]) continue; for (int j = max(i * i, (a + i - 1) / i * i); j < b; j += i) p[j - a] = false; } for (int i = 2; i * i <= b; i++) { if (!s[i]) continue; int j = i * i; while (j < a) j *= i; for (; j < b; j *= i) p[j - a] = true; } }
void _main() { cin >> l >> r; if (l == r) return cout << 1, void(); solve(l, r + 1); int cnt = 0; for (int i = l; i <= r; i++) cnt += p[i - l]; if (!p[0]) cnt++; cout << cnt; }
[模拟赛] 舔狗的付出
给你一个十进制正整数 x,在 x 后面添加若干数字使它成为一个质数,可以不添加,求这个质数的最小值。
longlongmpow(longlong a, longlong b, longlong p){ longlong res = 1; for (a %= p; b; a = a * a % p, b >>= 1) { if (b & 1) res = res * a % p; } return res; } voiddecompose(int x, map<int, int>& mp){ for (int i = 2; i * i <= x; i++) { while (x % i == 0) mp[i]++, x /= i; } if (x != 1) mp[x]++; }
void _main() { cin >> n >> q; map<int, int> mp; decompose(n, mp); map<int, int> cur = mp; while (q--) { cin >> opt; if (opt == 1) { cin >> x; decompose(x, cur); longlong a = 1, b = 1; for (constauto& i : cur) b *= i.second + 1; for (constauto& i : cur) a = a * mpow(i.first, i.second, b) % b; cout << (a % b ? "NO\n" : "YES\n"); } else cur = mp; } cout << '\n'; }
constint N = 1e5 + 5; int n, q, opt, x; longlong y; vector<int> fac[N]; vector<int> decompose(int x){ vector<int> res; for (int i = 2; i * i <= x; i++) { if (x % i) continue; res.emplace_back(i); while (x % i == 0) x /= i; } if (x != 1) res.emplace_back(x); return res; }
structnode { longlong val; int id, time; node(longlong a = 0, longlong b = 0, longlong c = 0) : val(a), id(b), time(c) {} booloperator< (const node& a) const {return val > a.val;} }; priority_queue<node> heap[N];
longlong lastans, tim, num, a[N], b[N], last[N], c[N], f[N]; vector<longlong> nw, res; voidrebuild(const node& x){ int id = x.id; if (last[id] == -1) return; longlong sum = 0; for (int i : fac[a[id]]) sum += c[i]; if (sum >= f[id] + b[id]) return res.emplace_back(id), last[id] = -1, void(); // id报警 b[id] += f[id] - sum, f[id] = sum, last[id] = ++tim; longlong cnt = fac[a[id]].size(), d = (b[id] + cnt - 1) / cnt; for (int i : fac[a[id]]) heap[i].push(node{c[i] + d, id, tim}); } voidcheck(int x){ while (!heap[x].empty() && heap[x].top().val <= c[x]) { node u = heap[x].top(); heap[x].pop(); if (last[u.id] != u.time) continue; // 懒删除 rebuild(u); } } voidask(){ res.clear(), res.insert(res.end(), nw.begin(), nw.end()); nw.clear(); for (int i : fac[x]) c[i] += y; for (int i : fac[x]) check(i); sort(res.begin(), res.end()); cout << (lastans = res.size()) << ' '; for (int i : res) cout << i << ' '; cout << '\n'; } voidadd(){ longlong cnt = fac[x].size(), d = (y + cnt - 1) / cnt; tim++, num++; if (y == 0) return nw.emplace_back(num), void(); a[num] = x, b[num] = y, last[num] = tim; for (int i : fac[x]) f[num] += c[i], heap[i].push(node{c[i] + d, num, tim}); }
void _main() { cin >> n >> q; for (int i = 2; i <= n; i++) fac[i] = decompose(i); while (q--) { cin >> opt >> x >> y; y ^= lastans; if (opt == 0) ask(); elseadd(); } }
template <classT> constexpr T gcd(T a, T b){ int az = ctz(a), bz = ctz(b), z = min(az, bz); for (b >>= bz; a; ) { a >>= az; int d = a - b; az = ctz(a - b), b = min(a, b), a = abs(d); } return b << z; }
将 x 分解质因数为 p1c1p2c2p3c3⋯。注意到 (axby)z=axzbxz。所以 p=gcd(c1,c2,c3,⋯)。
需要注意 x 不一定是正数。此时 p 不能是偶数,不然 ap 就是正数了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#define int long long int x; void _main() { while (cin >> x, x) { vector<int> c; bool neg = x < 0; x = abs(x); for (int i = 2; i * i <= x; i++) { if (x % i) continue; c.emplace_back(0); while (x % i == 0) x /= i, c.back()++; } if (x != 1) c.emplace_back(1); int g = 0; for (int i : c) g = __gcd(g, i); if (neg) g >>= __builtin_ctzll(g); cout << g << '\n'; } }
说明 (cnm−d)∣x。O(x) 地枚举 x 的因子 i。移项有 cnm=d+i,即 c∣(d+i)。再将 cd+i 分解质因数,对于每种质因子只有全给 n 和全给 m 两种选择,否则会使得 $(cnm-d) \nmid x $。用线性筛先得到每个数的质因子个数,则贡献为 2cnt。复杂度 O(n+Tn)。
constint N = 2e7 + 5; bitset<N> isprime; int cnt[N], prime[N]; voidinit(){ isprime.set(), isprime[0] = isprime[1] = false; for (int i = 2; i < N; i++) { if (isprime[i]) prime[++prime[0]] = i, cnt[i] = 1; for (int j = 1; j <= prime[0] && 1LL * i * prime[j] < N; j++) { isprime[i * prime[j]] = false; if (i % prime[j] == 0) { cnt[i * prime[j]] = cnt[i]; break; } cnt[i * prime[j]] = cnt[i] + 1; } } }
longlong c, d, x; longlongf(int x){ if ((x + d) % c) return0; return1LL << cnt[(x + d) / c]; } void _main() { cin >> c >> d >> x; longlong res = 0; for (longlong i = 1; i * i <= x; i++) { if (x % i) continue; res += f(i); if (i * i != x) res += f(x / i); } cout << res << '\n'; }
分四种情况讨论。以 m1=m2=0 为例,等式两边同除 2可得 gcd(a,b)∣2x,即 2gcd(a,b)∣x,对于 y 同理。
以 m1=0,m2=1 为例,同加 b 再同除 2,化简得到 2gcd(a,b)∣(x+b)。
剩下两种类似。四种可能或起来即可。
1 2 3 4 5 6 7 8 9 10 11 12 13
longlong a, b, x, y;
void _main() { cin >> a >> b >> x >> y; longlong g = __gcd(a, b); if (x % g || y % g) return cout << "N\n", void(); g *= 2; if (x % g == 0 && y % g == 0) return cout << "Y\n", void(); if ((x + b) % g == 0 && (y + a) % g == 0) return cout << "Y\n", void(); if ((x + a) % g == 0 && (y + b) % g == 0) return cout << "Y\n", void(); if ((x + a + b) % g == 0 && (y + a + b) % g == 0) return cout << "Y\n", void(); cout << "N\n"; }
#define int long long constint N = 2.5e5 + 5; int n, k, a[N]; boolcheck(int x){ for (int i = 1; i < k; i++) { if (a[i] % x == 0) returnfalse; } returntrue; }
void _main() { cin >> n >> k; for (int i = 1; i <= k; i++) cin >> a[i]; int x = __gcd(n, a[k]); for (int i = 1; i * i <= x; i++) { if (x % i) continue; if (check(i)) return cout << n / i, void(); } for (int i = sqrt(x) + 1; i >= 1; i--) { if (x % i) continue; if (check(x / i)) return cout << n / (x / i), void(); } }
考虑优化。枚举因子最多只有 107,思考如何快速 check。首先令 ai←gcd(ai,x),显然不影响结果。接着对 x 质因数分解。注意到 2×3×5×7×11×13×17×19×23×29×31×37×41×43>1014,考虑对于每个 ai 直接按质因子爆搜因数。使用哈希表记忆化搜索,复杂度大概是 O(klogV+V+d(V)ω(V))。
#define int long long constint N = 2.5e5 + 5; int n, k, a[N]; boolcheck(int x){ for (int i = 1; i < k; i++) { if (a[i] % x == 0) returnfalse; } returntrue; } vector<int> p; voiddecompose(int x){ for (int i = 2; i * i <= x; i++) { if (x % i) continue; p.emplace_back(i); while (x % i == 0) x /= i; } if (x != 1) p.emplace_back(x); } unordered_set<int> f; voiddfs(int x){ if (f.count(x)) return; f.emplace(x); for (int i : p) { if (x % i == 0) dfs(x / i); } }
void _main() { cin >> n >> k; for (int i = 1; i <= k; i++) cin >> a[i]; int x = __gcd(n, a[k]); decompose(x); for (int i = 1; i < k; i++) dfs(__gcd(a[i], x)); for (int i = 1; i * i <= x; i++) { if (x % i) continue; if (!f.count(i)) return cout << n / i, void(); } for (int i = sqrt(x) + 1; i >= 1; i--) { if (x % i) continue; if (!f.count(x / i)) return cout << n / (x / i), void(); } }
template <classT> voidexgcd(T a, T b, T& x, T& y){ if (b == 0) return x = 1, y = 0, void(); exgcd(b, a % b, y, x), y -= a / b * x; } longlong x, y, m, n, L;
void _main() { cin >> x >> y >> m >> n >> L; longlong a = n - m, b = L, c = x - y; if (a < 0) a = -a, c = -c; longlong d = __gcd(a, b); if (c % d) return cout << "Impossible", void(); a /= d, b /= d, c /= d; longlong x0, y0; exgcd(a, b, x0, y0); longlong x1 = c * x0; cout << ((x1 > 0 && x1 % b != 0) ? x1 % b : x1 % b + b); }
constint N = 2005; #define int long long voidexgcd(int a, int b, int& x, int &y){ if (b == 0) return x = 1, y = 0, void(); exgcd(b, a % b, y, x), y -= a / b * x; } int w, n, d, x[N];
void _main(int kase) { cout << "Case #" << kase << ": "; cin >> w >> n >> d; for (int i = 1; i <= w; i++) cin >> x[i]; int g = __gcd(n, d), n0 = n / g, res = 0; for (int i = 1; i <= w / 2; i++) { if ((x[i] - x[w - i + 1]) % g) return cout << "IMPOSSIBLE\n", void(); int a, b; exgcd(d, n, a, b); int p = a * ((x[w - i + 1] - x[i]) / g % n0) % n0; if (p >= 0) p %= n0, res += min(p, n0 - p); else { int q = p + n0 * ceil(-1.0 * p / n0); res += min(q, n0 - q); } } cout << res << '\n'; }
template <classT> voidexgcd(T a, T b, T& x, T& y){ if (!b) return x = 1, y = 0, void(); exgcd(b, a % b, y, x), y -= a / b * x; } template <classT> T crt(int n, const T* a, const T* m){ T x = 0, y = 0, p = m[1], res = a[1]; for (int i = 2; i <= n; i++) { T a0 = p, b0 = m[i], c = (a[i] - res % b0 + b0) % b0, g = __gcd(a0, b0); if (c % g) return-1; exgcd(a0, b0, x, y); x = (__int128) x * c / g % b0, res += x * p, p = p / __gcd(p, b0) * b0, res = (res % p + p) % p; } return res; }
int n; longlong a[N], m[N];
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> m[i] >> a[i]; cout << crt(n, a, m); }
inlineintphi(int n){ if (n == 1) return1; int res = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { res = res / i * (i - 1); while (n % i == 0) n /= i; } } if (n > 1) res = res / n * (n - 1); return res; }
int n; void _main() { cin >> n; if (n == 1) return cout << 0, 0; int res = 1; eular(40000); for (int i = 1; i < n; i++) res += 2 * phi[i]; cout << res; }
#define int long long int n; inlineintphi(int n){ if (n == 1) return1; int res = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { res = res / i * (i - 1); while (n % i == 0) n /= i; } } if (n > 1) res = res / n * (n - 1); return res; }
inlinevoid _main() { cin >> n; longlong res = 0; for (int i = 1; i * i <= n; i++) { if (n % i) continue; res += i * phi(n / i); if (i * i != n) res += n / i * phi(n / (n / i)); } cout << res; }
longlong p; longlongpower(longlong a, longlong b, longlong p){ longlong res = 1; for (a %= p; b; a = a * a % p, b >>= 1) { if (b & 1) res = res * a % p; } return res; } longlongf(longlong p){return p == 1 ? 0 : power(2, f(phi[p]) + phi[p], p);}
constint N = 2e5 + 5; int n, q, opt, l, r, a[N]; #define ls (rt << 1) #define rs (rt << 1 | 1) int val[N << 2], mx[N << 2], cnt[N << 2], cmin[N << 2], tag[N << 2]; voidpushup(int rt){mx[rt] = max(mx[ls], mx[rs]), cmin[rt] = min(cmin[ls], cmin[rs]);} voidpushdown(int rt){ if (!tag[rt]) return; cnt[ls] += tag[rt], cnt[rs] += tag[rt], cmin[ls] += tag[rt], cmin[rs] += tag[rt]; tag[ls] += tag[rt], tag[rs] += tag[rt], tag[rt] = 0; } voidbuild(int l = 1, int r = n, int rt = 1){ cnt[rt] = cmin[rt] = tag[rt] = 0; if (l == r) return val[rt] = mx[rt] = a[l], void(); int mid = (l + r) >> 1; build(l, mid, ls), build(mid + 1, r, rs), pushup(rt); } voidadd(int tl, int tr, int l = 1, int r = n, int rt = 1){ if (tl <= l && r <= tr) return cnt[rt]++, cmin[rt]++, tag[rt]++, void(); int mid = (l + r) >> 1; pushdown(rt); if (tl <= mid) add(tl, tr, l, mid, ls); if (tr > mid) add(tl, tr, mid + 1, r, rs); pushup(rt); } voidsub(int tl, int tr, int l = 1, int r = n, int rt = 1){ if (mx[rt] <= 1) return; if (tl <= l && r <= tr && cmin[rt] >= 1) return cnt[rt]--, cmin[rt]--, tag[rt]--, void(); if (l == r) { if (cnt[rt]) cnt[rt]--, cmin[rt]--; else mx[rt] = val[rt] = sqrt(val[rt]); return; } int mid = (l + r) >> 1; pushdown(rt); if (tl <= mid) sub(tl, tr, l, mid, ls); if (tr > mid) sub(tl, tr, mid + 1, r, rs); pushup(rt); } mod998244353 ask(int x, int l = 1, int r = n, int rt = 1){ if (l == r) { mod998244352 v = mod998244352(2).pow(cnt[rt]); returnmod998244353(val[rt]).pow(static_cast<int>(v)); } int mid = (l + r) >> 1; pushdown(rt); return x <= mid ? ask(x, l, mid, ls) : ask(x, mid + 1, r, rs); }
void _main() { cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; build(); while (q--) { cin >> opt >> l >> r; if (opt == 1) sub(l, r); elseadd(l, r); } mod998244353 res = 0; for (int i = 1; i <= n; i++) res += ask(i); cout << res; }
longlongpower(longlong a, longlong b, longlong p){ longlong res = 1; for (a %= p; b; a = (__int128) a * a % p, b >>= 1) { if (b & 1) res = (__int128) res * a % p; } return res; } vector<longlong> factors(longlong n){ vector<longlong> res; for (longlong i = 1; i * i <= n; i++) { if (n % i) continue; res.emplace_back(i); if (n / i != i) res.emplace_back(n / i); } sort(res.begin(), res.end()); return res; }
longlong n;
void _main() { for (int kase = 1; ; kase++) { cin >> n; if (n == 0) break; cout << "Case " << kase << ": "; n = 9 * n / __gcd(n, 8LL); if (__gcd(n, 10LL) != 1) {cout << "0\n"; continue;} vector<longlong> f = factors(phi(n)); for (longlong x : f) { if (power(10, x, n) == 1) {cout << x << '\n'; break;} } } }
intpower(int a, int b, int p){ int res = 1; for (a %= p; b; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
namespace Lucas { int fac[N], ifac[N]; inlinevoidinit(int p){ fac[0] = fac[1] = ifac[0] = ifac[1] = 1; for (int i = 2; i <= p; i++) fac[i] = fac[i - 1] * i % p, ifac[i] = power(fac[i], p - 2, p); } inlineintC(int n, int m, int p){ if (n < m) return0; return fac[n] * ifac[m] % p * ifac[n - m] % p; } intlucas(int n, int m, int p){ if (m == 0) return1; if (n < p && m < p) returnC(n, m, p); returnlucas(n / p, m / p, p) * C(n % p, m % p, p) % p; } }
namespace CRT { template <classT> voidexgcd(T a, T b, T& x, T& y){ if (!b) return x = 1, y = 0, void(); exgcd(b, a % b, y, x), y -= a / b * x; } template <classT> T crt(int n, const T* a, const T* m){ T x = 0, y = 0, p = m[1], res = a[1]; for (int i = 2; i <= n; i++) { T a0 = p, b0 = m[i], c = (a[i] - res % b0 + b0) % b0, g = __gcd(a0, b0); if (c % g) return-1; exgcd(a0, b0, x, y); x = (__int128) x * c / g % b0, res += x * p, p = p / __gcd(p, b0) * b0, res = (res % p + p) % p; } return res; } }
constint P[] = {0, 2, 3, 4679, 35617}; int a[5];
void _main() { cin >> n >> g; if (__gcd(g, 999911659LL) != 1) return cout << 0, void(); // 注意判无解 for (int i = 1; i <= 4; i++) { Lucas::init(P[i]); for (int d = 1; d * d <= n; d++) { if (n % d) continue; a[i] = (a[i] + Lucas::lucas(n, d, P[i])) % P[i]; if (n / d != d) a[i] = (a[i] + Lucas::lucas(n, n / d, P[i])) % P[i]; } } int val = CRT::crt(4, a, P); if (val == -1) return cout << 0, void(); // 注意判无解 cout << power(g, val, 999911659); }
#define int long long int n; intcnt(int n){ int res = 0; for (int i = 1; i <= n; i <<= 1) { for (int j = 1; j <= n; j *= 5) { if (1LL * i * j > n) break; res++; } } return res; } intg(int l, int r, int d){return r / d - (l - 1) / d;}
void _main() { cin >> n; int res = 0; for (int l = 1, r = 0; l <= n; l = r + 1) { r = min(n, n / (n / l)); res += cnt(n / l) * (n / l) * (r - l + 1 - g(l, r, 2) - g(l, r, 5) + g(l, r, 10)); } cout << res; }
constint N = 2e5 + 5; int n, a[N], b[N], p[N], q[N]; longlongcalc(int len){return1LL * len * (len - 1) / 2;}
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], p[a[i]] = i; for (int i = 1; i <= n; i++) cin >> b[i], q[b[i]] = i; int s = p[1], t = q[1]; if (s > t) swap(s, t); longlong res = 0; if (1 <= s - 1) res += calc(s); if (t + 1 <= n) res += calc(n - t + 1); if (s < t) res += calc(t - s);
int l = s, r = t; for (int m = 2; m <= n; m++) { s = p[m], t = q[m]; if (s > t) swap(s, t); if ((l <= s && s <= r) || (l <= t && t <= r)) { l = min(l, s), r = max(r, t); continue; } if (s < l && t < l) res += 1LL * (n - r + 1) * (l - t); if (s > r && t > r) res += 1LL * l * (s - r); if (s < l && r < t) res += 1LL * (l - s) * (t - r); l = min(l, s), r = max(r, t); } cout << res; }
void _main() { cin >> n >> m >> k; for (int i = 0; i <= m; i++) dp[i][0] = 1; for (int i = 1; i <= m; i++) { mint sum = i; for (int j = 1; j <= n; j++) { dp[i][j] = sum, sum += dp[i - 1][j + 1]; if (j >= k) sum -= dp[i - 1][j - k]; } } cout << dp[m][n]; }
constint N = 105, M = 2005; int n, m; mint a[N][M], sum[N], f[N][N << 1];
mint solve(int x){ f[0][n] = 1; for (int i = 1; i <= n; i++) { for (int j = -n; j <= n; j++) { f[i][j + n] = 0; f[i][j + n] += f[i - 1][j - 1 + n] * a[i][x]; f[i][j + n] += f[i - 1][j + 1 + n] * (sum[i] - a[i][x]); f[i][j + n] += f[i - 1][j + n]; } } mint res = 0; for (int i = 1; i <= n; i++) res += f[n][i + n]; return res; }
void _main() { cin >> n >> m; mint res = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cin >> a[i][j], sum[i] += a[i][j]; res *= sum[i] + 1; } for (int i = 1; i <= m; i++) res -= solve(i); cout << res - 1; }
constint N = 1e5 + 5; int k, n, m, x[N], y[N]; structnode { int l, r; } a[N], b[N]; discrete_map<int, N << 2> mp; mint f[2][N];
void _main() { cin >> k >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r, mp.add(a[i].r); if (a[i].l != 1) mp.add(a[i].l - 1); } for (int i = 1; i <= m; i++) { cin >> b[i].l >> b[i].r, mp.add(b[i].r); if (b[i].l != 1) mp.add(b[i].l - 1); } mp.add(1), mp.add(k), mp(); for (int i = 1; i <= n; i++) x[mp[a[i].r]] = max(x[mp[a[i].r]], mp[a[i].l]); for (int i = 1; i <= m; i++) y[mp[b[i].r]] = max(y[mp[b[i].r]], mp[b[i].l]); f[0][0] = (x[1] == 0), f[1][0] = (y[1] == 0); mint s0 = f[0][0], s1 = f[1][0], v = 0; int a = 0, b = 0; for (int i = 1; i < mp.width; i++) { int len = mp.value(i + 1) - mp.value(i); mint p = mint(2).pow(len) - 2; if (i >= x[i + 1]) f[0][i] = s1 + v; if (i >= y[i + 1]) f[1][i] = s0 + v; if (len > 1) v += s0 + s1, v *= p; else v = 0; s0 += f[0][i], s1 += f[1][i]; for (; a < x[i + 1]; a++) s0 -= f[0][a]; for (; b < y[i + 1]; b++) s1 -= f[1][b]; } cout << v + s0 + s1; }
8. 容斥原理
容斥原理是加法 & 减法原理的推广。
8.1 引入
用一个例题引入:假设班里有 a 个学生喜欢语文,b 个学生喜欢数学,c 个数学喜欢英语,则班里至少喜欢一门学科的有多少个学生?
可以发现 gcd(i,j) 的值只有 n 种,不妨考虑 gcd(i,j)=k 的数目,设其数目为 f(k)。我们可以考虑求以 k 为公约数的数对数目,再减去以 k 的倍数为公约数的数对数目。进一步推导,以 k 的倍数为公约数的数对个数等于所有以 k 的倍数为最大公约数的数对个数之和。于是有
f(k)=⌊kn⌋×⌊km⌋−i=2∑ik≤min(n,m)f(ik)
我们发现 2k>min(n,m) 时 f(k)=⌊kn⌋×⌊km⌋,于是倒着算就行了,是调和型枚举,复杂度 O(nlogn)。于是 GCD SUM 问题就多了一种容斥做法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
constint N = 1e5 + 5; longlong f[N]; int n, m;
void _main() { cin >> n >> m; for (int k = n; k >= 1; k--) { f[k] = 1LL * (n / k) * (m / k); for (int i = 2; i * k <= min(n, m); i++) f[k] -= f[i * k]; } longlong res = 0; for (int i = 1; i <= n; i++) res += f[i] * i; cout << res * 2 - 1LL * n * m; }
笔者数论训练赛の T5。和上面题的套路一样,我们发现,gcdai=k 时当且仅当 a1,a2,⋯,an 均为 k 的倍数,且这个倍数是互质的。考虑容斥 + DP,令 dpx 表示 [1,x] 内选出 n 个互质数的方法数目。考虑用减法原理,总数目减去不互质的方案,枚举公约数 i,则根据约数性质可得
dpx=xn−i=2∑xdp⌊ix⌋
赛时写的记搜。可以发现这个东西就是高维容斥。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
int n, k; mint dp[N]; mint solve(int x){ if (dp[x] != 0) return dp[x]; if (x == 1) return dp[x] = 1; mint res = mint(x).pow(n); for (int i = 2; i <= x; i++) { res -= solve(x / i); } return dp[x] = res; }
void _main() { cin >> n >> k; mint res = 0; for (int i = 1; i <= k; i++) res += solve(k / i) * i; cout << res; }
constint N = 65; int n, m, k, u, v; pair<int, int> a[N]; int tot = 1, head[N]; structEdge { int next, to; } edge[N << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } int fa[N], sz[N]; intfind(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);} voidunite(int x, int y){fa[find(x)] = find(y);}
vector<int> p[N]; booldfs(int u, int fa, int to, vector<int>& vec){ if (u == to) returntrue; for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; if (v == fa) continue; vec.emplace_back(j >> 1); if (dfs(v, u, to, vec)) returntrue; vec.pop_back(); } returnfalse; }
void _main() { cin >> n >> m >> k; for (int i = 1; i < n; i++) cin >> u >> v, add_edge(u, v), add_edge(v, u); for (int i = 1; i <= m; i++) { cin >> a[i], dfs(a[i].first, -1, a[i].second, p[i]); } mint res = 0; for (int s = 0; s < (1 << m); s++) { iota(fa + 1, fa + n + 1, 1); for (int i = 1; i <= m; i++) { if (!(s >> (i - 1) & 1)) continue; for (int j = 1; j < (int) p[i].size(); j++) unite(p[i][j - 1], p[i][j]); } int part = 0; for (int i = 1; i < n; i++) part += (i == find(i)); if (popcount(s) & 1) res -= mint(k).pow(part); else res += mint(k).pow(part); } cout << res; }
#define int long long constint N = 1e5 + 5; int a, b, c, d, s, c1, c2, c3, c4, q, dp[N]; voidwork(int x){ for (int i = x; i < N; i++) dp[i] += dp[i - x]; } intf(int x){return x < 0 ? 0 : dp[x];}
void _main() { cin >> c1 >> c2 >> c3 >> c4; dp[0] = 1; work(c1), work(c2), work(c3), work(c4); for (cin >> q; q--; ) { cin >> a >> b >> c >> d >> s; a = (a + 1) * c1, b = (b + 1) * c2, c = (c + 1) * c3, d = (d + 1) * c4; cout << f(s) - f(s - a) - f(s - b) - f(s - c) - f(s - d) + f(s - a - b) + f(s - a - c) + f(s - a - d) + f(s - b - c) + f(s - b - d) + f(s - c - d) - f(s - a - b - c) - f(s - a - b - d) - f(s - a - c - d) - f(s - b - c - d) + f(s - a - b - c - d) << '\n'; } }
int tot = 0, head[N]; structEdge { int next, to; } edge[M]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } int n, m, u, v, q, len, ideg[N], odeg[N];
int cnt, bfn[N]; mint dp[N][N], f[N], g[N], h[20]; voidtopo(){ queue<int> q; for (int i = 1; i <= n; i++) { if (ideg[i] == 0) q.emplace(i); dp[i][i] = 1; } while (!q.empty()) { int u = q.front(); q.pop(); bfn[u] = ++cnt; for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; for (int k = 1; k <= n; k++) dp[k][v] += dp[k][u]; if (--ideg[v] == 0) q.emplace(v); } } }
vector<int> st, ed; void _main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u >> v; add_edge(u, v); odeg[u]++, ideg[v]++; } for (int i = 1; i <= n; i++) { if (ideg[i] == 0) st.emplace_back(i); if (odeg[i] == 0) ed.emplace_back(i); } topo(); mint tot = 0; for (int i : st) { for (int j : ed) tot += dp[i][j]; } for (int i = 1; i <= n; i++) { for (int j : st) f[i] += dp[j][i]; for (int j : ed) g[i] += dp[i][j]; } for (cin >> q; q--; ) { fill(h, h + len, 0); cin >> len; vector<int> c; for (int i = 0; i < len; i++) cin >> u, c.emplace_back(u); sort(c.begin(), c.end(), [](int x, int y) -> bool { return bfn[x] < bfn[y]; }); for (int i = 0; i < len; i++) { h[i] = f[c[i]]; for (int j = 0; j < i; j++) h[i] -= dp[c[j]][c[i]] * h[j]; } mint res = 0; for (int i = 0; i < len; i++) res += h[i] * g[c[i]]; cout << tot - res << '\n'; } }
constint N = 5e5 + 5; int n, x, a[N], b[N], c[N], d[N], tr[N]; voidadd(int x, int c){ for (; x <= n; x += lowbit(x)) tr[x] += c; } intask(int x){ int res = 0; for (; x >= 1; x -= lowbit(x)) res += tr[x]; return res; } longlongsolve(int *a, int *b){ fill(tr + 1, tr + n + 1, 0); longlong res = 0; for (int i = 1; i <= n; i++) d[b[i]] = a[i]; for (int i = 1; i <= n; i++) res += ask(d[i]), add(d[i], 1); return res; }
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> x; for (int i = 1; i <= n; i++) cin >> x, a[x] = i; for (int i = 1; i <= n; i++) cin >> x, b[x] = i; for (int i = 1; i <= n; i++) cin >> x, c[x] = i; cout << (solve(a, b) + solve(a, c) + solve(b, c) - 1LL * n * (n - 1) / 2) / 2; }
9. 排列组合
还有一些较难的内容放到进阶部分了。
9.1 排列
从 n 个不同元素中取 m 个元素排成有序的一列,方案数用 Anm 表示。
我们这样计算:第一个数有 n 种选法,第二个数有 n−1 种选法……第 m 个数有 n−m+1 种选法,由乘法原理得
Anm=n(n−1)(n−2)⋯(n−m+1)=i=n−m+1∏ni=(n−m)!n!
规定 m>n 时 Anm=0。
而如果 m=n,也就是所有元素都参与排列,此时称为全排列。全排列的计算
Ann=n!
9.1.1 全排列的枚举
在 C++ STL 中提供了 next_permutation 函数,可以这样使用:
1 2 3 4 5
// a为要枚举排列的数组,n为长度 sort(a + 1, a + n + 1); do { ... } while (next_permutation(a + 1, a + n + 1));
时间复杂度为 O(n!)。
9.1.2 多重集的排列数
就是元素有重,此时需要除去重复的排列。
考虑一组有 m 个的重复元素,其造成重复的个数就是它在排列中的次序交换,也就是 m! 种情况,所以总排列数
m1!m2!m3!⋯n!=∏mi!n!
其中 n 为总元素个数,m 为各元素出现次数。
9.1.3 圆排列
从 n 个不同元素中取 m 个元素排成有序的一圈,方案数用 Qnm 表示。考虑断环为链,共有 m 个断点,故
Qnm=mAnm=m(n−m)!n!
特别地,Qnn=nAnn=(n−1)!。
9.2 组合
从 n 个不同元素中取 m 个元素组成无序的一个集合,方案数用 Cnm 表示。
考虑先作排列,由于集合无序,需要除去重复的组合,也就是 m 的全排列,逆用乘法原理:
Cnm=m!Anm=m!(n−m)!n!
规定 m>n 时 Cnm=0。
9.2.1 组合的枚举
代码如下:
1 2 3 4 5 6 7
int n, m, cur[N]; voiddfs(int x){ if (x > m) return ..., void(); // 这里cur就是一个组合,进行处理 for (int i = cur[x - 1] + 1; i <= n; i++) cur[x] = i, dfs(x + 1); }
dfs(1);
它用于枚举 1 到 n 所有自然数选 m 个的组合。如果套上 next_permutation,还能实现排列的枚举。
9.2.2 二项式定理
(a+b)n=i=0∑nCnian−ibi
这个定理表明,二项式 (a+b)n 展开项的系数与组合数有直接关系。
我们知道杨辉三角:
其每一个位置的数字通过左上 + 右上确定,每一行所对应的就是二项式展开的系数。
9.2.3 组合数的性质
对称性:
Cnm=Cnn−m
代数推导易证,组合意义就是把选出的集合取补集。
递推式:
Cnm=Cn−1m+Cn−1m−1
代数推导略去,组合意义类似 DP 的思想可以证明。这个式子实际上就是杨辉三角的递推式。
二项式定理的特殊情况 1:
2n=i=0∑nCni
也就是杨辉三角每一行的和。
斐波那契数列:
fibn+1=i=0∑nCn−ii
把杨辉三角每条斜 30° 角的线取出来相加可以发现。
范德蒙恒等式:
Cm+nk=i=0∑kCmiCnk−i
假设有两堆物品,每堆分别有 m,n 个物品,总共取 k 个,则方案数可分解为:从第一堆取 i 个物品,第二堆取 k−i 个物品,且两种选择独立,故由乘法得到贡献。最后方案即为求和。
二项式定理的特殊情况 2:
i=0∑n(−1)iCni=0
特殊情况是 n=0 时上式的值为 1。
9.2.4 计算组合数
定义法
优点:写起来简单,不用预处理。
缺点:查询复杂度 O(m)。
根据定义直接计算,注意先乘后除。
1 2 3 4 5 6 7 8
inlinelonglongC(int n, int m){ if (m > n) return0; longlong res = 1; for (int i = 1; i <= m; i++) { res = res * (n - i + 1) % mod * power(i, mod - 2) % mod; } return res; }
递推法
优点:任意模数,写起来简单,查询 O(1)。
缺点:预处理时空复杂度均为 O(n2)。
即利用组合数性质 2 预处理杨辉三角。
1 2 3 4
for (int i = 0; i < N; i++) c[i][0] = 1, c[i][i] = 1; for (int i = 0; i < N; i++) { for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; }
逆元法
优点:预处理可做到 O(n),查询 O(1)。
缺点:只能在模数为质数时使用。
通过预处理阶乘和阶乘的逆元,直接用定义式计算组合数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
inlinelonglongpower(longlong a, longlong b){ longlong res = 1; for (a %= mod; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
longlong fac[N], ifac[N]; inlinevoidpre(){ fac[0] = fac[1] = ifac[0] = ifac[1] = 1; for (int i = 2; i < N; i++) fac[i] = fac[i - 1] * i % mod, ifac[i] = power(fac[i], mod - 2); }
inlinelonglongC(int n, int m){ if (n < m) return0; return fac[n] * ifac[m] % mod * ifac[n - m] % mod; }
inlinelonglongpower(longlong a, longlong b){ longlong res = 1; for (a %= mod; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
longlong fac[N], ifac[N]; inlinevoidpre(){ fac[0] = fac[1] = ifac[0] = ifac[1] = 1; for (int i = 2; i < N; i++) fac[i] = fac[i - 1] * i % mod, ifac[i] = power(fac[i], mod - 2); }
inlinelonglongC(int n, int m){ if (n < m) return0; return fac[n] * ifac[m] % mod * ifac[n - m] % mod; } longlonglucas(longlong n, longlong m){ if (m == 0) return1; if (n < mod && m < mod) returnC(n, m); returnlucas(n / mod, m / mod) * C(n % mod, m % mod) % mod; }
int k, x; BigInteger C(int n, int m){ if (n < m) return0; BigInteger res = 1; for (int i = 1; i <= m; i++) { res *= n - i + 1; res /= i; } return res; }
void _main() { cin >> k >> x; x = i_pow(x, x, 1000).to_int64(); cout << C(x - 1, k - 1); }
constint N = 2e5 + 5; int n, m; mint fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];}
void _main() { cin >> n >> m; fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; mint res = 1; for (int i = 2; i * i <= m; i++) { if (m % i) continue; int c = 0; while (m % i == 0) m /= i, c++; res *= C(n + c - 1, n - 1); } if (m != 1) res *= n; cout << res; }
constint N = 2e3 + 5; int a, b, c, d, k; mint fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];} mint f(int n, int m, int k){returnC(n, k) * C(m, k) * fac[k];}
void _main() { fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; cin >> a >> b >> c >> d >> k; mint res = 0; for (int i = 0; i <= k; i++) { res += f(a, b, i) * f(a + c - i, d, k - i); } cout << res; }
考虑二分查找的过程,由于 n 是固定的,则二分查找的路径是唯一的,因此我们可以求出一定小于等于 x 的数的个数,一定大于 x 的数的个数,分别记作 a,b。那么在小于等于 x 的 x−1 个数中,就要找 a−1 个数出来排列(因为还有一个数等于 x) ,而大于 x 的 n−x 个数中找 b 个来排列,剩下的任意排列,是全排列。
由乘法原理可得答案
Ax−1a−1An−xbAn−a−bn−a−b
计算排列数也可以用逆元法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
constint N = 1005; int n, x, pos; mint fac[N], ifac[N]; mint A(int m, int n){ if (m > n) return0; return fac[n] * ifac[n - m]; }
void _main() { cin >> n >> x >> pos; int l = 0, r = n, a = 0, b = 0; while (l < r) { int mid = (l + r) >> 1; if (mid <= pos) l = mid + 1, a++; else r = mid, b++; } fac[0] = 1, ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; cout << A(a - 1, x - 1) * A(b, n - x) * A(n - a - b, n - a - b); }
constint N = 5e5 + 5; int n, p[N], q[N]; mint factorial(int x){ mint res = 1; for (int i = 2; i <= x; i++) res *= i; return res; } void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> p[i]; for (int i = 1; i <= n; i++) cin >> q[i]; int i = 1, j = 1; for (int x = 1; x <= n; x++) { if (p[x] == n) i = x; if (q[x] == n) j = x; } if (i == j) cout << "2 " << factorial(n - 1); else cout << "3 " << factorial(n - 1) / (n - q[i]) + factorial(n - 1) / (n - p[j]); }
#define int long long int a, b, c, l; intsolve(int a, int b, int c){ int res = 0; for (int i = 0; i <= l; i++) { int u = min(c + i - a - b, l - i); if (u >= 0) res += (u + 1) * (u + 2) / 2; } return res; }
void _main() { cin >> a >> b >> c >> l; int res = 1; for (int i = 1; i <= l; i++) res += (i + 1) * (i + 2) / 2; res -= solve(a, b, c), res -= solve(a, c, b), res -= solve(b, c, a); cout << res; }
constint N = 2e6 + 5; mint fac[N], ifac[N]; mint C(int n, int m){ if (n < m) return0; //return fac[n] * ifac[m] * ifac[n - m]; mint res = 1; for (int i = n - m + 1; i <= n; i++) res *= i; return res * ifac[m]; } mint solve(int n, int l, int r){ if (n <= 0 || l > r) return1; returnC(r - l + n, n); }
int n, c, a[N], ls[N], rs[N], v[N]; voiddfs(int rt){ if (rt == -1) return; dfs(ls[rt]), a[++a[0]] = v[rt], dfs(rs[rt]); }
void _main() { cin >> n >> c; for (int i = 1; i <= n; i++) cin >> ls[i] >> rs[i] >> v[i]; a[0] = 0, dfs(1); mint res = 1; int l = 0; for (int i = 1; i <= n; i++) { if (a[i] == -1) continue; res *= solve(i - l - 1, l ? a[l] : 1, a[i]); l = i; } res *= solve(n - l, l ? a[l] : 1, c); cout << res << '\n'; }
constint N = 1e6 + 5; int n, k; mint fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];}
void _main() { fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; cin >> n >> k; mint res = 1; for (int i = 1; i <= n; i++) res += C(n - (i - 1) * k, i); cout << res; }
constint N = 3e5 + 5; mint fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];}
int n, q, opt, x, y, last; int fa[N], sz[N]; mint w[N]; intfind(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);} voidunite(int x, int y){ x = find(x), y = find(y); if (x == y) return; fa[x] = y, sz[y] += sz[x], w[y] *= w[x] * C(sz[y] - 1, sz[x]); }
void _main() { cin >> n >> q; fac[0] = ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; iota(fa + 1, fa + n + 1, 1), fill(sz + 1, sz + n + 1, 1), fill(w + 1, w + n + 1, 1); while (q--) { cin >> opt >> x; if (opt == 1) { cin >> y; x = (x + last) % n + 1, y = (y + last) % n + 1; unite(x, y); } else { x = (x + last) % n + 1; cout << (last = w[find(x)].val) << '\n'; } } }
constint N = 4e5 + 5; int n, a[N]; mint fac[N], ifac[N]; mint C(int n, int m){ if (n < m) return0; return fac[n] * ifac[m] * ifac[n - m]; }
void _main() { cin >> n; for (int i = 0; i <= n; i++) cin >> a[i]; fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; mint res = 0; for (int i = 0; i <= n; i++) res += C(i + a[i], i + 1); cout << res; }
*[模拟赛] 马戏表演
对于长为 n 的排列 a,设 ai 表示 pi 成为了多少个区间最大值。求有多少排列满足 ∀i∈[1,n],ci≤m。对给出的质数 p 取模。
n≤107,n≤m≤Cn+12,108≤p≤109。
好题。赛时场切之,喜提机房 rk1。
注意到合法的瓶颈是最大值。考虑从最大值的位置入手 DP。
设 f(n) 表示长为 n 的排列的答案。若 ⌈2n⌉×(⌊2n⌋+1)≤m,则所有排列都合法,f(n)=n!。
#define int long long constint N = 1e7 + 5; int c, n, m, p; mod32 f[N], fac[N], ifac[N], inv[N], g[N]; mod32 A(int n, int m){return fac[n] * ifac[n - m];}
void _main() { cin >> c >> n >> m >> p; mod32{}.set_mod(p); fac[0] = 1; for (int i = 1; i <= n + 1; i++) { fac[i] = fac[i - 1] * i; inv[i] = (i == 1 ? 1 : -inv[p % i] * (p / i)); } ifac[n + 1] = ~fac[n + 1]; for (int i = n; i >= 1; i--) ifac[i] = ifac[i + 1] * (i + 1); for (int i = 0; i <= n; i++) { if ((i / 2 + (i & 1)) * (i / 2 + 1) <= m) { f[i] = fac[i]; } else { int delta = (i + 1) * (i + 1) - 4 * m; int j = 1.0 * (i + 1 - sqrt(delta)) / 2; f[i] = (g[i - 1] - g[i - j - 1]) * inv[i] * fac[i] * 2; } g[i] = g[i - 1] + f[i] * ifac[i]; } cout << f[n]; }
constint N = 1e6 + 5; int tot = 0, head[N]; structEdge { int next, to; } edge[N << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } mint fac[N], ifac[N]; int n, k, u, l[N], r[N]; mint A(int n, int m){return n < m ? 0 : fac[n] * ifac[n - m];}
void _main() { cin >> n >> k; fac[0] = ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; for (int i = 2; i <= n; i++) cin >> u, add_edge(u, i); l[1] = 1, dfs(1); for (int i = 1; i <= r[1]; i++) sort(level[i].begin(), level[i].end()); mint res = 0; for (int i = 2; i <= n; i++) { int len = level[l[i]].size(); if (k >= len) continue; int x = lower_bound(level[l[i]].begin(), level[l[i]].end(), r[i]) - level[l[i]].begin(); int y = upper_bound(level[l[i]].begin(), level[l[i]].end(), r[i]) - level[l[i]].begin() - 1; int a = y - x, b = len - y - 1; if (a <= 0 || a + b < k) continue; res += A(a + b, k - 1); if (b > k - 1) res -= A(b, k - 1); } cout << res; }
constint N = 105; int n, m, h, v[N]; mint C[N][N], dp[N][35][35][16];
void _main() { for (int i = 0; i < N; i++) C[i][0] = 1, C[i][i] = 1; for (int i = 0; i < N; i++) { for (int j = 1; j < i; j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; } cin >> n >> m >> h; for (int i = 0; i <= m; i++) cin >> v[i]; dp[0][0][0][0] = 1; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { for (int k = 0; k <= h; k++) { for (int p = 0; p <= n / 2; p++) { for (int c = 0; c <= n - j; c++) dp[i + 1][j + c][k + (c + p) % 2][(c + p) >> 1] += dp[i][j][k][p] * C[n - j][c] * mint(v[i]).pow(c); } } } } mint res = 0; for (int k = 0; k <= h; k++) { for (int p = 0; p <= n / 2; p++) { if (k + popcount(p) <= h) res += dp[m + 1][n][k][p]; } } cout << res; }
10. 排列组合进阶
由于把这坨东西放到上面会导致目录阅读体验较差,所以把这些较难的内容单独开出来了。
10.1 排列进阶
*10.1.1 康托展开
康托展开解决的是求排列字典序的问题。先给出公式:
1+i=1∑nrki×(n−i)!
其中 rki 表示 [i,n] 中有多少个数小于 ai,即 ai 的后缀排名。理解一下这个公式,字典序就是比当前排列小的排列数目,贪心地枚举 i,使得第 i 位小于 ai,而后置位与字典序无关。那么我们就需要把 i 后面小于 ai 的数换到前面,且根据全排列的原理有 (n−i)! 种方案。
longlongpower(longlong a, longlong b, longlong p){ longlong res = 1; for (a %= p; b; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; } voidexgcd(longlong a, longlong b, longlong& x, longlong& y){ b == 0 ? (x = 1, y = 0) : (exgcd(b, a % b, y, x), y -= a / b * x); } longlonginverse(longlong x, longlong p){ longlong a, b; returnexgcd(x, p, a, b), (a % p + p) % p; } longlongcalc(longlong n, longlong x, longlong p){ if (n == 0) return1; longlong s = 1; for (longlong i = 1; i <= p; i++) { if (i % x) s = s * i % p; } s = power(s, n / p, p); for (longlong i = n / p * p + 1; i <= n; i++) { if (i % x) s = i % p * s % p; } return s * calc(n / x, x, p) % p; } longlongmultilucas(longlong m, longlong n, longlong x, longlong p){ int cnt = 0; for (longlong i = m; i; i /= x) cnt += i / x; for (longlong i = n; i; i /= x) cnt -= i / x; for (longlong i = m - n; i; i /= x) cnt -= i / x; returnpower(x, cnt, p) % p * calc(m, x, p) % p * inverse(calc(n, x, p), p) % p * inverse(calc(m - n, x, p), p) % p; } longlong x[20]; intcrt(int n, longlong* a, longlong* m){ longlong mod = 1, res = 0; for (int i = 1; i <= n; i++) mod *= m[i]; for (int i = 1; i <= n; i++) { x[i] = mod / m[i]; longlong x0 = -1, y0 = -1; exgcd(x[i], m[i], x0, y0); res += a[i] * x[i] * (x0 >= 0 ? x0 : x0 + m[i]); } return res % mod; } longlongexlucas(longlong m, longlong n, longlong p){ int len = 0; longlong p0[20], a0[20]; for (longlong i = 2; i * i <= p; i++) { if (p % i) continue; p0[++len] = 1; while (p % i == 0) p0[len] *= i, p /= i; a0[len] = multilucas(m, n, i, p0[len]); } if (p > 1) p0[++len] = p, a0[len] = multilucas(m, n, p, p); returncrt(len, a0, p0); }
int tr[N]; voidadd(int x, int c){for (; x <= n; x += (x & -x)) tr[x] += c;} intask(int x){ int res = 0; for (; x != 0; x -= (x & -x)) res += tr[x]; return res; }
mint fac[N];
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, add(i, 1); mint res = 1; // 初值为1 for (int i = 1; i <= n; i++) res += fac[n - i] * (ask(a[i]) - 1), add(a[i], -1); cout << res; }
constint N = 3e5 + 5; int n, m, a[N], pos[N], cnt[N], fa[N]; intfind(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
void _main() { memset(cnt, 0, sizeof(int) * (n + 1)); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i, cnt[(i - a[i] + n) % n]++; vector<int> res; for (int k = 0; k < n; k++) { if (cnt[k] < n - 2 * m) continue; iota(fa + 1, fa + n + 1, 1); int c = 0; for (int i = 1; i <= n; i++) { int x = pos[i], y = (i + k - 1) % n + 1; x = find(x), y = find(y); if (x != y) fa[x] = y, c++; } if (c <= m) res.emplace_back(k); } cout << res.size() << ' '; for (int i : res) cout << i << ' '; cout << '\n'; }
constint N = 2e5 + 5; int n, m, p[N], fa[N]; intfind(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);} vector<int> r[N], a, b;
void _main() { cin >> n >> m; iota(fa + 1, fa + n + m + 1, 1); for (int i = 1; i <= n + m; i++) { cin >> p[i]; fa[find(i)] = find(p[i]); } for (int i = 1; i <= n + m; i++) r[find(i)].emplace_back(i); int res = 0; for (int i = 1; i <= n + m; i++) { if (find(i) != i) continue; if (r[i].size() == 1) continue; // 自环 if (r[i].back() <= n) a.emplace_back(r[i].size()); // 红色环 elseif (r[i][0] > n) b.emplace_back(r[i].size()); // 白色环 else res += r[i].size() - 1; } sort(a.begin(), a.end(), greater<int>()), sort(b.begin(), b.end(), greater<int>()); int la = a.size(), lb = b.size(); for (int i = 0; i < min(la, lb); i++) res += a[i] + b[i]; for (int i = min(la, lb); i < max(la, lb); i++) res += (i < la ? a[i] : b[i]) + 1; cout << res; }
constint N = 1e5 + 5; int n, a[N], fa[N], cnt[N]; mint f[N], fac[N]; intfind(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);} mint T(int x, int y){return x == y ? x : x + y;}
voidinit(){ fac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i; f[1] = 1; for (int i = 2; i < 1000; i++) { for (int j = 1; j <= i / 2; j++) { f[i] += T(j, i - j) * f[j] * f[i - j] * fac[i - 2] / fac[j - 1] / fac[i - j - 1]; } } }
void _main() { cin >> n; iota(fa + 1, fa + n + 1, 1), fill(cnt + 1, cnt + n + 1, 0); for (int i = 1; i <= n; i++) cin >> a[i], fa[find(i)] = find(a[i]); for (int i = 1; i <= n; i++) cnt[find(i)]++; mint res = 1; int k = 0; for (int i = 1; i <= n; i++) { if (find(i) != i) continue; res *= f[cnt[i]] / fac[cnt[i] - 1], k++; } cout << res * fac[n - k] << '\n'; }
constint N = 2e5 + 5; int n, a[N], v[N]; mint f[N], fac[N], ifac[N]; mint C(int n, int m){ if (n < m) return0; return fac[n] * ifac[m] * ifac[n - m]; }
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> v[i]; fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; mint sum = 1, res = 0; for (int i = 1; i <= n; i++) f[i] = mint(2).pow(a[i]), sum *= f[i]; for (int i = 1; i <= n; i++) { mint cur = 0; res += (mint(v[i] + 1).pow(a[i]) - 1) * (sum / f[i]); } cout << res; }
longlong n, m, l, r; void _main() { cin >> n >> m >> l >> r; if (n * m % 2) return cout << mint(r - l + 1).pow(n * m), void(); longlong a = r / 2 - (l - 1) / 2, b = r - l + 1 - a; cout << (mint(a + b).pow(n * m) + mint(a - b).pow(n * m)) / 2; }
constint N = 2400, p = 2333; longlong q, n, k; mint c[N][N], pre[N][N];
mint lucas(longlong n, longlong m){ if (n < m) return0; if (n == m) return1; return c[n % p][m % p] * lucas(n / p, m / p); } mint f(longlong n, longlong k){ if (k < 0) return0; if (n == 0 || k == 0) return1; if (n < p && k < p) return pre[n][k]; returnf(n / p, k / p - 1) * pre[n % p][p - 1] + pre[n % p][k % p] * lucas(n / p, k / p); }
void _main() { for (int i = 0; i < N; i++) c[i][0] = 1, c[i][i] = 1; for (int i = 0; i < N; i++) { for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; } for (int i = 0; i < N; i++) { pre[i][0] = 1; for (int j = 1; j < N; j++) pre[i][j] = pre[i][j - 1] + c[i][j]; } for (cin >> q; q--; ) cin >> n >> k, cout << f(n, k) << '\n'; }
constint N = 4e5 + 5; longlong n, m, k; mint fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];} mint f(int x, int y){ if (x < 0 || y < 0) return0; returnC(x + y + 1, x) * (y + 1) - C(x + y + 1, x + 1) * 2; }
void _main() { cin >> n >> m >> k; if (k < n + m - 2) cout << 0 << '\n'; elseif (k == n + m - 2) cout << C(n + m - 2, m - 1) << '\n'; elseif (k == n + m - 1) { mint x = n * (m - 1) + m * (n - 1) - (n + m - 2); cout << x * C(n + m - 2, m - 1) << '\n'; } else { mint y = 2 * n * m - n - m - k + 1; cout << C(n + m - 2, m - 1) * y * (y + 1) / 2 - C(n + m - 4, n - 2) * (n + m - 3) + f(n, m - 3) + f(m, n - 3) << '\n'; } }
constint N = 2e5 + 5; int n, a[N], b[N]; char s[N]; mint fac[N], ifac[N]; mint C(int n, int m){ if (n < m) return0; return fac[n] * ifac[m] * ifac[n - m]; }
void _main() { cin >> (s + 1); n = strlen(s + 1); fac[0] = ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; for (int i = 1; i <= n; i++) a[i] = a[i - 1] + (s[i] == '('); for (int i = n; i >= 1; i--) b[i] = b[i + 1] + (s[i] == ')'); mint res = 0; for (int i = 1; i <= n; i++) { if (s[i] == '(') res += C(a[i] + b[i] - 1, a[i]); } cout << res; }
#define int long long constint N = 22; int n, m, a[N]; mint inv[N]; mint C(int n, int m){ if (m < 0 || n < 0 || n < m) return0; if (m == 0 || mint(n) == 0) return1; mint res = 1; for (int i = 0; i < m; i++) res *= n - i; for (int i = 1; i <= m; i++) res *= inv[i]; return res; }
void _main() { cin >> n >> m; for (int i = 1; i <= n; i++) inv[i] = ~mint(i); for (int i = 1; i <= n; i++) cin >> a[i]; mint res = C(n + m - 1, n - 1); for (int s = 1; s < (1 << n); s++) { int sum = n + m, k = 0; for (int i = 1; i <= n; i++) { if (s >> (i - 1) & 1) sum -= a[i], k++; } sum -= k + 1; if (k & 1) res -= C(sum, n - 1); else res += C(sum, n - 1); } cout << res; }
11. 二项式反演
11.1 原理
设 f(n) 表示恰好使用 n 个不同元素形成特定结构的方案数,g(n) 表示从这 n 个不同元素中选出若干个元素形成特定结构的方案数。
#define popcount __builtin_popcount constint N = 25; int n, m; longlong y, a[N], g[N], c[N][N];
void _main() { cin >> n >> m >> y; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0; i <= n; i++) c[i][0] = 1, c[i][i] = 1; for (int i = 0; i <= n; i++) { for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; } for (int s = 0; s < (1 << n); s++) { __int128 x = 1; for (int i = 1; i <= n; i++) { if (s >> (i - 1) & 1) x = x / __gcd<__int128>(x, a[i]) * a[i]; if (x > y) break; // 注意这句 } g[popcount(s)] += y / x; } longlong res = 0; for (int i = m; i <= n; i++) { if ((m - i) & 1) res -= c[i][m] * g[i]; else res += c[i][m] * g[i]; } cout << res; }
看到不好求的“恰好”,考虑二项式反演。设 f(i) 表示交集大小恰好为 i 的方案数,g(i) 表示钦定至少i 个元素属于交集的方案数。
那么对于 g(i),先从 n 个元素中选出 i 个,方案数 Cni。剩下 n−i 个元素可选可不选,就是求大小为 2n−i 的集合的非空子集数,答案为 22n−i−1,乘法原理:
g(i)=Cni(22n−i−1)
由二项式反演形式二得
f(k)=i=k∑n(−1)i−kCikg(i)
复杂度 O(nlogn)。注意求 g(i) 要用欧拉定理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
constint N = 1e6 + 5; mint fac[N], ifac[N], g[N]; mint C(int n, int m){ return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m]; } int n, k; void _main() { cin >> n >> k; fac[0] = ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; for (int i = 0; i <= n; i++) g[i] = C(n, i) * (mint(2).pow(mod32<1000000006>(2).pow(n - i).val) - 1); mint res = 0; for (int i = k; i <= n; i++) { if ((i - k) & 1) res -= C(i, k) * g[i]; else res += C(i, k) * g[i]; } cout << res; }
constint N = 5e4 + 5; int n, m; longlong g[5]; char a[N][5]; constint fac[] = {1, 1, 2, 6, 24}; intC(int n, int m){return n < m ? 0 : fac[n] / fac[m] / fac[n - m];}
void _main() { cin >> n >> m, m = 4 - m; for (int i = 1; i <= n; i++) cin >> (a[i] + 1); for (int s = 0; s < (1 << 4); s++) { umap<uint64_t, int> mp; for (int i = 1; i <= n; i++) { uint64_t h = 0; for (int j = 1; j <= 4; j++) { h *= 13331; if (s >> (j - 1) & 1) h += a[i][j]; } g[popcount(s)] += mp[h], mp[h]++; } } longlong res = 0; for (int k = m; k <= 4; k++) { if ((k - m) & 1) res -= C(k, m) * g[k]; else res += C(k, m) * g[k]; } cout << res; }
constint N = 2005; mint fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m]; } int n, m, a[N]; mint f(int x){ mint res = 1; for (int k = 1; k <= m; k++) res *= C(a[k] + n - x - 1, n - x - 1); return res; }
void _main() { fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; cin >> n >> m; for (int i = 1; i <= m; i++) cin >> a[i]; mint res = 0; for (int i = 0; i < n; i++) { if (i & 1) res -= C(n, i) * f(i); else res += C(n, i) * f(i); } cout << res; }
设 g(x) 表示钦定 x 位相同的方案数,f(x) 为钦定至少x 位相同的方案数,根据二项式反演形式二
g(x)=i=x∑n(−1)i−xCxif(i)
答案即为
g(0)=i=0∑n(−1)nf(i)
此时二项式反演退化为普通容斥原理。容易得到
f(x)=CnxAmx(An−xm−x)2
复杂度 O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
constint N = 5e5 + 5; int n, m; mint fac[N], ifac[N]; mint A(int n, int m){return n < m ? 0 : fac[n] * ifac[n - m];} mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];} mint f(int x){ returnC(n, x) * A(m, x) * A(m - x, n - x) * A(m - x, n - x); }
void _main() { cin >> n >> m; fac[0] = ifac[0] = 1; for (int i = 1; i <= max(n, m); i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; mint res = 0; for (int i = 0; i <= n; i++) { if (i & 1) res -= f(i); else res += f(i); } cout << res; }
设恰好 m 个 2023 出现的方案数为 f(m),钦定至少 m 个 2023 出现的方案数为 g(m),根据二项式反演形式二
f(m)=i=m∑⌊n/4⌋(−1)i−mCmig(i)
只需求出 g(i)。当钦定了 i 个 2023 时,数字串形如 ...2023...2023...,简单插板法得到
g(i)=10n−4iCn−3ii
做完了。复杂度 O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
constint N = 1e5 + 5; int n, m; mint g[N], fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];}
void _main() { cin >> n >> m; fac[0] = ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; for (int i = m; i <= n / 4; i++) g[i] = C(n - 3 * i, i) * mint(10).pow(n - 4 * i); mint res = 0; for (int i = m; i <= n / 4; i++) { if ((i - m) & 1) res -= C(i, m) * g[i]; else res += C(i, m) * g[i]; } cout << res; }
constint N = 2005; int n, m, k, a[N], b[N], last[N]; mint fac[N], ifac[N], dp[N][N], g[N]; mint C(int n, int m){ if (n < m) return0; return fac[n] * ifac[m] * ifac[n - m]; }
void _main() { cin >> n >> k; if ((n + k) & 1) return cout << 0, void(); fac[0] = ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i];
m = (n + k) / 2; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; sort(a + 1, a + n + 1), sort(b + 1, b + n + 1); for (int i = 1; i <= n; i++) last[i] = lower_bound(b + 1, b + n + 1, a[i]) - b - 1; dp[0][0] = 1; for (int i = 1; i <= n; i++) { dp[i][0] = dp[i - 1][0]; for (int j = 1; j <= i; j++) { dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * max(0, last[i] - j + 1); } } for (int i = 0; i <= n; i++) g[i] = dp[n][i] * fac[n - i]; mint res = 0; for (int i = m; i <= n; i++) { if ((i - m) & 1) res -= C(i, m) * g[i]; else res += C(i, m) * g[i]; } cout << res; }
constint N = 5005; int n, m, u, v, belong[N]; char c; int tot = 0, head[N]; structEdge { int next, to; } edge[N << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } mint f[N], g[N], fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];}
int sz[N], cnt[2][N]; mint dp[N][N]; voiddfs(int u, int fa){ sz[u] = 1, cnt[belong[u]][u] = 1, dp[u][0] = 1; for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; if (v == fa) continue; dfs(v, u); vector<mint> f(min(sz[u] + sz[v], m), 0); for (int j = 0; j <= min(sz[u], m); j++) { for (int k = 0; k <= min(sz[v], m - j); k++) { f[j + k] += dp[u][j] * dp[v][k]; } } sz[u] += sz[v], cnt[0][u] += cnt[0][v], cnt[1][u] += cnt[1][v]; copy(f.begin(), f.end(), dp[u]); } for (int i = cnt[belong[u] ^ 1][u]; i >= 0; i--) { dp[u][i + 1] += dp[u][i] * (cnt[belong[u] ^ 1][u] - i); } }
void _main() { fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; cin >> n, m = n / 2; for (int i = 1; i <= n; i++) cin >> c, belong[i] = c ^ 48; for (int i = 1; i < n; i++) { cin >> u >> v; add_edge(u, v), add_edge(v, u); } dfs(1, -1); for (int i = 0; i <= m; i++) g[i] = dp[1][i] * fac[m - i]; for (int i = 0; i <= m; i++) { for (int j = i; j <= m; j++) { if ((j - i) & 1) f[i] -= C(j, i) * g[j]; else f[i] += C(j, i) * g[j]; } cout << f[i] << '\n'; } }
constint N = 105; int n, m, k, u[N], r[N]; mint h[N], fac[N], ifac[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];} mint g(int k){ mint res = C(n - 1, k); for (int i = 1; i <= m; i++) res *= C(n - k - 1, r[i] - 1) * h[i]; return res; } namespace Lagrange { mint a[N], p[N], s[N]; mint solve(int n, int k){ p[0] = 1, s[k + 3] = 1; for (int i = 1; i <= k + 2; i++) a[i] = a[i - 1] + mint(i).pow(k), p[i] = p[i - 1] * (n - i); for (int i = k + 2; i >= 1; i--) s[i] = s[i + 1] * (n - i); if (n <= k + 2) return a[n]; mint res = 0; for (int i = 1; i <= k + 2; i++) { mint cur = a[i] * p[i - 1] * s[i + 1] * ifac[i - 1] * ifac[k + 2 - i]; if ((k + 2 - i) & 1) res -= cur; else res += cur; } return res; } } using Lagrange::solve;
void _main() { fac[0] = ifac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; cin >> n >> m >> k; for (int i = 1; i <= m; i++) cin >> u[i]; for (int i = 1; i <= m; i++) cin >> r[i]; for (int i = 1; i <= m; i++) { for (int k = 0; k < r[i]; k++) { mint cur = C(r[i] - 1, k) * mint(u[i]).pow(k) * solve(u[i], n - k - 1); if ((r[i] - k - 1) & 1) h[i] -= cur; else h[i] += cur; } } mint res = 0; for (int i = k; i <= n; i++) { if ((i - k) & 1) res -= C(i, k) * g(i); else res += C(i, k) * g(i); } cout << res; }
12. 错位排列
错排数Di 是指将 1 到 n 的自然数排列重新排列为 Pi 后,满足 ∀i∈[1,n],Pi=i 的方案数。
constint N = 1005; int q, n; mint fac[N], ifac[N], f[N]; mint A(int n, int m){ if (n < m) return0; return fac[n] * ifac[n - m]; } mint C(int n, int m){ if (n < m) return0; return fac[n] * ifac[m] * ifac[n - m]; }
void _main() { fac[0] = ifac[0] = 1, f[0] = 1, f[1] = 0; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; for (int i = 2; i < N; i++) f[i] = (f[i - 1] + f[i - 2] * 2 * (i - 1)) * 2 * i * (2 * i - 2); for (cin >> q; q--; ) { cin >> n; for (int k = 0; k <= n; k++) cout << C(n, k) * A(n, k) * mint(2).pow(k) * f[n - k] << '\n'; } }
13. Catalan 数
Catalan 数的起源是凸多边形三角剖分问题,即对于一个凸 n 边形,有多少种方式可以用不相交的对角线将其划分为若干个三角形。这里将方案数记作 Hn。Catalan 数列为: 1,1,2,5,14,42,132,429,1430,4862⋯,参见 A000108。
constint N = 2e6 + 5; int n, ls[N], rs[N], sz[N]; mint h[N];
voiddfs1(int u){ if (!u) return; dfs1(ls[u]), dfs1(rs[u]), sz[u] = sz[ls[u]] + sz[rs[u]] + 1; } mint dfs2(int u, mint x){ if (!u) return0; mint res = 0; for (int i = 0; i < sz[ls[u]]; i++) res += x * h[i] * h[sz[u] - i - 1]; res += dfs2(ls[u], x * h[sz[rs[u]]]); res += dfs2(rs[u], x); return res; }
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> ls[i] >> rs[i]; h[0] = 1; for (int i = 1; i <= (n << 1); i++) h[i] = h[i - 1] * (4 * i - 2) / (i + 1); mint res = 0; for (int i = 1; i < n; i++) res += h[i]; dfs1(1), res += dfs2(1, 1); cout << res; }
mint dfs2(int u, mint x){ if (!u) return0; mint res = 0; if (sz[ls[u]] <= sz[rs[u]]) { for (int i = 0; i < sz[ls[u]]; i++) res += x * h[i] * h[sz[u] - i - 1]; } else { res += x * h[sz[u]]; for (int i = 0; i <= sz[rs[u]]; i++) res -= x * h[i] * h[sz[u] - i - 1]; } res += dfs2(ls[u], x * h[sz[rs[u]]]); res += dfs2(rs[u], x); return res; }
14. Stirling 数
14.1 第二类 Stirling 数
第二类 Stirling 数S(n,k) 表示将 n 个不同元素分为 k 个互不区分的非空子集的方案数。
因为 lcmi=1k=gcdi=1kai∏i=1kai,所以 gcdi=1kai=1,而且又说了 a 单调不降,就是说 a 序列两两互质。对 n 分解质因数得 n=p1a1p2a2⋯,发现若 ax=0,则这些 px 只能被分配到同一个 ai 中。记有 c 个不同质因子,然后你发现这是把 c 个元素划成 k 个子集的方案数,即第二类 Stirling 数。
int n, k; intdecompose(int n){ int m = 0; for (int i = 2; i * i <= n; i++) { if (n % i) continue; m++; while (n % i == 0) n /= i; } if (n > 1) m++; return m; }
longlong s[15][15];
void _main() { cin >> n >> k; int m = decompose(n); cout << (m < k ? 0 : s[m][k]) << '\n'; } signedmain(){ s[0][0] = 1; for (int i = 1; i < 15; i++) { for (int j = 1; j <= i; j++) s[i][j] = s[i - 1][j - 1] + s[i - 1][j] * j; int t = 1; for (cin >> t; t--; ) _main(); }
constint N = 1e6 + 5; int n, k; mint fac[N], ifac[N]; mint S(int n, int k){ mint res = 0; for (int i = 0; i <= k; i++) { if ((k - i) & 1) res -= mint(i).pow(n) * ifac[i] * ifac[k - i]; else res += mint(i).pow(n) * ifac[i] * ifac[k - i]; } return res; }
void _main() { cin >> n >> k; fac[0] = ifac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; cout << S(n, n - k); }
#define int long long constint N = 105; int n, m, a[N][20][20], x[N], id[N], f[N], fac[N]; char s[N * N];
intguass(int tot){ int cnt = m; for (int i = 1, cur = 1; i <= tot && cur <= m; cur++) { for (int j = i; j <= tot; j++) { if (x[j] >> cur & 1) {swap(x[i], x[j]); break;} } if (!(x[i] >> cur & 1)) continue; for (int j = i + 1; j <= tot; j++) { if (x[j] >> cur & 1) x[j] ^= x[i]; } cnt--, i++; } return cnt; } voiddfs(int step){ if (step > n) { int tot = 0; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (id[i] == id[j]) continue; x[++tot] = 0; for (int k = 1; k <= m; k++) { if (a[k][i][j]) x[tot] |= 1LL << k; } } } return f[id[0]] += 1LL << guass(tot), void(); } id[step] = ++id[0], dfs(step + 1), id[0]--; for (int i = 1; i <= id[0]; i++) id[step] = i, dfs(step + 1); }
void _main() { cin >> m; for (int i = 1; i <= m; i++) { cin >> (s + 1); int len = strlen(s + 1), tot = 0; for (int j = 1; ; j++) { if (j * (j - 1) / 2 == len) {n = j; break;} } for (int j = 1; j <= n; j++) { for (int k = j + 1; k <= n; k++) a[i][j][k] = s[++tot] ^ 48; } } dfs(1); fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i; int res = 0; for (int i = 1; i <= n; i++) { if (i & 1) res += fac[i - 1] * f[i]; else res -= fac[i - 1] * f[i]; } cout << res; }
constint N = 1005; int n, x, p, m, a[N], b[N], s[N][N], low[N]; intmadd(int x, int y){return x += y, x >= p ? x -= p : x;} intmpow(int a, int b){ int res = 1; for (a %= p; b; a = 1LL * a * a % p, b >>= 1) { if (b & 1) res = 1LL * res * a % p; } return res; }
void _main() { cin >> n >> x >> p >> m; for (int i = 0; i <= m; i++) cin >> a[i]; s[0][0] = 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= i; j++) s[i][j] = madd(s[i - 1][j - 1], 1LL * j * s[i - 1][j] % p); } // 第二类 Stirling 数 for (int i = 0; i <= m; i++) { for (int j = i; j <= m; j++) b[i] = madd(b[i], 1LL * a[j] * s[j][i] % p); } // 下降幂系数 for (int i = 0; i <= m; i++) { low[i] = 1; for (int j = 0; j < i; j++) low[i] = 1LL * low[i] * (n - j) % p; } // n 的下降幂 int res = 0; for (int i = 0; i <= m; i++) res = madd(res, 1LL * b[i] * mpow(x, i) % p * low[i] % p * mpow(x + 1, n - i) % p); cout << res; }
constint N = 1005; longlong n, m, a[N]; char s[N]; mint b[N][N];
void _main() { cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> (s + 1); for (int j = 1; j <= m; j++) { if (s[j] == '1') a[j] |= 1LL << (i - 1); } } map<longlong, int> sz; for (int i = 1; i <= m; i++) sz[a[i]]++;
b[0][0] = 1; for (int i = 1; i <= m; i++) { b[i][0] = b[i - 1][i - 1]; for (int j = 1; j <= i; j++) b[i][j] = b[i - 1][j - 1] + b[i][j - 1]; } mint res = 1; for (constauto& k : sz) res *= b[k.second][0]; cout << res; }
constint N = 1e5 + 5, M = 405; int n, m, dp[N], p[M][N];
void _main() { cin >> n >> m; int b = sqrt(n) + 1; dp[0] = 1, p[0][0] = 1; for (int i = 1; i < b; i++) { for (int j = i; j <= n; j++) (dp[j] += dp[j - i]) %= m; } for (int i = 1; i < b; i++) { for (int j = i; j <= n; j++) { p[i][j] = p[i][j - i]; if (j >= b) (p[i][j] += p[i - 1][j - b]) %= m; } } int res = 0; for (int j = 0; j <= n; j++) { int cur = 0; for (int k = 0; k < b; k++) (cur += p[k][n - j]) %= m; (res += 1LL * dp[j] * cur % m) %= m; } cout << res; }
constint N = 20; int n, m, u, v, g[N][N]; longlong f[N][1 << N];
void _main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u >> v; g[u][v] = g[v][u] = 1; } for (int i = 1; i <= n; i++) f[i][1 << (i - 1)] = 1; longlong res = 0; for (int s = 1; s < (1 << n); s++) { for (int u = 1; u <= n; u++) { if (!(s >> (u - 1) & 1)) continue; for (int v = 1; v <= n; v++) { if (!g[u][v]) continue; if ((s & -s) > (1 << (v - 1))) continue; if (s >> (v - 1) & 1) { if ((s & -s) == (1 << (v - 1))) res += f[u][s]; } else { f[v][s | (1 << (v - 1))] += f[u][s]; } } } } cout << (res - m) / 2; }
constint N = 1e5 + 5; int n, m, deg[N], tag[N]; pair<int, int> e[N << 1]; vector<int> g[N];
void _main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> e[i], deg[e[i].first]++, deg[e[i].second]++; auto f = [&](int x, int y) -> bool {return deg[x] == deg[y] ? x < y : deg[x] < deg[y];}; for (int i = 1; i <= m; i++) { if (f(e[i].first, e[i].second)) g[e[i].first].emplace_back(e[i].second); else g[e[i].second].emplace_back(e[i].first); } int res = 0; for (int u = 1; u <= n; u++){ for (int v : g[u]) tag[v] = u; for (int v : g[u]) { for (int w : g[v]) res += tag[w] == u; } } cout << res; }
考虑枚举 1 号点所在的边双连通分量的大小 k。从 i−1 个节点中选出 k 个构成边双,方案数是 fk,0×Ci−1k−1 乘上其他部分的贡献。
设 gi,j,k 表示点数为 i,割边数为 j,有 k 个连通块的无向图数目。则对于 fi,j,去掉边双以后剩下 gi−k,j−x,x 的贡献,其中 x 是枚举的量,表示剩下的图中被分成了 x 个连通块。每个连通块与边双形成 x 条割边,所以还需要凑出 j−x 条割边。由于这个边双有 k 个点,每个节点都有 k 种选择,贡献还要乘上 kx。因此
constint N = 55; int n, m; mint fac[N], ifac[N], f[N][N], g[N][N][N], h[N]; mint C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];} mint G(int i, int j, int k){ if (k > i || (i != 0 && k == 0)) return g[i][j][k] = 0; if (g[i][j][k] != -1) return g[i][j][k]; g[i][j][k] = 0; for (int p = 1; p <= i; p++) { for (int q = 0; q <= j; q++) { g[i][j][k] += f[p][q] * C(i - 1, p - 1) * p * G(i - p, j - q, k - 1); } } return g[i][j][k]; }
void _main() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) fill(g[i][j], g[i][j] + N, -1); } cin >> n >> m; m = min(n, m); fac[0] = ifac[0] = 1, h[1] = 1, f[0][0] = 1, g[0][0][0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i]; for (int i = 2; i <= n; i++) { h[i] = mint(2).pow(C(i, 2).val); for (int j = 1; j < i; j++) h[i] -= C(i - 1, j - 1) * h[j] * mint(2).pow(C(i - j, 2).val); } for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { for (int k = 1; k < i; k++) { mint sum = 0; for (int x = 1; x <= min(i - k, j); x++) sum += G(i - k, j - x, x) * mint(k).pow(x); f[i][j] += f[k][0] * C(i - 1, k - 1) * sum; } } f[i][0] = h[i]; for (int j = 1; j < i; j++) f[i][0] -= f[i][j]; } mint res = 0; for (int i = 0; i <= m; i++) res += f[n][i]; cout << res; }
[模拟赛] 竞赛图
给你一个 n 个点的竞赛图,求有多少个点的子集 S 满足 S 的诱导子图是强连通的。答案包括空集。
竞赛图是一个有向图,满足任意两个不同的点之间均存在且仅存在一条有向边相连。
一个图在点集 S 的诱导子图的定义为:点集为 S,边集为所有两端的点都在 S 中的边的子图。
多测,n≤24,T≤10。
暴力 Tarjan 可以做到单次 O(n22n),和我一样没有前途。
根据竞赛图的性质,将一个强连通分量 S 提出来后,S 的补集与 S 只存在内向边。
直接想状压。考虑类似刷表的做法,用强连通子集 S 去转移其他自己,设出边集合的交集为 E,对于每个 T⊆E,S∪B 中来自 B 的部分一定不强联通,将其标记即可。类似筛法,未被标记的都是强连通子集。
int n, m, u, v, a[N][N]; int tot = 0, head[N]; structEdge { int next, to; } edge[N << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } uint64_t dp[N][N]; voiddfs(int u, int fa, int s){ for (int i = 1; i <= n; i++) { if (s >> (i - 1) & 1) dp[u][i] = 1; } for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; if (v == fa) continue; dfs(v, u, s); for (int x = 1; x <= n; x++) { if (!(s >> (x - 1) & 1)) continue; uint64_t cur = 0; for (int y = 1; y <= n; y++) { if (!(s >> (y - 1) & 1)) continue; if (a[x][y]) cur += dp[v][y]; } dp[u][x] *= cur; } } }
void _main() { cin >> n >> m; if (n == 1) return cout << 1, void(); for (int i = 1; i <= m; i++) cin >> u >> v, a[u][v] = a[v][u] = 1; for (int i = 1; i < n; i++) cin >> u >> v, add_edge(u, v), add_edge(v, u); uint64_t res = 0; for (int s = 0; s < (1 << n); s++) { dfs(1, -1, s); uint64_t cur = 0; for (int i = 1; i <= n; i++) { if (s >> (i - 1) & 1) cur += dp[1][i]; } res += ((n - popcount(s)) & 1) ? -cur : cur; } cout << res; }
这题有两种做法。我们先来说比较简单的概率 DP,就是设 dpi,j 表示已经售出了 i 张 A 类票,j 张 B 类票的概率。根据概率的加法原理
dpi,j=2dpi−1,j+dpi,j−1
边界是 dpi,0=dp0,1=1.0。复杂度 O(n2)。
1 2 3 4 5 6 7 8 9 10 11
constint N = 1300; int n; double dp[N][N];
inlinevoid _main() { cin >> n; n >>= 1; for (int i = 2; i <= n; i++) dp[0][i] = dp[i][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) / 2; } cout << fixed << setprecision(4) << dp[n][n]; }
第二种做法是数学推导,设事件 A 为最后两张不同,则前 2n−2 张中有 n−1 张 A,n−1 张 B,根据概率的乘法原理得
P(A)=22n−2C2n−2n−1
一边循环一边求值即可,复杂度 O(n)。
1 2 3 4 5 6 7
int n; void _main() { cin >> n; n >>= 1; double res = 1.0; for (int i = 1; i < n; i++) res *= 1.0 * (i + n - 1) / (i * 4); cout << fixed << setprecision(4) << 1.0 - res; }
void _main() { cin >> n >> A >> B >> C >> a[1]; if (n == 1) return cout << "1.000", void(); for (int i = 2; i <= n; i++) a[i] = (1LL * a[i - 1] * A + B) % 100000001; for (int i = 1; i <= n; i++) a[i] = a[i] % C + 1; double res = 0.0; a[n + 1] = a[1]; for (int i = 1; i <= n; i++) res += 1.0 / max(a[i], a[i + 1]); cout << fixed << setprecision(3) << res; }
*[模拟赛] 概率
有一个长为 2n 的非负整数序列,每个数字在 [0,m] 中随机均匀分布。求前 n 个数的和 s1 大于后 n 个数的和 s2 的概率。对给出的质数 p 取模。
constint N = 2005, M = 5e6; int p, q, n, m; mod32 fac[M + 5], ifac[M + 5]; mod32 C(int n, int m){return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];}
voidask(){ mod32 tot = mod32(m + 1).pow(2 * n), res = 0; for (int i = 0; i <= 2 * n; i++) { int j = n * m - i * (m + 1); if (j < 0) break; if (i & 1) res -= C(2 * n, i) * C(2 * n + j - 1, j); else res += C(2 * n, i) * C(2 * n + j - 1, j); } cout << (tot - res) / 2 / tot << '\n'; }
void _main() { cin >> p >> q, mod32{}.set_mod(p); fac[0] = 1; for (int i = 1; i <= M; i++) fac[i] = fac[i - 1] * i; ifac[M] = ~fac[M]; for (int i = M - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1); while (q--) cin >> n >> m, ask(); }
constint N = 2005; int n, m, v, e, x, y, w, s[N], t[N], dis[305][305]; double k[N], dp[2][N][N]; voidfloyd(){ for (int k = 1; k <= v; k++) { for (int i = 1; i <= v; i++) { for (int j = 1; j <= v; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } }
void _main() { cin >> n >> m >> v >> e; for (int i = 1; i <= n; i++) cin >> s[i]; for (int i = 1; i <= n; i++) cin >> t[i]; for (int i = 1; i <= n; i++) cin >> k[i]; memset(dis, 0x3f, sizeof(dis)); for (int i = 1; i <= v; i++) dis[i][i] = 0; for (int i = 1; i <= e; i++) { cin >> x >> y >> w; dis[x][y] = dis[y][x] = min(dis[x][y], w); } floyd(); for (int i = 0; i <= n; i++) fill(dp[0][i], dp[0][i] + n + 1, 1e18), fill(dp[1][i], dp[1][i] + n + 1, 1e18); dp[0][1][0] = dp[0][1][1] = dp[1][1][1] = 0; for (int i = 2; i <= n; i++) { for (int j = 0; j <= min(i, m); j++) { dp[0][i][j] = min( dp[0][i - 1][j] + dis[s[i - 1]][s[i]], dp[1][i - 1][j] + dis[s[i - 1]][s[i]] * (1 - k[i - 1]) + dis[t[i - 1]][s[i]] * k[i - 1] ); if (j > 0) dp[1][i][j] = min( dp[0][i - 1][j - 1] + dis[s[i - 1]][s[i]] * (1 - k[i]) + dis[s[i - 1]][t[i]] * k[i], dp[1][i - 1][j - 1] + dis[s[i - 1]][s[i]] * (1 - k[i - 1]) * (1 - k[i]) + dis[s[i - 1]][t[i]] * (1 - k[i - 1]) * k[i] + dis[t[i - 1]][s[i]] * k[i - 1] * (1 - k[i]) + dis[t[i - 1]][t[i]] * k[i - 1] * k[i] ); } } double res = 1e18; for (int j = 0; j <= min(n, m); j++) res = min({res, dp[0][n][j], dp[1][n][j]}); cout << fixed << setprecision(2) << res; }
constint N = 1e5 + 5; int n, m, a[N], c, d; mint v; unordered_map<int, int> mp;
void _main() { mp.clear(), memset(a, 0, sizeof(int) * (m + 1)); cin >> n >> m >> v; bool flag = true; for (int i = 1; i <= m; i++) { cin >> c >> d; if (mp.count(c)) { if (mp[c] != d) flag = false; } else { a[++a[0]] = c, mp[c] = d; } } if (!flag) return cout << 0 << '\n', void(); sort(a + 1, a + a[0] + 1); mint res = v.pow(2 * (n - 1)); for (int i = 2; i <= a[0]; i++) { int l = a[i - 1], r = a[i]; res *= mint(1) - (v - 1) / v.pow(r - l + 1); } cout << res << '\n'; }
constint N = 3005; int n, m, a[N], x[N], y[N]; mint dp[N][N];
void _main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) cin >> x[i] >> y[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (a[i] > a[j]) dp[i][j] = 1; } } for (int k = 1; k <= m; k++) { for (int i = 1; i <= n; i++) { if (i == x[k] || i == y[k]) continue; dp[x[k]][i] = dp[y[k]][i] = (dp[x[k]][i] + dp[y[k]][i]) / 2; dp[i][x[k]] = dp[i][y[k]] = (dp[i][x[k]] + dp[i][y[k]]) / 2; } dp[x[k]][y[k]] = dp[y[k]][x[k]] = (dp[x[k]][y[k]] + dp[y[k]][x[k]]) / 2; } mint res = 0; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) res += dp[i][j]; } cout << res * mint(2).pow(m); }
constint N = 5e5 + 5; int n, a[N]; longlongsolve(longlong x){ longlong res = 0; for (int i = 1, j = n; i <= n; i++) { while (a[i] + a[j] >= x && j >= 1) j--; res += n - max(i, j + 1) + 1; } return res; }
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); int res = 0; for (int i = 30; i >= 0; i--) { vector<int> x, y; for (int j = 1; j <= n; j++) { if (a[j] >> (i + 1) & 1) x.emplace_back(a[j] ^ (1 << (i + 1))); else y.emplace_back(a[j]); } merge(x.begin(), x.end(), y.begin(), y.end(), a + 1); longlong v = solve(1LL << i) - solve(2LL * (1 << i)) + solve(3LL * (1 << i)); if (v & 1) res |= 1 << i; } cout << res; }
constint N = 1005; int n, a[N][N], b[N][N], top, st[N]; mint calc(int d, int type){ for (int i = 1; i <= n; i++) b[1][i] = (a[1][i] >> d & 1) ^ type ^ 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= n; j++) { int x = (a[i][j] >> d & 1) ^ type; b[i][j] = x ? 0 : b[i - 1][j] + 1; } } mint res = 0, cur = 0; for (int i = 1; i <= n; i++) { cur = 0, top = 0; for (int j = 1; j <= n; j++) { for (; top && b[i][st[top]] >= b[i][j]; top--) cur -= 1LL * b[i][st[top]] * (st[top] - st[top - 1]); cur += 1LL * b[i][j] * (j - st[top]), res += cur; st[++top] = j; } } return res; }
void _main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cin >> a[i][j]; } mint x = 0, y = 0, tot = mint(n) * n * (n + 1) * (n + 1) / 4; for (int i = 0; i < 31; i++) { x += mint(2).pow(i) * calc(i, 1); y += mint(2).pow(i) * (tot - calc(i, 0)); } cout << x << ' ' << y; }
constint N = 2e5 + 5, M = 31; int n, a[N]; mint f[N], g[2][2][M][M];
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], a[i] ^= a[i - 1]; fill(f, f + n + 1, 0), memset(g, 0, sizeof(g)), f[0] = 1; for (int i = 0; i < M; i++) { for (int j = 0; j < M; j++) g[0][0][i][j] = 1; } for (int i = 1; i <= n; i++) { for (int x = 0; x < M; x++) { for (int y = 0; y < M; y++) f[i] += g[(a[i] >> x & 1) ^ 1][(a[i] >> y & 1) ^ 1][x][y] * (1LL << (x + y)); } for (int x = 0; x < M; x++) { for (int y = 0; y < M; y++) g[a[i] >> x & 1][a[i] >> y & 1][x][y] += f[i]; } } cout << f[n] << '\n'; }
void _main() { for (int b = 1; b <= N / 2; b++) { for (int a = b * 2; a < N; a += b) { if ((a ^ b) == a - b) res[a]++; } } for (int i = 2; i < N; i++) res[i] += res[i - 1]; int t; cin >> t; for (int i = 1; i <= t; i++) cin >> n, cout << "Case " << i << ": " << res[n] << '\n'; }
constint N = 2e6 + 5; int n, a[N]; int cnt = 1, ch[2][N];
voidinsert(int x){ int cur = 1; for (int i = 31; i >= 0; i--) { int p = x >> i & 1; if (!ch[p][cur]) ch[p][cur] = ++cnt; cur = ch[p][cur]; } } intquery(int x){ int cur = 1, res = 0; for (int i = 31; i >= 0; i--) { int p = x >> i & 1; if (!ch[p ^ 1][cur]) cur = ch[p][cur]; else cur = ch[p ^ 1][cur], res += (1 << i); } return res; }
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], insert(a[i]); int res = 0; for (int i = 1; i <= n; i++) res = max(res, query(a[i])); cout << res; }
constint N = 1e5 + 5; constexpr int128 pw(int x){returnint128(1) << x;} const int128 inf = pw(120) + 5; int n, m, k, b[N]; int128 a[N];
structtrie { int tot, num[2][N * 120]; int128 sum[N * 120], mn[N * 120]; trie() : tot(1) {} voidclear(){ for (int i = 0; i <= tot; i++) num[0][i] = num[1][i] = 0, sum[i] = 0, mn[i] = inf; tot = 1, sum[1] = 0, mn[1] = inf; } voidinsert(int128 x, int cost){ int rt = 1; mn[rt] = min(mn[rt], x), sum[rt] += cost; for (int i = k - 1; i >= 0; i--) { int c = x >> i & 1; if (!num[c][rt]) num[c][rt] = ++tot, mn[tot] = inf, sum[tot] = 0; rt = num[c][rt], mn[rt] = min(mn[rt], x), sum[rt] += cost; } } #define ls (num[0][rt]) #define rs (num[1][rt]) booldfs(int rt, int dep, int128 cmn, int128 csum, int128 mid, int128 cur){ if (csum > m) returnfalse; if (dep < 0 || !rt) { if (dep >= 0) cur += pw(dep + 1) - 1; return mid <= cur + cmn; } if (mid >> dep & 1) { returndfs(rs, dep - 1, min(cmn, mn[ls]), csum + sum[ls], mid, cur) || dfs(ls, dep - 1, min(cmn, mn[rs]), csum + sum[rs], mid, cur ^ pw(dep)); } else { returndfs(ls, dep - 1, cmn, csum, mid, cur) || dfs(rs, dep - 1, cmn, csum, mid, cur ^ pw(dep)); } } } tr; boolcheck(int128 x){return tr.dfs(1, k - 1, inf, 0, x, 0);}
void _main() { read(n, m, k), read(a + 1, a + n + 1), read(b + 1, b + n + 1); int128 sum = 0; for (int i = 1; i <= n; i++) sum += b[i]; if (sum <= m) returnwriteln(*min_element(a + 1, a + n + 1) + pw(k) - 1), void(); tr.clear(); for (int i = 1; i <= n; i++) tr.insert(a[i], b[i]); int128 l = 0, r = pw(k) - 1, res = 0; while (l <= r) { int128 mid = (l + r) >> 1; if (check(mid)) l = mid + 1, res = mid; else r = mid - 1; } writeln(res); }
constint N = 1e5 + 5, B = 1e4; int n, k, a[3][N], p[3][N], ans[N]; bitset<N> b[B], s; // 119MB
void _main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[0][i] >> a[1][i] >> a[2][i]; for (int i = 0; i < 3; i++) { iota(p[i] + 1, p[i] + n + 1, 1); sort(p[i] + 1, p[i] + n + 1, [&](int x, int y) -> bool { return a[i][x] < a[i][y]; }); } for (int l = 1, r; l <= n; l = r + 1) { r = min(n, l + B - 1); for (int i = l; i <= r; i++) b[i - l].set(); for (int i = 0; i < 3; i++) { s.reset(); for (int j = 1, k = 1; j <= n; j++) { int x = p[i][j]; while (k <= n && a[i][p[i][k]] <= a[i][x]) s[p[i][k++]] = 1; if (l <= x && x <= r) b[x - l] &= s; } } for (int i = l; i <= r; i++) ans[b[i - l].count()]++; } for (int i = 1; i <= n; i++) cout << ans[i] << '\n'; }
constint N = 3e4 + 5; int n, m, deg[N]; int tot = 0, head[N]; structEdge { int next, to; } edge[N << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } bitset<N> f[N]; queue<int> q; voidtopo(){ for (int i = 1; i <= n; i++) f[i][i] = 1; for (int i = 1; i <= n; i++) { if (!deg[i]) q.emplace(i); } while (!q.empty()) { int u = q.front(); q.pop(); for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; f[v] |= f[u]; if (!--deg[v]) q.emplace(v); } } }
void _main() { cin >> n >> m; for (int i = 1, u, v; i <= m; i++) cin >> u >> v, add_edge(v, u), deg[u]++; topo(); for (int i = 1; i <= n; i++) cout << f[i].count() << '\n'; }
int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19}; int n, p; structnode { int v, p, s; node() : v(0), p(-1), s(0) {} voidget(){ int x = v; for (int i = 1; i <= 8; i++) { if (x % prime[i]) continue; s |= 1 << (i - 1); while (x % prime[i] == 0) x /= prime[i]; } if (x != 1) p = x; } } a[N]; int dp[N][N], f[N][N], g[N][N];
void _main() { cin >> n >> p; for (int i = 2; i <= n; i++) a[i].v = i, a[i].get(); sort(a + 2, a + n + 1, [](const node& x, const node& y) -> bool { return x.p < y.p; }); dp[0][0] = 1; for (int i = 2; i <= n; i++) { if (i == 2 || a[i].p != a[i - 1].p || a[i].p == -1) { // 新连续段 memcpy(f, dp, sizeof(f)), memcpy(g, dp, sizeof(g)); } #define add(x, y) ((x) += (y), (x) >= p ? (x) -= p : (x)) #define madd(x, y) ((x) + (y) >= p ? (x) + (y) - p : (x) + (y)) #define msub(x, y) ((x) - (y) < 0 ? (x) - (y) + p : (x) - (y)) for (int s = M - 1; s >= 0; s--) { for (int t = M - 1; t >= 0; t--) { if (s & t) continue; if ((a[i].s & t) == 0) add(f[a[i].s | s][t], f[s][t]); if ((a[i].s & s) == 0) add(g[s][a[i].s | t], g[s][t]); } } if (i == n || a[i].p != a[i + 1].p || a[i].p == -1) { // 下一个点是新连续段 for (int s = 0; s < M; s++) { for (int t = 0; t < M; t++) { if (s & t) continue; dp[s][t] = msub(madd(f[s][t], g[s][t]), dp[s][t]); } } } } int res = 0; for (int s = 0; s < M; s++) { for (int t = 0; t < M; t++) { if (s & t) continue; add(res, dp[s][t]); } } cout << res; }
void _main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int k = 1; k <= m; k++) { int res = a[n], s = (k - 1) ^ ((1 << 20) - 1); for (int t = s; t; t = (t - 1) & s) { if (t < n) res ^= a[n - t]; } cout << res << ' '; } }
constint N = 1e5 + 5, M = 1 << 15; int n, u, v, w, a[N], xorv[M + 5], cnt[20], dp[M + 5];
void _main() { cin >> n; for (int i = 1; i < n; i++) { cin >> u >> v >> w; u++, v++; a[u] ^= w, a[v] ^= w; } for (int i = 1; i <= n; i++) cnt[a[i]]++; int res = 0, fin = 0; for (int i = 1; i <= 15; i++) { res += cnt[i] / 2; if (cnt[i] & 1) fin |= 1 << (i - 1); // 消不完 }
for (int i = 1; i < M; i++) { for (int j = 1; j <= 15; j++) { if (i >> (j - 1) & 1) xorv[i] ^= j; } } for (int i = 1; i < M; i++) { dp[i] = __builtin_popcount(i) - 1; if (xorv[i]) continue; for (int j = (i - 1) & i; j; j = (j - 1) & i) { if (xorv[j]) continue; dp[i] = min(dp[i], dp[j] + dp[i ^ j]); } } cout << res + dp[fin]; }
21. 分数规划
分数规划一般与其他算法一起出现,比如:
与 01 背包结合,称为最优比率背包;
与最小生成树结合,称为最优比率生成树;
与最短路结合,称为最优密度路径;
与 SPFA 判负环结合,称为最优比率环;
与网络流结合,称为最优密度子图。
21.1 模型
分数规划的基本模型是:有 n 个物品,每种物品有两个权值 a,b,选出若干个最大化或最小化 ∑b∑a。
int tot = 0, head[N]; structEdge { int next, to; double dis; } edge[N << 1]; inlinevoidadd_edge(int u, int v, double w){ edge[++tot].next = head[u], edge[tot].to = v, edge[tot].dis = w, head[u] = tot; } int n, m, u, v; double w;
deque<int> q; double dis[N]; int cnt[N]; bitset<N> vis;
inlineboolspfa(int s, double x){ for (int i = 1; i <= n; i++) dis[i] = 1e9; q.clear(), memset(cnt, 0, sizeof(cnt)), vis.reset(); q.emplace_back(s), dis[s] = 0, vis[s] = 1, cnt[s] = 1; while (!q.empty()) { int u = q.front(); q.pop_front(), vis[u] = 0; if (!q.empty() && dis[q.front()] > dis[q.back()]) swap(q.front(), q.back()); for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; double w = edge[j].dis - x; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (++cnt[v] >= n) returntrue; if (vis[v]) continue; vis[v] = 1, q.emplace_back(v); if (!q.empty() && dis[q.front()] > dis[q.back()]) swap(q.front(), q.back()); } } } returnfalse; }
void _main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> u >> v >> w, add_edge(u, v, w); double l = -1e7, r = 1e7; while (r - l > eps) { double mid = (l + r) / 2; if (spfa(1, mid)) r = mid; else l = mid; } cout << fixed << setprecision(8) << l; }
constint N = 305, M = 5e4 + 5; int n, m, p, q, u, v, deg[N]; int tot = 0, head[N]; structEdge { int next, to; } edge[M << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } double a[N], dp[N];
void _main() { cin >> n >> m >> p >> q; for (int i = 1; i <= m; i++) { cin >> u >> v, deg[u]++, deg[v]++; add_edge(u, v), add_edge(v, u); } GuassSolution<N> sol(n); for (int u = 1; u <= n; u++) { fill(a + 1, a + n + 1, 0.0); a[u] = 1.0; for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; a[v] = -(1.0 - 1.0 * p / q) / deg[v]; } sol.add(a + 1, u == 1); } sol.solve(dp + 1); for (int i = 1; i <= n; i++) cout << fixed << setprecision(12) << 1.0 * p / q * dp[i] << '\n'; }
constint N = 2005; int n, m; char c; bitset<N> a[N]; int v[N], id[N];
intguass(){ int cnt = 0; for (int k = 1; k <= n; k++) { int mx = m + 1; for (int i = k; i <= m; i++) { if (a[i][k] && id[mx] > id[i]) mx = i; } if (mx == m + 1) return-1; cnt = max(cnt, id[mx]); swap(a[k], a[mx]), swap(v[k], v[mx]), swap(id[k], id[mx]); for (int i = 1; i <= m; i++) { if (i != k && a[i][k]) a[i] ^= a[k], v[i] ^= v[k]; } } return cnt; }
void _main() { cin >> n >> m; iota(id + 1, id + m + 2, 1); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) cin >> c, a[i][j] = c ^ 48; cin >> c, v[i] = c ^ 48; } int h = guass(); if (h == -1) return cout << "Cannot Determine", void(); cout << h << '\n'; for (int i = 1; i <= n; i++) cout << (v[i] ? "?y7M#\n" : "Earth\n"); }
constint N = 35; int n, x, y, st[N], ed[N]; bitset<N> a[N];
intguass(){ int cnt = 0; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { if (a[j][i]) {swap(a[i], a[j]), swap(ed[i], ed[j]); break;} } for (int j = 1; j <= n; j++) { if (i != j && a[j][i]) a[j] ^= a[i], ed[j] ^= ed[i]; } } for (int i = 1; i <= n; i++) { if (a[i].count()) continue; if (ed[i]) return-1; cnt++; } return cnt; }
void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> st[i]; for (int i = 1; i <= n; i++) cin >> ed[i], ed[i] ^= st[i]; for (int i = 1; i <= n; i++) a[i].reset(); while (cin >> x >> y, x && y) a[y][x] = 1; for (int i = 1; i <= n; i++) a[i][i] = 1; int x = guass(); if (x == -1) cout << "Oh,it's impossible~!!\n"; else cout << (1LL << x) << '\n'; }
template <classT, constint N, classOp1, classOp2, const T o = 0> struct matrix { Op1 op1{}; Op2 op2{}; T val[N][N]; T* operator[] (int x) {return val[x];} matrix<T, N, Op1, Op2, o> operator* (matrix<T, N, Op1, Op2, o> B) { auto& A = *this; matrix<T, N, Op1, Op2, o> C; for (int i = 0; i < N; i++) { fill(C[i], C[i] + N, o); for (int k = 0; k < N; k++) { for (int j = 0; j < N; j++) C[i][j] = op1(C[i][j], op2(A[i][k], B[k][j])); } } return C; } matrix<T, N, Op1, Op2, o>& operator*= (matrix<T, N, Op1, Op2, o> B) {return *this = *this * B;} }; template <classT> structAddOP { constexpr T operator()(T a, T b){return a + b;} }; template <classT> structMinOP { constexpr T operator()(T a, T b){returnmin(a, b);} }; template <classT> structMaxOP { constexpr T operator()(T a, T b){returnmax(a, b);} };
我们希望找到一个矩阵 A,使得向量 (f1,j,f2,j,⋯,fn,j,f1,j−1,f2,j−1,⋯,fn,j−1) 在乘上 A 后变为 (f1,j+1,f2,j+1,⋯,fn,j+1,f1,j,f2,j,⋯,fn,j)。这是容易的,根据转移方程的系数构造即可。最后的答案为 dpn,m=fn,m−fn,m−2。复杂度 O(n3logm)。
这个题告诉我们:DP 状态一维很小,一维很大时,就要考虑矩阵快速幂优化 DP 了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
int n, m; matrix<mint, 100> A; mint f(int n, int m){ if (m <= 0) return0; matrix<mint, 100> B; B.val[0][0] = 1; auto C = B * mpow(A, m - 1); return C.val[0][n - 1]; }
void _main() { cin >> n >> m; for (int i = 0; i < n; i++) { A.val[i][i] = 1, A.val[i + n][i] = 1, A.val[i][i + n] = 1; if (i != 0) A.val[i - 1][i] = 1; if (i != n - 1) A.val[i + 1][i] = 1; } cout << f(n, m) - f(n, m - 2); }
constint N = 255; longlong A[31][N][N], dp[2][N]; int n, m, t, k, u, v, w, val[N]; intf(int x, int y){return x * n + y - 1;} structnode { int t, x, y; } a[N];
void _main() { cin >> n >> m >> t >> k; for (int i = 1; i <= n; i++) cin >> val[i]; memset(A, 0xcf, sizeof(A)); for (int i = 0; i < 4; i++) { for (int j = 1; j <= n; j++) A[0][f(i, j)][f(i + 1, j)] = 0; } for (int i = 1; i <= m; i++) { cin >> u >> v >> w; A[0][f(4, v)][f(5 - w, u)] = val[v]; } for (int s = 0; s < 30; s++) { for (int i = 0; i < n * 5; i++) { for (int k = 0; k < n * 5; k++) { for (int j = 0; j < n * 5; j++) { A[s + 1][i][k] = max(A[s + 1][i][k], A[s][i][j] + A[s][j][k]); } } } } memset(dp, 0xcf, sizeof(dp)); int st = 0; dp[0][f(4, 1)] = val[1]; auto trans = [&](int s) -> void { for (int d = 0; d < 30; d++) { if (!(s >> d & 1)) continue; st ^= 1; memset(dp[st], 0xcf, sizeof(dp[st])); for (int i = 0; i < 5 * n; i++) { for (int j = 0; j < 5 * n; j++) { dp[st][i] = max(dp[st][i], dp[st ^ 1][j] + A[d][i][j]); } } } }; for (int i = 1; i <= k; i++) cin >> a[i].t >> a[i].x >> a[i].y; sort(a + 1, a + k + 1, [](const node& a, const node& b) -> bool { return a.t < b.t; }); for (int i = 1; i <= k; i++) { trans(a[i].t - a[i - 1].t); dp[st][f(4, a[i].x)] += a[i].y; } trans(t - a[k].t); cout << (dp[st][f(4, 1)] < 0 ? -1 : dp[st][f(4, 1)]); }
constint N = 2e5 + 5; constlonglong inf = 1e15; using node = matrix<longlong, 3, MinOP<longlong>, AddOP<longlong>, inf>;
int n, q, k, u, v; longlong a[N]; int tot = 0, head[N]; structEdge { int next, to; } edge[N << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; }
int dep[N], sz[N], fa[N], son[N], top[N]; longlong s[N], dis[N]; voiddfs1(int u){ sz[u] = 1, dis[u] = dis[fa[u]] + a[u], dep[u] = dep[fa[u]] + 1; for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; if (v == fa[u]) continue; fa[v] = u, dfs1(v), sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } voiddfs2(int u, int t){ top[u] = t; if (son[u]) dfs2(son[u], t); for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; if (v != fa[u] && v != son[u]) dfs2(v, v); } } intlca(int u, int v){ while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); u = fa[top[u]]; } return dep[u] < dep[v] ? u : v; } int pa[20][N]; node I, B[N], mul[20][N], rmul[20][N]; voiddfs3(int u){ pa[0][u] = fa[u], mul[0][u] = rmul[0][u] = B[u]; for (int i = 1; i < 20; i++) { pa[i][u] = pa[i - 1][pa[i - 1][u]]; mul[i][u] = mul[i - 1][u] * mul[i - 1][pa[i - 1][u]]; rmul[i][u] = rmul[i - 1][pa[i - 1][u]] * rmul[i - 1][u]; } for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; if (v == fa[u]) continue; dfs3(v); } } node ask(int u, int v){ node x = I, y = I; if (dep[u] < dep[v]) y = B[v], v = fa[v]; for (int i = 19; i >= 0; i--) { if (dep[pa[i][u]] >= dep[v]) x = rmul[i][u] * x, u = pa[i][u]; } if (u == v) return y * B[u] * x; for (int i = 19; i >= 0; i--) { if (pa[i][u] == pa[i][v]) continue; x = rmul[i][u] * x, y = y * mul[i][v]; u = pa[i][u], v = pa[i][v]; } return y * B[v] * B[fa[v]] * B[u] * x; }
void _main() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i != j) I[i][j] = inf; } } cin >> n >> q >> k; for (int i = 1; i <= n; i++) cin >> a[i]; fill(s + 1, s + n + 1, inf); for (int i = 1; i < n; i++) { cin >> u >> v; add_edge(u, v), add_edge(v, u); s[u] = min(s[u], a[v]), s[v] = min(s[v], a[u]); } dfs1(1), dfs2(1, -1); if (k == 1) { while (q--) { cin >> u >> v; int f = lca(u, v); cout << dis[u] + dis[v] - 2 * dis[f] + a[f] << '\n'; } return; } B[0] = I; for (int i = 1; i <= n; i++) { node& A = B[i]; if (k == 2) { A[0][0] = A[0][1] = a[i]; A[1][0] = A[2][2] = 0; A[0][2] = A[1][1] = A[1][2] = A[2][0] = A[2][1] = inf; } else { A[0][0] = A[0][1] = A[0][2] = a[i]; A[1][0] = A[2][1] = 0; A[1][1] = s[i], A[1][2] = a[i] + s[i]; A[2][0] = A[2][2] = inf; } } dfs3(1); while (q--) { cin >> u >> v; if (u == v) {cout << a[u] << '\n'; continue;} if (dep[u] < dep[v]) swap(u, v); node x = ask(fa[u], v), y = I; if (k == 2) y[0][0] = a[u]; else y[0][0] = a[u], y[0][1] = a[u] + s[u]; x *= y, cout << x[0][0] << '\n'; } }
constint N = 205; int n, k, l[N], r[N]; int tot = 0, head[N]; structEdge { int next, to; } edge[N << 1]; inlinevoidadd_edge(int u, int v){ edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot; } discrete_map<int, N << 2> mp;
mint f[2][N], g[2][N]; voiddfs(int u, int fa, int ql, int qr){ int l0 = max(ql, l[u]), r0 = min(qr, r[u]); if (l0 > r0) l0 = 1, r0 = 0; int s = r0 - l0 + 1; mint h = 1LL * r0 * (r0 + 1) / 2 - 1LL * l0 * (l0 - 1) / 2; f[0][u] = f[1][u] = s, g[0][u] = g[1][u] = h; for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to; if (v == fa) continue; dfs(v, u, ql, qr); f[0][u] += f[1][u] * f[1][v]; g[0][u] += g[1][v] * f[1][u] + f[1][v] * g[1][u]; f[1][u] += f[1][v] * s; g[1][u] += g[1][v] * s + f[1][v] * h; } } voidsolve(mint w, int ql, int qr, mint& ans1, mint& ans2){ dfs(1, -1, ql, qr); for (int i = 1; i <= n; i++) ans1 += w * f[0][i], ans2 += w * g[0][i]; }
mint a[N << 2], b[N << 2], c[N << 2]; mint lagrange(int n, mint x0, mint *x, mint *y){ mint res = 0; for (int i = 0; i < n; i++) { mint a = 1, b = 1; for (int j = 0; j < n; j++) { if (i != j) a *= x0 - x[j], b *= x[i] - x[j]; } res += a / b * y[i]; } return res; }
void _main() { cin >> n >> k; int v = 0; for (int i = 1; i <= n; i++) { cin >> l[i] >> r[i], v = max(v, r[i] + 1); mp.add(l[i]), mp.add(r[i]), mp.add(max(0, l[i] - k)), mp.add(max(0, r[i] - k)); } mp.add(v), mp(); for (int i = 1, u, v; i < n; i++) cin >> u >> v, add_edge(u, v), add_edge(v, u); mint res1 = 0, res2 = 0; for (int i = 1; i < mp.width; i++) { int ql = mp.value(i), qr = ql + k, j = 0; for (; j <= n + 1; j++, qr++) { if (mp.value(i) + j == mp.value(i + 1)) break; solve(1, ql, qr, res1, res2), solve(-1, ++ql, qr, res1, res2); a[j] = mp.value(i) + j, b[j] = res1, c[j] = res2; } if (mp.value(i) + j < mp.value(i + 1)) { res1 = lagrange(j, mp.value(i + 1) - 1, a, b); res2 = lagrange(j, mp.value(i + 1) - 1, a, c); } } cout << res1 << '\n' << res2; }
#define int long long constint N = 1e5 + 5; int h, s[3], a, b, c;
void _main() { cin >> h >> s[0] >> s[1] >> s[2]; sort(s, s + 3), a = s[0], b = s[1], c = s[2], h--; for (int i = 0; i < a; i++) { add_edge(i, (i + c) % a, c); add_edge(i, (i + b) % a, b); } SPFA::spfa(0); int res = 0; for (int i = 0; i < a; i++) { if (h >= SPFA::dis[i]) res += (h - SPFA::dis[i]) / a + 1; } cout << res; }
int m, n, l, r, x, a[N]; longlongquery(longlong x){ longlong res = 0; for (int i = 0; i < a[1]; i++) { if (x >= SPFA::dis[i]) res += (x - SPFA::dis[i]) / a[1] + 1; } return res; }
void _main() { cin >> m >> l >> r; for (int i = 1; i <= m; i++) { cin >> x; if (x != 0) a[++n] = x; } sort(a + 1, a + n + 1); for (int x = 0; x < a[1]; x++) { for (int i = 2; i <= n; i++) add_edge(x, (x + a[i]) % a[1], a[i]); } SPFA::spfa(0); cout << query(r) - query(l - 1); }
#define int long long constint N = 60005; int m, k, d[10], dis[5][N];
int tot = 0, head[N]; structEdge { int next, to, dis; } edge[N << 1]; inlinevoidadd_edge(int u, int v, int w){ edge[++tot].next = head[u]; edge[tot].to = v, edge[tot].dis = w; head[u] = tot; }
structnode { int to, dis; node(int x = 0, int y = 0) : to(x), dis(y) {} booloperator< (const node& other) const {return dis > other.dis;} }; priority_queue<node> q; inlinevoiddijkstra(){ memset(dis, 0x3f, sizeof(dis)); dis[2][0] = 0, q.emplace(2, 0); while (!q.empty()) { int u = q.top().to, d = q.top().dis; q.pop(); for (int j = head[u]; j != 0; j = edge[j].next) { int v = edge[j].to, w = edge[j].dis, c = dis[u][d % m] + w; if (dis[v][c % m] > c) dis[v][c % m] = c, q.emplace(v, c); } } }
void _main() { cin >> k >> d[1] >> d[2] >> d[3] >> d[4]; add_edge(1, 2, d[1]), add_edge(2, 1, d[1]); add_edge(2, 3, d[2]), add_edge(3, 2, d[2]); add_edge(3, 4, d[3]), add_edge(4, 3, d[3]); add_edge(4, 1, d[4]), add_edge(1, 4, d[4]); m = min(d[1], d[2]) * 2; memset(dis, 0x3f, sizeof(dis)); dijkstra(); int res = LLONG_MAX; for (int i = 0; i < m; i++) { if (dis[2][i] >= k) res = min(res, dis[2][i]); else { int x = k - dis[2][i], t = x / m * m + m * (x % m != 0); res = min(res, t + dis[2][i]); } } cout << res; }
#define int long long constint N = 1e6 + 5; int n, m, p, a[N]; void _main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); int p = max<int>(1, a[1] - m); if (p == 1) return cout << -1, void(); for (int i = 1; i <= n; i++) { for (int j = max(a[i - 1] + 1, a[i] - m); j <= a[i]; j++) { if (j == p) continue; for (int k = 0; k < p; k++) add_edge(k, (k + j) % p, j); } } SPFA::spfa(0); int res = 0; for (int i = 0; i < p; i++) { if (SPFA::dis[i] >= 0x3f3f3f3f3f3f3f3f) return cout << -1, void(); res = max(res, SPFA::dis[i] - p); } cout << res; }