Educational Codeforces Round 132

發表於 更新於 分類於 ， Disqus： 文章字數： 2.5k 所需閱讀時間 ≈ 8 分鐘
E(树,xor,贪心,树上启发式合并)F(DP,NTT,前缀和)

E

https://codeforces.com/contest/1709/problem/E

给你个一个树, 每个点上有值, 修改尽量少的点为任意值

让任何简单路径的 xor都不为零

范围

n 2e5

ai [1,2^30]

3s

256MB

题解

我的思路

显然啊, 类似树上差分的思想, a…b xor = 0

意味着 a…root ^ root …b = 0

所以直接变成 计算每个数到根的xor

然后问题变成, 任意两个相同值之间的连线, 需要至少选一个点

或者说, 需要xor树最终两两不等

不知道往后怎么搞

一个思路是dp

但是 遇到同值点不是 祖先关系,而是分叉的关系 ,也不知打怎么记录

题解

虽然的确有前缀意义,但其实 我想的总思路没问题, 但是细节有问题

并不是简单路径 = 到根的 路径 xor

因为它们的lca 被算了两次

所以其实是 path[u]^path[v] = a[lca[u,v]]

那么 对于一个点x = lca(u,v) , 且 u..v 的xor = 0

那么 (x,y) 上至少有一点需要改变

然后 我们对所有的有这种情况的x 按深度从深到浅考虑

找深度最深的x, 那么修改 x的方案不会比修改 u…v 的更差

因为是最深的, 所以其它满足的链 如果经过它的子树 则必定经过它,因为它需要修改, 所以而至少一个, 而对于其它经过它的链来说是至多一个

dfs(u){
对于u的所有子树 dfs(v)

每个点获取 从根到它的子节点 能得到的 xor 集合

一旦有来自两个子树 中有值 xor == u 那么u就必然被选
而被选的u对于它的父节点的返回是 空集合
未被选的u对于它的父节点的返回是它所有子集合可达值 xor 它自身
}

怎么看都是n^2 啊 , 为啥 O(nlog^2 n)

因为虽然dfs一次就可以把所有点到根的xor 算完

但是每次做 set 的合并时, 一个点就是会在它的 父节点 中被运算

那每个点被参与比较的次数可以达到 链的长度 不就是 n^2 吗

然后神奇的是 这个启发式合并的复杂度不是n方

启发式合并(DSU on Tree)

oi-wiki 树上启发式合并

重儿子, 儿子节点子节点个数最多的

重边, 当前点连向其中一个重儿子的边

轻边 非重边

根到任意点 轻边不超过log n 条

反证法, 如果大于log n 条,

则最深的轻边的根至少还额外连了一个点大小为1的子树

第二深的轻边的根至少还额外连了一个点大小为3的子树

第三深的轻边的根至少还额外连了一个点大小为7的子树

…

第m深的轻边的根至少还额外连了一个点大小为2^m-1的子树

显然 m > log n , 则 2^m - 1 > n - 1 >= n

性质得证

那么每个节点 只有在它的某个祖先u的视角, 它是u的轻边的那一部分时, 才会作为被遍历的

所以每个节点的被遍历次数 = 它到根的 轻边数

所以 O(n log n)

代码

https://codeforces.com/contest/1709/submission/165472602

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N = 200000;
int ans=0;
int a[N+10]; // read
int p[N+10]; // 当前每个节点对应st节点下标 pos[u]
vector<int> e[N+10]; // edge
set<int> st[N+10]; // st[顶点] = {链到根的xor集合}

void dfs(int u,int f, int x) {
  int &iu = p[u]; // 真的u
  int bu = x^a[u]; // 从根下来的xor 链
  st[iu].insert(bu);
  bool delu = false; // delete u
  for(auto v:e[u]) if(v != f){
    dfs(v,u,bu);
    int &iv = p[v];
    // 把小的向大的合并, 结果存在st[iu] 中
    if(st[iu].size() < st[iv].size()) swap(iu, iv);
    for(auto val:st[iv]){
      if(delu) break;
      if(st[iu].count(val ^ a[u])) delu = true;
    }
    if(!delu) for(auto val:st[iv]) st[iu].insert(val);
    st[iv] = {};
  }
  if(delu){
    st[iu] = {};
    ans++;
  }
}

