2020-ccpc-qinhuangdao

 2020.10.28 19:23  2023.09.01 18:14  ACM  树dp  字符串哈希  组合计数  线性基底  辗转相除  计数DP 󰈭 3235字

K 树dp

场上想了一个不太对的排序办法，真正的排序方法应该是将子树按照最深深度从低到高进行排序。然后随便维护一个dp数组表示从根节点派遣若干士兵遍历完i子树所需要的最小时间，每次尝试用子树的结果更新他们共同父节点的信息：

如果某节点是叶子，那么用其深度作为结果；
如果某节点不是叶子，将子树按照上述顺序排序后，考虑子树v1可能对v2造成的贡献：当height[v1] + 2 <= dep[v2]，那么从v1的士兵原路返回会比重新派遣一个人过来更优，将结果减去差值，不断重复更新。每次只需要考虑子树$i$对子树${i + 1}$的贡献，这是因为子树序列是单调的，一旦到某个位置后重新派遣更优，之后的所有位置也一定是重新派遣更优。

 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()不会清空缓存，导致之后的哈希表元素相距较远，查询起来就会慢很多？

 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~~

 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!~~

 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}

2020-ccpc-qinhuangdao

K 树dp

J 哈希与组合数学

I 数论&辗转相除 线性空间基底

H 计数 DP

I 数论&辗转相除线性空间基底