2020-2021:teams:namespace:2020洛谷多校day1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:2020洛谷多校day1 [2020/05/11 16:21] great_designer [题面] |
2020-2021:teams:namespace:2020洛谷多校day1 [2020/05/18 18:07] (当前版本) great_designer |
||
|---|---|---|---|
| 行 339: | 行 339: | ||
| </code> | </code> | ||
| - | |||
| - | 以下四题是未AC的题目。接下来几天看看题解。（待施工） | ||
| =====A===== | =====A===== | ||
| 行 393: | 行 391: | ||
| 2 | 2 | ||
| + | |||
| + | ====题解==== | ||
| + | |||
| + | 我一开始直觉是统计圈的个数（破圈），但后来发现当同时到达顶点的时候，只统计一次爆炸而不是多次，最后只好打算模拟bfs…… | ||
| + | |||
| + | 题解放进了这个页面：[[广度优先搜索_bfs_与标数最短路_dijkstra]] | ||
| =====C===== | =====C===== | ||
| 行 447: | 行 451: | ||
| 575218836 | 575218836 | ||
| + | |||
| + | ====题解==== | ||
| + | |||
| + | 这是本套题最难的题目。难点在于细节特别多。 | ||
| + | |||
| + | 原题题解如下： | ||
| + | |||
| + | 首先考虑p 与k 不互素的情况。这种情况下，整除只与最后一位有关，且有$$\frac{k}{p}-1$$种取法，其余位任取。注意k = p 时答案为[n = 1]，可能会导致部分没有特判的程序挂掉。 | ||
| + | |||
| + | 现在考虑(p, k) = 1 的情况。考虑暴力：dpi,j 表示前i 位和后i 位填好了，其余位取0 时mod p = j的方案数。更新一位的复杂度是O(kp) 的，总复杂度是O(nkp) 的。 | ||
| + | |||
| + | 考虑优化，由费马小定理，ki mod p 存在长度为p − 1 循环节，因此$$k^{i} + k^{n−i−1}\quad mod \ p$$ 也有长度为p − 1 的循环节。按p − 1 分块后，每块的贡献是相同的，而块的背包合并可以通过类似多项式乘法的循环卷积来实现，因此就可以快速幂了。 | ||
| + | |||
| + | 预处理一个块和处理边缘的零散部分的复杂度是O(kp2), 一次块的暴力卷积是O(p2) 的，因此总复杂度为O(kp2 + p2(log n − log p))。 | ||
| + | |||
| + | 标程使用vector 实现，不开O2 也只跑了一秒，应该是不卡常的。 | ||
| + | |||
| + | 以上。 | ||
| + | |||
| + | 好。我可以明确地宣布，到“快速幂”之前的部分还是能看懂的。之后就不知道怎么个递推法了。 | ||
| + | |||
| + | 标程代码如下： | ||
| + | |||
| + | <code C++> | ||
| + | |||
| + | #include<iostream> | ||
| + | #include<vector> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | long long MOD=998244353; | ||
| + | |||
| + | long long power(long long first, long long second, long long z) | ||
| + | { | ||
| + | long long ret = 1; | ||
| + | for(first %= z; second; second >>= 1) | ||
| + | { | ||
| + | if(second & 1) | ||
| + | { | ||
| + | ret = ret * first % z; | ||
| + | } | ||
| + | first = first * first % z; | ||
| + | } | ||
| + | return ret; | ||
| + | } | ||
| + | |||
| + | long long n; | ||
| + | int p, K; | ||
| + | |||
| + | void init(vector <int> & a) | ||
| + | { | ||
| + | a.clear(); | ||
| + | a.resize(p); | ||
| + | a[0] = 1; | ||
| + | } | ||
| + | |||
| + | void upd(vector <int> &a, long long b, int st = 0) | ||
| + | { | ||
| + | int first; | ||
| + | if (b == n - b - 1) | ||
| + | { | ||
| + | first = int(power(K, b, p)) % p; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | first = int(power(K, b, p) + power(K, n - b - 1, p)) % p; | ||
| + | } | ||
| + | vector <int> c; | ||
| + | c.resize(p); | ||
| + | int i; | ||
| + | for(i = st; i < K; i++) | ||
| + | { | ||
| + | int j; | ||
| + | for(j = 0; j < p; j++) | ||
| + | { | ||
| + | (c[(j + i * first) % p] += a[j]) %= MOD; | ||
| + | } | ||
| + | } | ||
| + | swap(a, c); | ||
| + | } | ||
| + | |||
| + | void mul(vector <int> &a, vector <int> &b) | ||
| + | { | ||
| + | vector <int> c; | ||
| + | c.resize(p); | ||
| + | int i; | ||
| + | for(i = 0; i < p; i++) | ||
| + | { | ||
| + | int j; | ||
| + | for(j = 0; j < p; j++) | ||
| + | { | ||
| + | int first = (i + j) % p; | ||
| + | c[first] = int((c[first] + (long long)a[i] * b[j]) % MOD); | ||
| + | } | ||
| + | } | ||
| + | swap(a, c); | ||
| + | } | ||
| + | |||
| + | void power(vector <int> &a, long long b) | ||
| + | { | ||
| + | vector <int> ret; | ||
| + | init (ret); | ||
| + | for(;b;b>>=1) | ||
| + | { | ||
| + | if(b & 1) | ||
| + | { | ||
| + | mul(ret, a); | ||
| + | } | ||
| + | mul(a, a); | ||
| + | } | ||
| + | swap(a, ret); | ||
| + | } | ||
| + | |||
| + | vector <int> ans, tr; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%lld%d%d", &n, &p, &K); | ||
| + | if(n == 1) | ||
| + | { | ||
| + | int aa = 0; | ||
| + | int i; | ||
| + | for(i = 0; i < K; i++) | ||
| + | { | ||
| + | if (i % p == 0) | ||
| + | { | ||
| + | aa ++; | ||
| + | } | ||
| + | } | ||
| + | cout << aa << endl; | ||
| + | return 0; | ||
| + | } | ||
| + | long long sz = n / 2 - 1; | ||
| + | if (K % p == 0) | ||
| + | { | ||
| + | cout << (K / p - 1) * power(K, sz + (n & 1), MOD) % MOD << endl; | ||
| + | return 0; | ||
| + | } | ||
| + | init(ans); | ||
| + | init(tr); | ||
| + | long long tot = sz / (p - 1); | ||
| + | if(tot) | ||
| + | { | ||
| + | int i; | ||
| + | for(i = 2; i <= p; i++) | ||
| + | { | ||
| + | upd(tr, i - 1); | ||
| + | } | ||
| + | power(tr, tot); | ||
| + | mul(ans, tr); | ||
| + | } | ||
| + | upd(ans, 0, 1); | ||
| + | long long i; | ||
| + | for(i = 2 + tot * (p - 1); i <= (n + 1) / 2; i++) | ||
| + | { | ||
| + | upd(ans, i - 1); | ||
| + | } | ||
| + | printf("%d\n", ans[0]); | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | 总之这是道值得好好研究的题目。 | ||
| =====D===== | =====D===== | ||
| 行 483: | 行 650: | ||
| 123570404 | 123570404 | ||
| + | |||
| + | ====题解==== | ||
| + | |||
| + | 本题找到了“逆变换”结论：给定值，判断是第几个。因此最终就是一个二分查找。 | ||
| + | |||
| + | 我想新开一个页面来讲解本题。题解也先放进去了。 | ||
| + | |||
| + | [[裴蜀定理与一次不定方程]] | ||
| + | |||
| =====H===== | =====H===== | ||
| 行 522: | 行 698: | ||
| 8 2 0 0 0 | 8 2 0 0 0 | ||
| + | |||
| + | ====题解==== | ||
| + | |||
| + | 这个题解就很高端了…… | ||
| + | |||
| + | 采用支持合并的数据结构，下标维护标号，信息维护深度总和与点数，在每个点合并子树信息并维护答案。合并的两端的某个颜色的信息分别为(dep1, cnt1), (dep2, cnt2)，当前点深度为d，则合并时产生贡献： | ||
| + | |||
| + | $$dep_1cnt_2 + dep_2cnt_1 − 2d \ cnt_1cnt_2$$ | ||
| + | |||
| + | 采用线段树合并等的时间复杂度为O(n log n)，采用启发式合并的set(map) 也能够以O(n log2 n) 的复杂度通过。 | ||
| + | |||
| + | 给了两份代码： | ||
| + | |||
| + | <code C++> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | #include<vector> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | struct Node | ||
| + | { | ||
| + | long long dep; | ||
| + | int l, r, cnt; | ||
| + | }; | ||
| + | |||
| + | struct Node t[201111 * 19]; | ||
| + | |||
| + | vector <int> E[201111]; | ||
| + | |||
| + | int n, tcnt; | ||
| + | int a[201111], rt[201111], dep[201111]; | ||
| + | |||
| + | long long sc[201111], delta; | ||
| + | int curdep; | ||
| + | |||
| + | int Merge(int x, int y, int l, int r) | ||
| + | { | ||
| + | if (!y) return x; | ||
| + | if (!x) return y; | ||
| + | if (l == r) | ||
| + | { | ||
| + | delta += t[x].dep * t[y].cnt + t[y].dep * t[x].cnt - 2ll * curdep * t[x].cnt * t[y].cnt; | ||
| + | t[x].dep += t[y].dep; | ||
| + | t[x].cnt += t[y].cnt; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | int mid = (l + r) / 2; | ||
| + | t[x].l = Merge(t[x].l, t[y].l, l, mid); | ||
| + | t[x].r = Merge(t[x].r, t[y].r, mid + 1, r); | ||
| + | } | ||
| + | return x; | ||
| + | } | ||
| + | |||
| + | int init(int p, int l, int r) | ||
| + | { | ||
| + | int x = ++tcnt; | ||
| + | if (l < r) | ||
| + | { | ||
| + | int mid = (l + r) / 2; | ||
| + | if (p <= mid) t[x].l = init(p, l, mid); | ||
| + | else t[x].r = init(p, mid + 1, r); | ||
| + | } | ||
| + | else t[x].dep = curdep, t[x].cnt = 1; | ||
| + | return x; | ||
| + | } | ||
| + | |||
| + | |||
| + | |||
| + | void dfs(int x, int fa) | ||
| + | { | ||
| + | curdep = dep[x]; | ||
| + | rt[x] = init(a[x], 1, n); | ||
| + | for (auto v : E[x]) | ||
| + | { | ||
| + | if (v != fa) | ||
| + | { | ||
| + | dep[v] = dep[x] + 1; | ||
| + | dfs(v, x); | ||
| + | sc[x] += sc[v]; | ||
| + | delta = 0; | ||
| + | curdep = dep[x]; | ||
| + | rt[x] = Merge(rt[x], rt[v], 1, n); | ||
| + | sc[x] += delta; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%d", &n); | ||
| + | int i; | ||
| + | for(i = 1; i <= n; i++) | ||
| + | { | ||
| + | scanf("%d", a + i); | ||
| + | } | ||
| + | for(i = 1; i < n; i++) | ||
| + | { | ||
| + | int u, v; | ||
| + | scanf("%d%d", &u, &v); | ||
| + | E[u].push_back(v); | ||
| + | E[v].push_back(u); | ||
| + | } | ||
| + | dfs(1, -1); | ||
| + | for(i = 1; i <= n; i++) | ||
| + | { | ||
| + | printf("%lld ", sc[i]); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | <code C++> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | #include<vector> | ||
| + | #include<map> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | vector <int> E[101111]; | ||
| + | |||
| + | int n; | ||
| + | int a[101111], dep[101111]; | ||
| + | |||
| + | map<int, pair<long long, int> > rt[101111]; | ||
| + | |||
| + | long long sc[101111], delta; | ||
| + | int curdep; | ||
| + | |||
| + | void Merge(map<int, pair<long long, int> >& a, map<int, pair<long long, int> >& b) | ||
| + | { | ||
| + | if (a.size() < b.size()) swap(a, b); | ||
| + | for (auto& v : b) | ||
| + | { | ||
| + | int col = v.first; | ||
| + | auto it = a.find(col); | ||
| + | if (it != a.end()) | ||
| + | { | ||
| + | long long d1 = it->second.first, c1 = it->second.second; | ||
| + | long long d2 = v.second.first, c2 = v.second.second; | ||
| + | delta += d1 * c2 + d2 * c1 - 2LL* curdep * c1 * c2; | ||
| + | it->second.first += d2; | ||
| + | it->second.second += int(c2); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | a.insert(v); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | void init(map<int, pair<long long, int>>& r, int p) | ||
| + | { | ||
| + | r[p] = { curdep, 1 }; | ||
| + | } | ||
| + | |||
| + | |||
| + | |||
| + | void dfs(int x, int fa) | ||
| + | { | ||
| + | curdep = dep[x]; | ||
| + | init(rt[x], a[x]); | ||
| + | for (auto v : E[x]) | ||
| + | { | ||
| + | if (v != fa) | ||
| + | { | ||
| + | dep[v] = dep[x] + 1; | ||
| + | dfs(v, x); | ||
| + | sc[x] += sc[v]; | ||
| + | delta = 0; | ||
| + | curdep = dep[x]; | ||
| + | Merge(rt[x], rt[v]); | ||
| + | sc[x] += delta; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%d", &n); | ||
| + | int i; | ||
| + | for(i = 1; i <= n; i++) | ||
| + | { | ||
| + | scanf("%d", a + i); | ||
| + | } | ||
| + | for(i = 1; i < n; i++) | ||
| + | { | ||
| + | int u, v; | ||
| + | scanf("%d%d", &u, &v); | ||
| + | E[u].push_back(v); | ||
| + | E[v].push_back(u); | ||
| + | } | ||
| + | dfs(1, -1); | ||
| + | for(i = 1; i <= n; i++) | ||
| + | { | ||
| + | printf("%lld ", sc[i]); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
2020-2021/teams/namespace/2020洛谷多校day1.1589185292.txt.gz · 最后更改: 2020/05/11 16:21 由 great_designer
