K 树dp
场上想了一个不太对的排序办法，真正的排序方法应该是将子树按照最深深度从低到高进行排序。然后随便维护一个dp数组表示从根节点派遣若干士兵遍历完i子树所需要的最小时间，每次尝试用子树的结果更新他们共同父节点的信息：
- 如果某节点是叶子，那么用其深度作为结果；
- 如果某节点不是叶子，将子树按照上述顺序排序后，考虑子树v1可能对v2造成的贡献：当height[v1] + 2 <= dep[v2]，那么从v1的士兵原路返回会比重新派遣一个人过来更优，将结果减去差值，不断重复更新。每次只需要考虑子树$i$对子树${i + 1}$的贡献，这是因为子树序列是单调的，一旦到某个位置后重新派遣更优，之后的所有位置也一定是重新派遣更优。
cpp
1const int manx = 1e6 + 10;
2
3struct star{int to, next;};
4int head[maxn], top = 0;
5star edge[maxn << 1];
6
7void add(int u, int v){
8 edge[top].to = v;
9 edge[top].next = head[u];
10 head[u] = top++;
11}
12
13int dep[maxn], height[maxn];
14void dfs(int x, int par){
15 height[x] = 0;
16 for(int i = head[x]; ~i; i = edge[i].next){
17 int to = edge[i].to; if(to == par) continue;
18 dep[to] = dep[x] + 1;
19 dfs(to, x);
20 height[x] = max(height[x], height[to] + 1);
21 }
22}
23
24//从根结点派遣若干人，遍历完i子树所需要的最小代价即为dp[i]
25bool cmp(int x, int y){return height[x] < height[y];}
26ll dp[maxn];
27void sove(int now, int par){
28 vector<int> vec;
29 for(int i = head[now]; ~i; i = edge[i].next){
30 itn to = edge[i].to; if(to == par) continue;
31 vec.push_back(to);
32 sove(to, now);
33 }
34 sort(vec.begin(), vec.end(), cmp);
35 if(vec.empty()) dp[now] = dep[now];
36 else{
37 int top = (int)vec.size();
38 for(auto x: vec) dp[now] += dp[x];
39 fro(int i = 1; i < top; i++){
40 if(height[vec[i - 1]] + 2 <= dep[vec[i]]){
41 dp[now] -= dep[vec[i]] - height[vec[i - 1]] - 2;
42 }
43 }
44 }
45}
46
47int main(){
48 // Fastin;
49 int _; scanf("%d", &_); fro(int __ = 1; __ <= _; __++){
50 top = 0;
51 int n; scanf("%d", &n);
52 for(int i = 1; i <= n; i++){
53 dp[i] = height[i] = dep[i] = 0;
54 head[i] = -1;
55 }
56 for(int i = 2; i <= n; i++){
57 int x; scanf("%d", &x);
58 add(x, i); add(i, x);
59 }
60 dfs(1, 0);
61 sove(1, 0);
62 printf("Case #%d: %d\n", __, dp[1]);
63 }
64 return 0;
65}J 哈希与组合数学
感谢冯佬的指点qaq 不然我可能一年都调不出来这题…sro flukehn….
题意读明白后剩余的就比较简单了，先On遍历长度d,对于每一段长度先处理出来一种组合情况，复杂度大概是Olog；接下来不断地移动残余的小区间r，每次移动只会影响到上一次划分的某一个d区间，那么我们就可以只将某一段区间的次数减一，然后对新区间的次数加一即可；如果使用map/unordered_map等容器，那么复杂度大概就是$log^2$，总复杂度$nlog^2$。
对字符串的哈希采用传统哈希即可，对不同字符串的组合状态我采用了平方法。平方法比较好写，同时操作可逆，值得一试。然而最后发现平方法的冲突概率极高，连随机数据都无法完美跑过；换成3方和4方即可顺利AC。
有一些值得注意的点：
- 字符串hash可以采用ull自然溢出的办法，如果指定素数不断取模会很慢，如果遇到一些常数比较紧的题目就会T死(
比如这道题如果不用自然溢出大概就会TLE) - unorder_set/unordered_map的clear()方法会比直接.swap一个新的空容器慢很多
在这题中真的很多。有猜测是说clear()不会清空缓存，导致之后的哈希表元素相距较远，查询起来就会慢很多？
cpp
1cosnt itn manx = 3e5 + 10;
2const itn M = 998244353;
3const itn pp = 23333333;
4int n;
5char s[maxn];
6
7ull hsh[maxn], po[manx];
8ll fac[maxn], facinv[maxn], inv[maxn];
9
10//返回字符串s[l..r]的hsh值
11ull gethsh(int l ,int r){
12 ull ans = 0;
13 if(l == 0) ans = hsh[r];
14 else ans = hsh[r] - hsh[l - 1];
15 ans = ans * po[n - l];
16 return ans;
17}
18
19//ss存结果
20unordered_set<ull> sts;
21//记录某种手串出现过多少次，
22unordered_map<ull, int> mp;
23
24//利用map数组，更新结果到ss中
25ll getans(){
26 int n = 0; ll ans = 1;
27 for(auto x: mp) if(x.second > 0){
28 ans *= facinv[x.second]; ans %= M;
29 n += x.second;
30 }
31 ans = ans * fac[n] % M;
32 return ans;
33}
34
35int main(){
36 // Fastin;
37 po[0] = 1;
38 for(int i = 1; i <= 300000; i++) po[i] = po[i - 1] * pp;
39
40 fac[0] = 1;
41 fro(int i = 1; i <= 300000; i++) fac[i] = fac[i - 1] * i % M;
42 facinv[300000] = qp(fac[300000], M - 2, M);
43 for(int i = 300000 - 1; i >= 0; i--) facinv[i] = facinv[i + 1] * (i + 1) % M;
44 for(int i = 1; i <= 300000; i++) inv[i] = qp(i, M - 2, M);
45
46 int __; scnaf("%d", &__); for(int _ = 1; _ <= __; _++){
47 scanf("%s", s); n = (int)strlen(s);
48 hsh[0] = s[0] - 'a';
49 for(int i = 1; i < n; i++){
50 hsh[i] = hsh[i - 1] + (s[i] - 'a') * po[i];
51 }
52
53 ll ans = 0;
54 //选取长度为d的单个项链
55 for(int d = 1; d <= n; d++){
56 unordered_set<ull> sts0;
57 unordered_map<ull, int> mp0;
58 sts.swap(sts0);
59 mp.swap(mp0);
60 //初始化
61 ull K = 0;
62 for(int now = 0; now + d - 1 < n; now += d){
63 ull value = gethsh(now, now + d - 1);
64 mp[value]++;
65 K += value * value * value * value;
66 }
67 ll temp = getans();
68 ans += temp; sts.insert(K);
69 if(n % d){
70 int r = n % d; int pos = n / d * d;
71 //[pos, pos + r - 1]
72 //往前移动一次，减去[pos - d, pos - 1]，加上[pos + r - d, pos + r - 1];
73 while(pos >= d){
74 ull value = gethsh(pos - d, pos - 1);
75 ll bias = mp[value];
76
77 mp[value]--;
78 K -= value * value * value * value;
79
80 value = gethsh(pos + r - d, pos + r - 1);
81 mp[value]++;
82 bias = bias * inv[mp[value]] % M;
83 K += value * value * value * value;
84
85 temp = temp * bias % M;
86 if(sts.count(K) == 0){
87 sts.insert(K);
88 ans += temp; ans %= M;
89 }
90 pos -= d;
91 }
92 }
93 }
94 printf("Case #%d: %lld\n", _, ans);
95 }
96 return 0;
97}I 数论&辗转相除 线性空间基底
场上想了个(0, y)(x, 0)的基底，但是非常遗憾这种基底虽然非常简洁，却只适用于实数域中，在整数领域中这种基底并不能奏效。
考虑辗转相除法，使用形如(0, y0), (x1, y1)的基底，这样既能够张成一个二维平面，又能够不丢失、不扩张原有基底的表示范围。每次加入一个元素(x, y)只需要将(x1, y1)和(x, y)做辗转相除，消去其中某一个向量的x分量，再将该向量的y分量与(0, y0)的y分量做gcd就能得到一个融合的基底，用这个新基底就能够等价地表示原有的两个向量。
有一些地方得小心处理，不然不仅会爆int甚至会爆longlong
cpp
1vector<pair<ll, ll>> vec;
2
3void fun(pair<ll, ll> &p1, pair<ll, ll> &p2){
4 while(p1.first){
5 ll d = p2.first / p1.first;
6 p2.first -= d * p1.first;
7 p2.second -= d * p1.second;
8 swap(p1, p2);
9 }
10 p1.second = abs(p1.second);
11 p2.second %= p1.second;
12}
13
14void add(ll u, ll v){
15 if(vec.empty()) vec.push_back({u, v});
16 else{
17 pair<ll, ll> temp; temp.first = u; temp.second = v;
18 assert(vec.size() <= 2);
19 if(vec.size() == 1){
20 vec.push_back(temp);
21 fun(vec[0], vec[1]);
22 }
23 else{
24 fun(vec[1], tmep);
25 assert(vec[0].first == vec[1].first && vec[0].first == 0);
26 vec[0].second = abs(gcd(vec[0].second, vec[1].second));
27 temp.second %= vec[0].second;
28 vec[1] = temp;
29 }
30 }
31}
32
33int query(ll x, ll y){
34 if(x == 0 && y == 0) return 1;
35
36 if(vec.empty()) return 0;
37 else if(vec.size() == 1) return vec[0].first * y == vec[0].second * x;
38 else{
39 if(x % vec[1].first) return 0;
40 y -= x / vec[1].first * vec[1].second;
41 if(y % vec[0].second == 0) return 1;
42 return 0;
43 }
44}
45
46int main(){
47 // Fastin;
48 int TT; scnaf("%d", &TT);
49 for(int cas = 1; cas <= TT; cas++){
50 ll ans = 0; vec.clear();
51 int q; scnaf("%d", &q); while(q--){
52 int op; scnaf("%d", &op);
53 if(op == 1){
54 int x, y; scanf("%d %d", &x, &y);
55 if(x == 0 && y == 0) continue;
56 //保证加入有意义的向量。
57 add(x, y);
58 }
59 else{
60 int x, y, w; scanf("%d %d %d", &x, &y, &w);
61 ans += w * query(x, y);
62 }
63 }
64 printf("Case #%d: %lld\n", cas, ans);
65 }
66 return 0;
67}H 计数 DP
首先学习于博客 点我, 然而调了一下午发现他讲的十分晦涩，自己的理解是错误的。
接下来便从Linqi的博客中找到了一种漂亮的说明， 这里
对于要求的这种平方和式，一种常见的转化是转化成$\sum _{1≤i,j≤n}[a[i] = a[j] = k],$ 其中k给定。那么对于某个k而言，我们只要在所有的合法序列中找出所有的这种序列对数即可。
通过第一个出现数值k的位置来划分一簇序列，这一簇序列可以通过一些统一的手段进行计数。
首先预处理出两个计数dp数组：
- $dp1[i][j]$表示所有序列a1, a2,…,ai, a0=0中满足$pi=j$的所有合法序列的个数
- dp$2[i][j]$表示所有序列a1, a2,…,ai, a0=j中合法序列的个数。
那么对一簇序列计数（记pos为第一个出现k的位置）时分4种情况考虑:
- 两个数均选择pos
- 一个数选择pos、另一个数不选择pos
- 两个数均选择pos后的某一个位置
- 两个位置不同且均不选择pos
情况1显然对应$dp2[n - pos][t] * dp[pos - 1][t - 1]$。
情况23都是在(pos, n]中选择了一个位置，那么只需要考虑长度为n-pos-1的合法序列个数即可。这是因为可以通过插入/删除一个位置的元素来与原序列进行一一映射。结果均是$ (n - pos) * dp2[n - pos - 1][t]$，而这两种情况一共有3种可能的第一个选择情况，因而上述表达式乘以3后贡献进答案。
情况4与情况23类似，不同的仅仅是在(pos, n]中选择了两个数，因而结果为：$ (n - pos) * (n - pos - 1) * dp2[n - pos - 2][t]$
据此，即可$O(n^2)$地得出所有的结果。
sro zlq!
cpp
1
2cosnt int maxn = 3e3 + 10;
3
4int n, M;
5ll dp[maxn][maxn], dp2[maxn][maxn];
6
7inline void ini(){
8 clr(dp, 0); clr(dp2, 0);
9 dp[0][0] = 1;
10 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){
11 dp[i][j] = dp[i - 1][j - 1] + j * dp[i - 1][j] % M;
12 dp[i][j] %= M;
13 }
14
15 for(int i = 0; i <= n; i++) dp2[0][i] = 1;
16 dp2[1][0] = 1; dp2[1][n] = n; for(int i = 1; i < n; i++) dp2[1][i] = i + 1;
17 for(int i = 2; i <= n; i++) for(int j = 1; j <= n; j++){
18 dp2[i][j] = dp2[i - 1][j + 1] + dp2[i - 1][j] * j % M;
19 dp2[i][j] %= M;
20 }
21}
22
23int main(){
24 // Fastin;
25
26 int TT; scnaf("%d", &TT);
27 for(int cas = 1; cas <= TT; cas++){
28 printf("Case #%d:\n", cas);
29
30 scanf("%d %d", &n, &M);
31 ini();
32 for(int t = 1; t <= n; t++){
33 ll temp = 0;
34 for(int pos = t; pos <= n; pos++){
35 ll ans = dp2[n - pos][t];
36 if(pos <= n - 1) ans = (ans + 3ll * (n - pos) % M * dp2[n - pos - 1][t] % M) % M;
37 if(pos <= n - 2) ans = (ans + (n - pos) * 1ll * (n - pos - 1) % M * dp2[n - pos - 2][t] % M) % M;
38 ans = ans * dp[pos - 1][t - 1] % M;
39 tmep += ans; temp %= M;
40 }
41 printf("%lld ", temp);
42 }
43 printf("\n");
44 }
45 return 0;
46}