Atcoder abc235

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
G(容斥,组合数)Ex(并查集,图论,DP,树上DP)

https://atcoder.jp/contests/abc235/tasks

G - Gardens

A个种子1

B个种子2

C个种子3

N个花园

要满足条件, 任何花园都有种种子

每个花园每种的个数[0,1]

不需要把所有都种植

求方案数mod 998244353

范围

n 5e6

3s

1024mb

我的思路

R(i,j) 表示,i个花园,种完其中j个花园的方案数

T(n) 表示,n个花园,恰好种满这n个花园的方案数, T(n) = R(n,n)

ans = T(n)

S(n) = R(n,n) + R(n,n-1) + R(n,n-2) + … + R(n,0);

S(n) = R(n,n) * binom(n,n) + R(n-1,n-1) * binom(n,n-1) + .. + R(0,0) * binom(n,0)

S(n) = T(n) * binom(n,n) + T(n-1) * binom(n,n-1) + .. + T(0) * binom(n,0)

S(n) 很容易算, 相当于A,B,C互不影响, = prod (sum binom(n,0..X)), X=A,B,C, 问题是这个依赖于n需要O(n),

如果能反过来得到T(n) 就好了

T(n) = S(n) - (T(n-1) * binom(n,n-1) + … + T(0) * binom(n,0))

T(n)/n! = S(n)/n! - sum T(i)/i!/(n-i)!

考虑花园状态只有2^3-1=7 种,那么就是 七种中,总个数小于a,b,c的

生成方程?

$\sum \lbrack pwr_x\le a,pwr_y\le b,pwr_z\le c \rbrack ((1+x)(1+y)(1+z)-1)^n$

$= \sum_{i\in[0, n],i_x\le a,,i_y\le b,i_z\le c} (-1)^{n-i} \binom{n}{i} \binom{i}{i_x}\binom{i}{i_y}\binom{i}{i_z} $

$= \sum_{i\in[0, n],i_x\le a,,i_y\le b,i_z\le c} (-1)^{n-i} \binom{n}{i} \binom{i}{min(i,i_x)}\binom{i}{min(i,i_y)}\binom{i}{min(i,i_z)} $

并没法算

再就是, 假设 a<=b<=c

ans(a,b,c) 通过 ans(b,b,b) 让每次头-1,或者尾+1,多次得到

去考虑之间的变化

题解

看来我容斥原理完全不会了, 题目是容斥得到了 我通过生成方程得到的表达式

然后 也是, 如果暴力, 枚举i,总的是O(n^2) 时间

$f(M,N) = \sum_{i=0}^{min(N,M)} \binom{N}{i}$

哦 我好蠢, 这相当于M取值只会是a,b,c, 所以针对性的 只有N变化!!

因此可以O(1)算出 $f(M,N+1) = \sum_{i=0}^{min(N+1,M)} \binom{N+1}{i}$

对于$N\le M$显然 $ f(M,N) = 2^N$

直接定义无效的binom=0

考虑sum(i,0..X) 到 sum(i+1,0..X)的增量

grid

显然$f(M,N) = 2f(M,N-1) + binom{N,M}$

代码

https://atcoder.jp/contests/abc235/submissions/34663174

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;} // read

mint fac[5000010] = {1};
mint ifac[5000010] = {1};
int a[3];
mint binom(int n,int m){
  if(n < 0 || m > n) return 0;
  return fac[n]*ifac[m]*ifac[n-m];
}

int main(){
  int n = read();
  rep(i,0,3) a[i] = read();
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  ifac[n] = fac[n].inv();
  per(i,0,n) ifac[i]=ifac[i+1]*(i+1);

  mint f[] = {1,1,1};
  mint sgn = n%2?-1:1;
  mint ans = 0;
  rep(i,0,n+1){
    ans += binom(n, i) * f[0] * f[1] * f[2] * sgn;
    rep(j,0,3) f[j] = f[j]*2 - binom(i,a[j]);
    sgn = -sgn;
  }
  printf("%d\n",ans.val());
  return 0;
}

Ex - Enumerate Pairs

n点m边无向有边权图,

初始所有点黑色,你可以做最多k次操作

每次操作: 任选点v和数x, 把所有从v出发只经过<=x的边可达的所有点染红

问最终染红的点的集合 有多少种集合, mod 998244353

范围

n 1e5

m 1e5

k 500

ci [1,1e9]

3s

1024mb

我的思路

显然x更大的时候, 如果u,v不能连通,那么更小的时候也不能联通

因此联通关系随着x变大, 相当于并查集合并的感觉

考虑把每个点变成叶子,当距离为0时,就是每个节点单独成

然后把边排序,从小到大做合并, 最多n-1次, 因为每合并一次个数-1

问题是这样每个里面点数也是O(n) 整体要n^2空间

考虑直接用树来表示

为了 A,B,C 在达到某个长度x时,合成了一起

所以树上的根节点还要记录合并时的长度

这样问题变成了, 有一个2n量级节点的树, 每次选一个节点,染色它的所有子节点, 问叶子节点被染色的集合的方案数, 一共k次操作

树问题, 变成树上dp?

f(u,t) = 节点u以及它的子节点 操作k次后的集合状态