int main() {
  int n = read();
  rep(i,1,n+1) {
    a[i] = read();
    p[i] = i;
  }
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }
  dfs(1,0,0);
  printf("%d\n",ans);
}

F

题目

https://codeforces.com/contest/1709/problem/F

读入 n, k ,f

包含长度等于n的字符串 的可重集合 beautiful 定义为

对于长度 [1,n] 之间任意字符串s, c[s] >= 集合中以s为前缀的字符串个数

任务 对于[1,n] 的所有字符串s, 你需要计算有多少 中映射c[s] 的选择方式

max(beautiful的集合的元素个数 )= f

其中 0 <= c[s] <= k

范围

n 15

k,f 2e5

6s

512ms

题解

我的思路

显然关于前缀

如果 s0 是 s1的前缀

那么显然 s0 出现的次数 >= s1 出现的次数

那么 如果 c[s0] <= c[s1] , c[s1] 就没什么作用

反过来, 如果 c[s0] >= sum c[s0的所有下一级后缀], 那么c[s0] 也不是紧限制

因此 真正有效的内容是

c[s1] <= c[s0] ,c[s0] <= sum c[s0的所有下一级后缀],

而这样约束以后, 方案数 就 = c[0] + c[1], 因为每个都表示能达到的最大个数

问题来了, 这样如何 算原始的c呢

题解

转化一下题目

高度n的满二叉树

你需要对每个父子之间做最大流量限制,[0,k] 之间整数

让根源, 所有叶子汇, 的最大流恰好 = f

求方案数 % 998244353

对于给定k

a(n,f) = 高度n, 最大恰好f的方案数

考虑状态转移

那么也就是 左边的n-1高度 最大流为v的时候,右边为f-v

但是这个 左边的最大流 可能是被根到左边这个边限制的, 也可能是本身n-1,v 的方案

定义 b(n,f) 等于 高度n 且根上多一个[0,k] 的限制的最大流 = k,方案数

如果是下面子树最大f, 那么对于根上可以选择 f~k, 所以有(k-f+1)a(n,f) 种

如果是下面子树最大 > f, 那么对于根上仅可选择f, 所以有 $\sum_{i=f+1}^{2k} a(n,i) 种

综上$b(n,f) = (k-f+1)a(n,f) + \sum_{i=f+1}^{2k} a(n,i)$ , 前缀和每个状态 均摊O(1) 可算

那么对于a就是最开始的转移

$a(n,f) = \sum_{i=0}^f b(n-1,i)\cdot b(n-1,f-i)$, 卷积, 需要FFT或者NTT就可以搞

那么答案 = $a(n,f)$, 也说明 $f > 2k$ 无解

最后边界处理, $b(n,f) = 0, f > k$

关于实现, 似乎直接NTT c++17会被卡, 可能要c++20

因为这里 相当于 是$a[n] = b[n-1]^2$, 所以平方可以少算一次NTT

然后 注意计算前把 末尾0删了, 不然可能长度倍增

以及我本地测 带了-fsanitize的编译, c++17/20 都4.5s, 而不带的都是1s

代码

https://codeforces.com/contest/1709/submission/165613575

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

// ------------------------------- NTT --------------------------------
namespace NTT998{
  const int MOD = 998244353; // 7*17*2^23 + 1
  const int MAXPWR = 22; // 随着MOD改变, 2的幂次, 对应复平面单位向量的N = 2 && MAXPWR;
  const int g = 3;// 原根 随着MOD改变
  const int invg = 332748118;// 原根模逆元 随着MOD 和 g 改变

