A
对于一个重量为 的物品,他的生成函数为 。
对于以 为根的子树,设答案的生成函数为 。那么如果要更新一个点的答案,先把他所有儿子的生成函数乘起来,求出前 项,然后直接剪掉即可。最后得到 ,用线性递推算第 项即可。
时间复杂度
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 9; const int P = 998244353; int X[555], Y[555]; int len = 1, rev[N], ans[N]; vector<int> dp[111], e[111]; int lim, s[111], c[111]; int inv(int x, int base = P - 2) { int res = 1; while (base) { if (base & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; base >>= 1; } return res; } void init() { for (int i = 0; i < len; i++) { rev[i] = rev[i >> 1] >> 1; if (i & 1) rev[i] |= (len >> 1); } } void NTT(vector<int> &x, int op) { for (int i = 0; i < len; i++) if (i < rev[i]) swap(x[i], x[rev[i]]); for (int i = 2; i <= len; i <<= 1) { int mid = i >> 1; int wn = inv(3, (P - 1) / i); if (op == -1) wn = inv(wn, P - 2); for (int j = 0; j < len; j += i) { for (int k = j, now = 1; k < j + mid; k++) { int aa = x[k], bb = 1ll * x[k + mid] * now % P; now = 1ll * now * wn % P; x[k] = (aa + bb) % P; x[k + mid] = (aa - bb + P) % P; } } } if (op == -1) { int INV = inv(len); for (int i = 0; i < len; i++) x[i] = 1ll * x[i] * INV % P; } } vector<int> mul(vector<int> a, vector<int> b) { vector<int> c; int Lim = a.size() + b.size(); len = 1; while (len < Lim) len <<= 1; init(); a.resize(len + 1); b.resize(len + 1); c.resize(len + 1); NTT(a, 1); NTT(b, 1); for (int i = 0; i <= len; i++) c[i] = 1ll * a[i] * b[i] % P; NTT(c, -1); return c; } void dfs(int rt) { dp[rt].resize(lim + 1); for (int i = 0; i <= lim; i += s[rt]) dp[rt][i] = 1; for (int i = 0; i < e[rt].size(); i++) { int v = e[rt][i]; dfs(v); dp[rt] = mul(dp[v], dp[rt]); dp[rt].resize(lim + 1); } for (int i = 0; i < c[rt]; i++) dp[rt][i] = 0; } int cal(int num, int x[], int y[], int id) { int ans = 0; for (int i = 1; i <= num; i++) { int res1 = y[i], res2 = 1; for (int j = 1; j <= num; j++) { if (i == j) continue; res1 = 1ll * res1 * ((id - x[j] + P) % P) % P; res2 = 1ll * res2 * ((x[i] - x[j] + P) % P) % P; } ans += 1ll * res1 * inv(res2) % P; if (ans >= P) ans -= P; } return ans; } int Fa[N], rt; signed main() { lim = 50000; int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n - 1; i++) { int u, v; scanf("%d%d", &u, &v); e[u].push_back(v); Fa[v] = 1; } for (int i = 1; i <= n; i++) if (!Fa[i]) rt = i; for (int i = 1; i <= n; i++) scanf("%d", &s[i]); for (int i = 1; i <= n; i++) scanf("%d", &c[i]); dfs(rt); while (q--) { int w; scanf("%d", &w); if (w <= lim) printf("%d", dp[rt][w]); else { int j; for (j = 10000; j <= 10000 + 60; j++) if (j % 60 == w % 60) break; for (int i = 1; i <= n + 1; i++) { X[i] = j; Y[i] = dp[rt][j]; j += 60; } printf("%d", cal(n + 1, X, Y, w)); } puts(""); } }
B
考虑期望 。
设 为当前非递减序列最后一个数是 ,之后能得到的期望数字个数。那么有转移方程:
$xxx$ 大的数。
把 全部移到左边可以得到
$E(x^2)g(x)$
因为 ,所以可得
$dpf_xg_x$。
最终答案为:
$$
因为第一步可以抽到任意一个数。
#include <bits/stdc++.h> #define int long long using namespace std; const int p = 998244353; int n, F = 1, c, sum; int a[101]; int inv(int x, int base = p - 2) { int res = 1; while (base) { if (base & 1) res = res * x % p; x = x * x % p; base >>= 1; } return res; } signed main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i], sum += a[i]; for (int i = 0; i < n; i++) F = F * sum % p * inv(sum - a[i]) % p, c += a[i] * inv(sum - a[i]); cout << (c % p * 2 * F + F) % p << endl; }
C
先假设
首先,如果 那么无解。所以一定有
给三个串都加上 个 ,就变成了长度为 ,三个 分别为 的子问题。
因为 ,所以 。
给前两个串放 个 ,后两个串放 个 。
这样下来,第一个字符串长度为 ,第二个字符串长度为 ,第三个字符串长度为 。并且 也满足条件。长度不够的用其他不冲突字符补上就好了。
#include <bits/stdc++.h> using namespace std; int main() { int a, b, c, n; cin >> a >> b >> c >> n; int minn = min(a, min(b, c)); if (b + c + a - 2 * minn > n) { puts("NO"); return 0; } string s1, s2, s3; s1 = string(a, 'a') + string(c - minn, 'b'); s2 = string(a, 'a') + string(b - minn, 'c'); s3 = string(minn, 'a') + string(b - minn, 'c') + string(c - minn, 'b'); s1 += string(n - s1.length(), 'x'); s2 += string(n - s2.length(), 'y'); s3 += string(n - s3.length(), 'z'); cout << s1 << endl; cout << s2 << endl; cout << s3 << endl; }
D
前考虑删掉指定的 条边后,再加 条边还是树的方案数。
假设删掉 条边,剩下连通块大小为
根据 序列可知方案数为
其中后面的 可以等价于,在 个连通块中,每个连通块选一个点的方案数。
设 表示以 为根的子树内,删掉 条边, 所在连通块是否已经选了点的方案数。树上背包转移即可。时间复杂度 。
#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 9; const int p = 998244353; int n, k, sz[N]; vector<int> e[N]; int f[N][105][2], g[105][2]; void dfs(int x, int fa) { sz[x] = 1; f[x][1][0] = f[x][1][1] = 1; for (int to : e[x]) if (to != fa) { dfs(to, x); memcpy(g, f[x], sizeof(g)); memset(f[x], 0, sizeof(f[x])); for (int a = 1; a <= min(sz[x], k + 1); a++) for (int b = 1; b <= min(sz[to], k + 1) && a + b - 1 <= k + 1; b++) { f[x][a + b - 1][0] = (f[x][a + b - 1][0] + 1ll * g[a][0] * f[to][b][0]) % p; f[x][a + b - 1][1] = (f[x][a + b - 1][1] + 1ll * g[a][0] * f[to][b][1]) % p; f[x][a + b - 1][1] = (f[x][a + b - 1][1] + 1ll * g[a][1] * f[to][b][0]) % p; f[x][a + b][0] = (f[x][a + b][0] + 1ll * g[a][0] * f[to][b][1]) % p; f[x][a + b][1] = (f[x][a + b][1] + 1ll * g[a][1] * f[to][b][1]) % p; } sz[x] += sz[to]; } } int main() { scanf("%d%d", &n, &k); for (int i = 1; i < n; i++) { int x, y; scanf("%d%d", &x, &y); e[x].push_back(y); e[y].push_back(x); } dfs(1, 0); int ans = f[1][k + 1][1]; for (int i = 1; i < k; i++) ans = 1ll * ans * n % p; cout << ans << endl; }
E
容易发现,只要确定树上一个点的权值,那么整棵树的权值也就确定了。不妨假设 ,先求出一个初始答案。
当 时,。那么需要找到满足所有 的 的个数。
但是不能在不等式上同时异或一个数。否则直接异或上 就可以求出答案了。
但发现在一些特殊的 下,不等式可以同时异或一个数。那就是当 的最高 位相等,且 剩下位数全是 , 剩下位数全是 的时候。那这就启发将 拆成 个这样的区间计算,并且这些区间不会相交。
最后合法的 满足覆盖他的区间个数为 ,就差分计算答案即可。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 9; const int M = (1 << 30) - 1; int n, L[N], R[N]; vector<pair<int, int>>p, G[N]; void insert(int a, int b) { int res = a ^ b; for (int i = 0; i < 30; ++i) { int t = res ^ (1 << i) ^ (res & ((1 << i) - 1)); if ((t ^ a) > b) p.push_back({t, t + (1 << i) - 1}); } } void dfs(int x, int fa, int k) { insert(k, R[x]), insert(M ^ k, M ^ L[x]); for (auto it : G[x]) if (it.first != fa) dfs(it.first, x, k ^ it.second); } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d", &L[i], &R[i]); for (int i = 1; i < n; ++i) { int x, y, w; scanf("%d%d%d", &x, &y, &w), G[x].emplace_back(y, w), G[y].emplace_back(x, w); } dfs(1, 0, 0); sort(p.begin(), p.end()); int ans = 0, x = 0; for (auto it : p) { int l = it.first, r = it.second; if (l > x) ans += l - x - 1; x = max(x, r); } if (x < M) ans += M - x; cout << ans << endl; return 0; }
F
第一种操作会使边数
第二种操作会使点数 ,边数
两种操作都会使得 奇偶性改变。所以最终答案只和 的奇偶性有关。
#include<bits/stdc++.h> using namespace std; int a, b; int main(){ cin >> a >> b; puts( (a + b) & 1 ? "Alice" : "Bob"); return 0; }
G
让我们考虑 的特殊情况。
$Dna_i+ka_i\geq kn,k\leq 50$ ,数据范围都很小,不妨考虑容斥。
根据容斥步骤,需要钦定 个不合法的 ,剩下的随便放,然后乘上容斥系数 。
设 表示钦定 组不合法,他们的和是 的方案数。最终答案就是
$D!a_iij\mathcal O((nk)^2)$
#include <bits/stdc++.h> using namespace std; const int N = 2e3 + 5e2 + 9; const int p = 998244353; int n, k, d, f[55][N], ans; int inv(int x, int base = p - 2) { int res = 1; while (base) { if (base & 1) res = 1ll * res * x % p; x = 1ll * x * x % p; base >>= 1; } return res; } int fac[30010], ifac[30010]; void init(int n = 30000) { fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % p; ifac[n] = inv(fac[n]); for (int i = n - 1; i >= 0; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % p; assert(1ll * fac[10]*ifac[10] % p == 1); } int C(int n, int m) { return n >= m && m >= 0 ? 1ll * fac[n] * ifac[m] % p * ifac[n - m] % p : 0; } int main() { scanf("%d%d%d", &n, &k, &d); init(); d += n * k; f[0][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 0; j <= i * (k - 1); ++j) for (int l = min(j, k - 1); ~l; --l) f[i][j] = (1ll * f[i - 1][j - l] * C(j, l) + f[i][j]) % p; for (int i = 0; i <= n; ++i) { for (int j = 0, res = 1; j <= i * (k - 1); ++j) { ans = (ans + (i & 1 ? -1ll : 1ll) * C(n, i) * f[i][j] % p * res % p * inv(n - i, d - j)) % p; res = 1ll * res * (d - j) % p * inv(j + 1) % p; } } for (int i = 0; i < n * k; ++i) ans = 1ll * ans * inv(d - i) % p; printf("%d\n", (ans + p) % p); return 0; }
H
有 。枚举 。那么有:
$\mathcal O(n\log n)x>y,m=\lfloor \frac{n}{x}\rfloorf_{x,m}(\sum_{d=1}^ma_{xd}(xd)^c)\mathcal O(n\log n)$
#include <bits/stdc++.h> using namespace std; #define int long long const int P = 998244353; const int N = 1e6 + 9; int dp[N]; int n, a[N], p[N], b[N], c; int inv(int x, int base = P - 2) { int res = 1; while (base) { if (base & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; base >>= 1; } return res; } signed main() { cin >> n >> c; for (int i = 1; i <= n; i++) { cin >> a[i]; p[i] = inv(i, c); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n / i; j++) { dp[j] = (dp[j - 1] + a[i * j] * p[j] % P) % P; } for (int j = 1; j <= n / i; j++) if (__gcd(i, j) == 1) { b[i * j] = (b[i * j] + p[j] * dp[min(n / i, n / j)] % P) % P; } } for (int i = 1; i <= n; i++) b[i] ^= b[i - 1]; cout << b[n]; }
I
若把某个 加一,只可能影响 与 的关系。即当 在 前面时,操作 ,不操作 可以使逆序对 。若对于 在 前面这样的点对 连边,最终的图由几条链构成。一条长为 的链最多让逆序对数减少 。
#include <bits/stdc++.h> #define lowbit(x) (x&-x) using namespace std; const int N = 2e5 + 9; int n; long long ans; int a[N], b[N], c[N]; void add(int x) { while (x <= n) c[x]++, x += lowbit(x); } int get(int x, int res = 0) { while (x) res += c[x], x -= lowbit(x); return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = n; i >= 1; --i) { if (!b[a[i] - 1]) b[a[i]] = 1, a[i]++; } for (int i = n; i >= 1; --i) { add(a[i]); ans += get(a[i] - 1); } printf("%lld\n", ans); return 0; }
J
考虑快速计算一个子矩阵的答案。
$axb$ 同理。
这是个经典问题,二分答案 ,所有数减去 ,区间和大于等于 等价于区间平均值大于等于 。时间复杂度
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 0; const double eps = 1e-8; int n, m, x, y; int a[N]; double sum[N]; bool check(int k, double mid, int n) { double res, mn = 0.0; for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i] - mid; res = sum[n]; for (int i = n + 1; i <= k; i++) { mn = min(mn, sum[i - n]); sum[i] = sum[i - 1] + a[i] - mid; res = max(res, sum[i] - mn); } return res >= 0; } double wrok(int k, int n) { double l = 0.0, r = 100001.0; for (int i = 1; i <= k; i++) scanf("%d", &a[i]); while (r - l > eps) { double mid = (l + r) / 2.0; if (check(k, mid, n)) l = mid; else r = mid; } return r; } int main() { scanf("%d%d%d%d", &n, &m, &x, &y); printf("%.10lf\n", wrok(n, x) + wrok(m, y)); }
全部评论
(0) 回帖