染u则 1种

不染u则 需要计算不全染的方案数, 子节点数 > t 考虑乘积组合, 子节点数<=t, 则乘积组合后再减去1

dp[i][j] = ,前i个节点, 染了j次的方案数

`dp[i][j] = sum dp[i-1][l=0..j] * f(p[i],j-l)

感觉复杂度炸了

题解

一样的, 建树, 然后树上DP

注意到这里并没说是连通图, 所以是建森林然后DP, 树内和森林dp都是同样的dp转移式

就直接暴力就好了

证明复杂度不是nk^2,而是nk

考虑连接两个联通块, 它们各自的节点数

  1. 节点数都多于K个, 这样最多O(N/K)次, N/K * K ^2 = NK
  2. 节点数都少于K个, 这样把所有少于k个的操作代价累计, 在它们首次>k的时候进行贡献统计, 那么累计的代价是k^2(每个点和其它点最多发生一次计算,而直接对半就是k^2), 产生>k的个数是O(N/K)次, N/K * K ^2 = NK
  3. 如果一个多于k,一个少于k, 那么每个代价为small * k, 而所有small的和O(N),(因为每次发生后small的点讲不再是这种small x large的情况,所以每个点最多属于一次small),所以总的是O(NK)

因此总的复杂度是O(NK).

这题解上的没看懂,看的snuke的博客看懂了, 感谢snuke的博客和google翻译

代码

https://atcoder.jp/contests/abc235/submissions/34665160

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
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/dsu>
using mint = atcoder::modint998244353;
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

int k;
vector<vector<int>> to; // to[树的节点] = vector<叶子节点>
vector<mint> merge(const vector<mint>& d, const vector<mint>& e) { // 就暴力merge, 卷积
  vector<mint> dp(d.size() + e.size() - 1);
  rep(i,0,d.size())rep(j,0,e.size()) dp[i+j] += d[i]*e[j];
  if ((int)dp.size() > k+1) dp.resize(k+1);
  return dp;
};

vector<mint> dfs (int v) { // 树节点v
  vector<mint> dp = {1,0}; // dp[i]:  <=i-1次不行,i次才行的染色集合方案数, 可以写成{1,0}后面需要加 if(dp.size() == 1) dp.resize(2);,这里丢个0, 省去resize
  for (int u : to[v]) dp = merge(dfs(u),dp);
  int c = to[v].size(); // 子节点个数
  if (c != 0 && c < (int)dp.size()) dp[c] -= 1; // 每个子节点选一次, 全部染色的情况
  dp[1] += 1; // 直接染v
  return dp;
};

int top[100010]; // top[并查集根] = to上树的节点

int main() {
  int n = read();
  int m = read();
  k = read();
  map<int,vector<pair<int,int> >> mp;
  rep(i,0,m) {
    int a = read()-1;
    int b = read()-1;
    int c = read();
    mp[c].push_back({a,b});
  }
  to.resize(n);
  iota(top,top+n,0); // 初始每个根是自己 top[i] = i
  vector<bool> root(n,true); // 是否是树上目前的根节点

  // 建树
  atcoder::dsu t(n); // 并查集
  for (auto [_,es] : mp) { // 边从小到大
    set<int> st; // 哪些根是这轮合并的
    for (auto [a,b] : es) {
      a = t.leader(a); // 并查集根
      b = t.leader(b);
      if (a == b) continue;
      t.merge(a,b); // 合并 并查集
      st.insert(a);
      st.insert(b);
    }
    for (int v : st) if(v == t.leader(v)){ // 找到每组内部的根
      root[top[v]] = false; // top[v] 不再是根
      to.push_back(vector<int>(1,top[v])); // 新节点[] -> 树上叶子节点
      root.push_back(true); // root[to.size()-1] = true, 和to的sz一致
      top[v] = to.size()-1; // v的目前对应树上节点
    }
    for (int v : st) if(v != t.leader(v)){ // 非根的部分
      int p = t.leader(v); // p 是并查集跟
      root[top[v]] = false; // v不再是树根
      to[top[p]].push_back(top[v]); // 树节点指向vector<子节点>
    }
  }
  // dp on tree
  vector<mint> dp = {1};
  rep(i,0,root.size()) if (root[i]) dp = merge(dp,dfs(i));
  mint ans;
  rep(i,0,dp.size()) ans += dp[i];
  printf("%d\n",ans.val());
  return 0;
}

总结

G

组合数, 虽然看起来 = sum binom(i,0..min(a,i)), 是上面不动,下面动, 但实际上把下面提出来,以及定义无效的binom=0, 就变成了只于上面有关的binom和了,且可递推

有道理, 在公式上推半天,不如在二维平面看binom 推得很显然

Ex

好消息是 竟然 想了主要的内容,虽然可能这评分不太准,

但是树上dp不了解这个复杂度

又学了一下树上 dp, 做子节点乘积的复杂度分析.., 感觉之前有树上启发式合并,是按照重轻链来分类讨论,这个是按照子树节点数的重轻来讨论

虽然日常手写dsu,也是学了一下atcoder的dsu库

参考

官方题解

日文 snuke 树上dp复杂度计算