Atcoder arc140

發表於 更新於 分類於 ， Disqus： 文章字數： 950 所需閱讀時間 ≈ 3 分鐘
D(树的边与点,贡献统计,DP,特殊题目条件)

题目

https://atcoder.jp/contests/arc140/tasks/arc140_d

初始有 n 个点，给定一个长度为 n 的数组 ai，若 ai≠−1，则有无向边 (i,ai)，若 ai=−1，则点 i 可以连向 1∼n 任意点，求所有图的联通块个数之和

n 2e3

答案mod 998244353

题解

考虑G中一个联通分量

如果它有N点,N个边,那么它恰好有一个环

这关键就在题目的特殊性上,因为(i->ai),即每个点连出一条边,所以n个点组成的联通分量一定恰好N个边, 题目条件特点!

因此 题目变成统计环的 而不是统计联通分量

然后先考虑 非-1的部分已经构成的环, 这部分如果再和其它相连,那么额外连的部分一定不会再有环,是个树,所以其它和它连的部分一定不会再贡献,

所以在考虑-1构成环的话不会考虑已经初始有环的联通分量

对于目前剩余没有环的联通分量是树,把这些树标号从1到k,并且b[i]表示这些树的点的个数, 注意到它一定只有一条未连接的边

现在考虑一个环的构成, 一定是由一些树连成的

树1->树2->树3->树k->树1

我们不考虑没有参与到环中的其它树,即使它从联通分量角度连进来了, 我们之考虑对环的构成直接有贡献的树

那么 如果是由 k个构成的,每一个的树的出点是固定的,但是入点的选择是上一个树的点的个数, 而它们排成环的方案是(k-1)!

所以环的构成是$(k-1)! \times \prod_{i=1}^{k} B_{x_i}$

n 很小 n方 可以接受可以DP

说是分治计算$\prod_{i=1}^{K} (1 + B_ix)$可以做到 n log(n)

代码

https://atcoder.jp/contests/arc140/submissions/31923069

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#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

int n;
int a[2010];// 读入
int fa[2010]; // 并查集父节点
int sz[2010]; // 点个数
bool cir[2010]; // 是否有环

int getfa(int x){
  return x == fa[x]?x:(fa[x] = getfa(fa[x]));
}

void link(int u,int v){
  int fu = getfa(u);
  int fv = getfa(v);
  if(fu == fv){
    cir[fu] = true; // 有环
    return;
  }
  sz[fv] += sz[fu]; // 大小
  cir[fv] |= cir[fu]; // 环
  fa[fu] = fv;
}

ll mypow(ll v,int pwr){
  ll r = 1;
  while(pwr){
    if(pwr%2)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}
ll fac[2010] = {1}; // 阶乘

int main(){
  cin>>n;
  int freecnt = 0; // 自由度 -1 个数
  rep(i,1,n+1){
    fa[i] = i;
    sz[i] = 1;
    fac[i] = fac[i-1]*i%MOD;
    scanf("%d",a+i);
    freecnt += a[i] == -1;
  }
  rep(i,1,n+1){
    if(a[i] == -1)continue;
    link(i,a[i]);
  }
  vector<int> arr ;
  int circnt = 0;
  rep(i,1,n+1){
    if(fa[i] != i)continue; // 非联通块根
    if(cir[i]){ // 环
      circnt++;
      continue;
    }
    arr.push_back(sz[i]); // 树 有一个自由度
  }
  ll ans = circnt * mypow(n,freecnt) % MOD; // 本身就是环的贡献
  vector<ll> mulsum(n+10,0); // dp mulsum[树的个数] = sz乘积和
  mulsum[0] = 1;
  rep(i,0,(int)arr.size()){
    rep(k,0,i+1){
      // 注意前面一半只是 k+1个构成环的方案数, 对于环以外的 freecnt-k-1的自由度任意搭配 才是这些环对总答案的贡献值
      (ans += fac[k] * mulsum[k] % MOD * arr[i] % MOD * mypow(n,freecnt-k-1) % MOD)%=MOD;
    }
    per(k,0,i+1){
      (mulsum[k+1] += mulsum[k]*arr[i])%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

总结

我想了很久,都没有注意到题目条件特殊性带给联通分量的特殊性, 这还是不应该,应该加强这方面的反应

其实也算是树的知识没有警醒我, 边=点-1,那么就会反应到这里连通分量的边 <= 点 且 >= 点-1

参考

官方