Codeforces Global Round 5

發表於 更新於 分類於 ， Disqus： 文章字數： 627 所需閱讀時間 ≈ 2 分鐘
E (bitdp)

原题链接

tourist出的题！

大意

二叉查找树 节点有n个且

倒数第二层满节点

每个节点和左儿子 奇偶相反

每个节点和右儿子 奇偶相同

的方案数

结果mod 998244353

数据范围

1<=n<=1'000'000

3s

512MB

题解

塞内没看到sum of depths做了个假题

第一个思路直接 树上dp, dp[cnt][height][oddoreven] 表示总节点cnt,高度height的,root奇偶性为oddoreven的 方案数

然后dp表达式

1
2
3
4
5
6
7
8
dp[cnt][height][root is odd?] = 

sum{
  dp[left cnt][height -1/-2][root is odd ^ 1] *
  dp[cnt-1-left cnt][height -1/-2][even] *
}

其中注意保证性质

调完bug的代码TLE 11 见下面

因为一些编写过程的推理问题，遗留的height,其实当cnt确定，根据题目的要求，height也就唯一了，算是多设计的

因为每次计算时 计算的子来源大概有 cnt/2左右个

代码

TLE 11

代码

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
// 1 -> 3 -> 7(C(4,4)) -> 15 -> 31 -> ...
// 4(C 4,1) 5(C 4,2)
 
//    ji
// ou     ji
//ji     ou      ou  ji
//ou ji ji ou  ji ou ou ji
 
 
// dp[cnt][height][ji/ou]
 
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
 
ll dp[1000010][22][2];
 
int v2h(int v){
  int ret = 0;
  while(v){
    ret++;
    v>>=1;
  }
  return ret;
}
 
int h2v(int v){
  return (1<<v)-1;
}
 
ll dfs(int cnt,int height,int jiou,int dep=0){
  // rep(i,0,dep){
  //   printf("\t");
  // }
  // printf("call dfs(%d,%d,%d)\n",cnt,height,jiou);
 
  ll &ret = dp[cnt][height][jiou];
  if(ret != -1)return ret;
  if(height == 1){
    return ret = (cnt == 1 && jiou == 1);
  }
  if(height == 0){
    return ret = (cnt == 0);
  }
  if(cnt > h2v(height) || cnt <= h2v(height-1))return ret = 0;
  ret = 0;
  int r = h2v(height-1);
  int l = cnt-1-r;
 
  rep(i,l,r+1){
    if(i%2 == jiou)continue;
    int hl = v2h(i);
    int hr = v2h(cnt-1-i);
    if(hl != height-1){
      if(hl != height-2 || hl > 1)continue;
    }
    if(hr != height-1){
      if(hr != height-2 || hr > 1)continue;
    }
    if(!(hr == height -1 || hl == height -1))continue;
 
    ll lcnt = dfs(i,hl,jiou^1,dep+1);
    ll rcnt = dfs(cnt-i-1,hr,0,dep+1);
 
    // rep(i,0,dep){
    //   printf("\t");
    // }
    // printf("dfs(%d,%d,%d) %d-1-%d : {l * r}={%lld * %lld}\n",cnt,height,jiou,i,cnt-1-i,lcnt,rcnt);
    (ret+=lcnt*rcnt)%=MOD;
  }
  // rep(i,0,dep){
  //   printf("\t");
  // }
  // printf("ret dfs(%d,%d,%d)=%lld\n",cnt,height,jiou,ret);
  return ret;
}
 
int main(){
  int n;
  cin>>n;
  int h = v2h(n);
  rep(i,0,1000001){
    rep(j,0,22){
      rep(k,0,2){
        dp[i][j][k] = -1;
      }
    }
  }
  cout<<(dfs(n,h,0)+dfs(n,h,1))%MOD<<endl;
  return 0;
}

果然tle了

AC代码 … TODO