Educational Codeforces Round 118

發表於 更新於 分類於 ， Disqus： 文章字數： 701 所需閱讀時間 ≈ 2 分鐘
F(生成函数)

CF tracker

Edu List

https://codeforces.com/contest/1613

F. Tree Coloring

根1的n点树

给点上排列色ci = 1~n (每个颜色出现且仅出现一次)

p[i]=i的父节点

如果所有点满足c[i] != c[p[i]] -1, 则认为美丽

问有多少种美丽的染色方案mod 998244353

范围

n 250000

4.5s

512mb

我的思路

也就是 每个点的颜色不能正好比父节点小1

一般来说, 树的兄弟之间没有关系, 但是这里 如果一个非法的子树, 和兄弟的子树, 值进行穿插, 这有可能变得合法

例如

1
2
3
  root
2     2
1     1
1
2
3
  root
3     4
1     2

一个方向就是去考虑容斥, 把边作为属性, 拥有属性表示边连的两个点相邻

有指定属性连接在一起的点, 在子树之间 做穿插时就不能拆开了,

而注意到当子树穿插时, 只与有几个可穿插的有关

考虑f[u][c] = 节点u的子树中, 可连可不连的自由节点个数为c时的方案数

先不考虑根, v1 和 v2 之间的穿插

[c1 + c2] = sum f[u][c1] * f[u][c2] * binom(c1+c2,c1)

[c1 + c2]/(c1+c2)! = sum f[u][c1]/c1! * f[u][c2]/c2!

看起来就是ntt

最后考虑根u

f[u][c1+c2+...] = [c1+c2+...]*count(child), 直接放(某个子树的最大+1) 且指定边不可移动

f[u][c1+c2+...+1] = [c1+c2+...]*(c1+c2+...+1), 放任意地方(包括 最大+1), 但不指定边

f[u][c] = (count child)[c] + [c-1]*c

变形 f[u][c]/c! = (count child)[c]/c! + [c-1]/(c-1)!

那么就是 g[u] = (c+x) g(v0) g(v1) g(v2) ...

g(leaf) = x

ans = sum f[1][c]*c!

但是看起来暴力算感觉会tle

仔细一看表达式 原来是 f[1] = (c1+x)(c2+x) * x^叶子

代码

https://codeforces.com/contest/1613/submission/190710914

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
// ---------- template end ----------
using mint = CMM::modint;

using namespace std;
typedef long long ll;
typedef long long i64;
#define rep(i,a,n) for(i64 i=(a);i<(i64)(n);i++)
#define per(i,a,n) for(i64 i=(n);i-->(i64)(a);)

i64 read(){i64 r;scanf("%lld",&r);return r;}
const int N=250000;
vector<int> g[N+10];
mint fac[N+10]={1};
mint ifac[N+10];

int main(){
  int n=read();
  rep(i,1,n){
    int u=read()-1;
    int v=read()-1;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  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);
  vector<vector<mint> > exps;
  exps.push_back({g[0].size(),1}); // (child + x)
  rep(i,1,n) exps.push_back({g[i].size()-1,1}); // (child + x)
  while((int)exps.size() > 1){
    rep(i,0,exps.size()/2) exps[i] = CMM::NTT::convolution(exps[i*2],exps[i*2+1]);
    if(exps.size()%2) exps[exps.size()/2] = exps.back();
    exps.resize((exps.size()+1)/2);
  }
  mint ans=0;
  rep(i,1,n+1) ans+=exps[0][i]*fac[i]*((n-i)%2==0?1:-1);
  printf("%d\n",ans.val());
  return 0;
}

总结

F. 又一次 自己做出了F, 看来生成函数的入门题 ,只要会了还是很容易的

参考

官方