  // bit 翻转
  int rev(int x, int len) {
    int ans = 0;
    while(len -- ){
      ans <<= 1;
      ans |= x & 1;
      x >>= 1;
    }
    return ans;
  }

  inline int getlog2(int n){ return 31 - __builtin_clz(n);}

  ll mypow(ll a, ll k) { //快速幂，a**k
    ll res = 1;
    while (k) {
      if (k & 1) (res *= a) %= MOD;
      (a *= a) %= MOD;
      k >>= 1;
    }
    return res;
  }

  void NTT(vector<ll> &A, int flag = 1 /* 1: NTT, -1: INTT*/ ) {
    int n = A.size();
    if(n == 1) return ;
    // assert((n & (n-1)) == 0); // 2 的幂次
    int lgn = getlog2(n);
    // assert(lgn <= MAXPWR);
    rep(i, 0, n) { // 同FFT
      int j = rev(i, lgn);
      if (j > i) swap(A[i], A[j]);
    }
    rep(pwr,0,lgn){
      int m = 1 << pwr;
      // assert((MOD - 1) % (m<<1) == 0);
      ll gn = mypow(flag == 1 ? g : invg, (MOD - 1) / (m << 1)); // 单位原根g_n
      for (int k = 0; k < n; k += (m<<1)) {
        ll gi = 1;
        rep(j,0,m) {
          auto U = A[k + j];
          auto T = gi * A[k + j + m] % MOD;
          A[k + j] = (U + T) % MOD;
          A[k + j + m] = (U - T + MOD) % MOD;
          (gi *= gn) %= MOD;
        }
      }
    }
    if(flag == -1){ // 内置 / N
      const ll INVSIZE = mypow(n, MOD-2);
      rep(i,0,n) (A[i] *= INVSIZE) %= MOD;
    }
  }

  void INTT(vector<ll> &A){ NTT(A,-1);}

  // 平方 少一次 NTT
  vector<ll> poly_sq(vector<ll> &v0) {
    int sz = v0.size() * 2;
    if(sz == 0)return {};
    sz = 1 << (getlog2(sz) + !!(sz & (sz-1))); // 非2的幂次
    v0.resize(sz,0);
    NTT(v0);
    vector<ll> a2(sz,0);
    rep(i,0,sz) a2[i] = v0[i] * v0[i] % MOD;
    INTT(a2);
    return a2;
  }
}

// ------------------------------- NTT --------------------------------

int n;

vector<ll> a;
vector<ll> b; // 滚动

int main(){
  const int MOD = NTT998::MOD;
  int n = read(); // 15
  int k = read(); // 2e5
  int f = read(); // 2e5
  if(f > 2 * k){
    printf("0\n");
    return 0;
  }
  b = vector<ll>(k+1,1);

  rep(i,1,n+1){
    // a
    a = NTT998::poly_sq(b); // 非平方也会TLE
    if(a.size() <= 2*k+1) a.resize(2*k+1,0);
    vector<ll> prea(2*k+2, 0); // prefix sum of a
    rep(j,0,2*k+1) prea[j+1] = (prea[j] + a[j]) % MOD;

    b = vector<ll>(k+1,0);
    rep(j,0,k+1) b[j] = (k-j+1) * a[j] % MOD + (prea[2*k+1] - prea[j+1]);
    while(!b.empty() && b.back() == 0) b.pop_back(); // 重要, 否则多出来的0 会导致 长度倍增 TLE
  }

  printf("%lld\n", a[f]);
  return 0;
}

总结

E

一个是细节想错, lca多算一次 没想到

另一个是 考虑最深的lca的根 ,而不是考虑端点

这两点都是能想到没想到

然后关键的来了, 就是启发式合并的知识点, 这下学会了又

F

一个是变成树的 “流计算”, 很神奇 我好想 竖着觉得是树 ,横着就没发现了,

一个是学一下NTT, 以及NTT中的平方

参考

官方

NTT