【赛题整理】[NOIonline Round2] C~F题解

依旧是按照个人做题时认为的难度排序…

打比赛的时候严重翻车,比赛经验还是太差劲了啊!

于是这篇文章就变成了游记+翻车实录

题外话

作为苏打绿死忠的我…觉得普及这个 T1 题目背景and题目名称都很赞!

C 涂色游戏

你有 $10^{20}$ 个格子,它们从 $0$ 开始编号,初始时所有格子都还未染色,现在你按如下规则对它们染色:

  1. 编号是 $p_1$ 倍数的格子(包括 $0$ 号格子,下同)染成红色。
  2. 编号是 $p_2$ 倍数的格子染成蓝色。
  3. 编号既是 $p_1$ 倍数又是 $p_2$ 倍数的格子,你可以选择染成红色或者蓝色。

其中 $p_1$ 和 $p_2$ 是给定的整数,若格子编号是 $p_1$ 或 $p_2$ 的倍数则它必须要被染色。在忽略掉所有未染色格子后,你不希望存在 $k$ 个连续的格子颜色相同,因为你认为这种染色方案是无聊的。现在给定 $p_1$, $p_2$, $k$,你想知道是否有一种染色方案不是无聊的。

对于所有测试点:$1 \leq T\leq 10^6$,$1\leq p_1,p_2,k\le 10^9$。

以下是做题时凌乱的内心活动

先开题…嗯,混乱地读了半天题,觉得大概是问是否存在一个 $x$ 和一个 $y$ 使得 $p_1>p_2$ 时

然后发现似乎很难处理编号是 $[p_1,p_2]$ 及其倍数的情况。然后就开始摸。摸了一会儿之后发现几个性质:

1、最多只用考虑 yxyxy 这种分布,即最多算上一个 $x$ 和 $y$ 的公倍数。因为如果存在连续两个 $x$ 和 $y$ 的公倍数之间,没有单独的 $y$ 的倍数,那么就说明 $x|y\cdot t,x|y\cdot (t+1)$,也就证明了 $x|y$ ,而这种情况是显然 Yes 的;

2、大概是每 $\rm lcm$ 一次循环…然后…


然后,读了半天题,才发现读题读反了…这题是要你去 check 是否对于任意一个 $y$ 都存在一个 $x$ 使得

同时也不用考虑 $\rm lcm$ 的问题了,因为遇到 $\rm lcm$ 肯定会涂 $p_1$ 色。所以上式直接换成了拟序。

那么也就是考虑是否满足

其中为什么是 $p_1-1$ 呢?因为不考虑 $\rm lcm$ 时这就是最近的界。但是注意到这个界有点宽,当且仅当 $(p_1,p_2)=1$ 的时候,存在这种最劣的情况,即式子 $bp_2-ap_1=1$ 存在整数解。

然后大概就是个代换,发现同时除以 $(p_1,p_2)$ 之后与原结果是等价的。然后就没了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int gcd(int x, int y){
return !y ? x : gcd(y, x % y) ;
}

int T, n, m, k, g ;

int main(){
cin >> T ;
while (T --){
n = qr(), m = qr(), k = qr() ;
g = gcd(n, m), n /= g, m /= g ;
if (k == 1) { puts("No") ; continue ; }
if ((ll)(k - 1) * min(n, m) < max(n, m) - 1) puts("No") ; else puts("Yes") ;
}
return 0 ;
}

D 建设城市

球球是一位建筑师。一天,他收到市长的任务:建设城市。球球打算建造 $2n$ 座高楼。为了保证城市美观,球球做出了如下计划:

  • 球球喜欢整齐的事物。他希望高楼从左向右排成一行,编号依次为 $1\sim 2n$。

  • 球球喜欢整数,他要求每座高楼的高度都是正整数。

  • 由于材料限制,高楼的高度无法超过 $m$。

  • 球球喜欢中间高,两边低的造型。他要求前 $n$ 座高楼的高度不下降,后 $n$ 座高楼的高度不上升。

  • 球球打算选两座编号为 $x,y$ 的高楼作为这座城市的地标。他认为只有当这两座高楼高度相等时,才会让城市变得美观。

球球把自己的想法告诉了市长。市长希望得知所有建设城市的方案数。两种方案不同,当且仅当某座高楼的高度在两个方案中不同。这个问题可难倒了球球。球球找到了你,希望你能帮他算出答案。由于答案可能很大,你只需要给出答案对 $998244353$ 取模后的结果。

下午 vp 这道题的时候是真的降智…首先先上已经写好的题解吧:


首先考虑不加 $a_x=a_y$ 的限制,单纯计算一个不递减序列的方案数。

发现本质上是这么一个问题:从 $(0,1)$ 开始走,每一步可以向右走,或者向右上走(此处右上指的是 $(x,y)\to(x+1,y+k)\quad k>0$ 的走法),最终走到 $(n,1),(n,2),(n,3)\cdots (n,m)$ 的方案数。那么不难发现,本质上是在对于两个楼之间的高度差进行拼插。若令 $h_0=0,d_{i}=h_{i}-h_{i-1}$ 的话, 那么本质上就是在解一个如下的方程:

本质上就是在求这个式子中非负整数解得个数…然而并不是。由于 $1$ 号楼必然高度 $\geq 1$ ,所以差分之后, 需要保证 $d_1>0$ 。

考虑做一个容斥,用 $d_1\geq 0$ 的答案减去 $d_1=0$ 时的答案。对于 $d_1\geq 0$ ,本质上就是一个 $n$ 元一次不定方程非负整数解计数。那么答案就是 $\binom{n+m-1}{m}$ 。$d_1=0$ 时,相当于用 $n-1$ 个未知元凑出 $m$ 来,方案数就是 $\binom{n+m-2}{m}$ 。所以可知如果不考虑 $x$ 和 $y$ 的限制,答案应该为 $\left(\binom{n+m-1}{m}-\binom{n+m-2}{m}\right)^2$ 。

考虑加上 $x$ 和 $y$ 的限制。那么需要分类讨论。

1、考虑如果 $x$ 和 $y$ 在同侧,那么可以都转化到 $1\leq x\leq y\leq n$ 的情况来做。那么 $x,y$ 之间的数都要相等假设此时 $x$ 和 $y$ 均等于 $z$,那么 $1\sim x$ 的方案数就是 $\binom{x+z-1}{z}-\binom{x+z-2}{z}$ ,$y\sim n$ 的方案数就是 $\binom{n-y+z}{z}$,因为此时相相当于有 $n-y+1$ 个未知元,和为 $z$ 的非负整数解个数。最后把这两部分拼插一下即可。

2、考虑如果 $x$ 和 $y$ 在异侧,那么两者本质上就没有关系了。于是考虑分别处理 $1\sim x,1\sim y,x\sim n,y\sim n$ 的答案,最后拼插一下即可。

于是复杂度线性。


然后是花絮…这题说实话我做了很久很久…以下事情按时间线排布:

  • 看了这题,觉得 $60$ 分很 ez,然后就在想 $100$ 分怎么搞。因为上次 NOIonline 给我的经验是,生成函数是可以进普及组的,于是觉得这个 100 一定是个生成函数。
  • wqy 说是 xxs 组合题。我想了一会儿觉得大概可以转化成从 $(0,1)$ 走到 $(n,m)$ ,每一步可以平着走或者飞到右边一列一个更高的高度上。算了一波,觉得可能跟 $m$ 的 $n$ 元可含 $0$ 有序拆分有关…觉得不太行。
  • wqy 说是插板法。我觉得自己是个弱智。因为「 $m$ 的 $n$ 元可含 $0$ 有序拆分」 本质上就是 $n$ 元一次不定方程组

的非负整数解组数。于是觉得枚举 $x$ 的高度然后做就很稳,遂开始写代码。

  • 写了半天,恍惚中觉得应该对 $\binom{n+m-1}{m}$ 这东西做一个前缀和,因为 $x$ 的高度如果是 $h$ ,那么 $x-1$ 的高度似乎可以是 $0\sim h$ …【注意!这个地方是有两个bug!!
  • 连写带调试过了好久,发现自己是弟弟,前缀和压根不对。因为枚举的是 $x$ 的高度,所以对于每个 $x$ 的高度,$[1…x-1]$ 的不同方案已经被准确计数了…发现自己的思路乱的很。
  • 又写了很久,还是不对,心情郁闷。冷静了一下发现 $1$ 号位置,即 $x_1$ ,取值不能为 $0$ 。想了想,觉得容斥一下就好了。
  • 最后发现 $70$ 分。下了数据之后思考了一下,发现是 case1 里面,如果 $x$ 和 $y$ 都在另一侧,那么转过来应该是 $y<x$…

写完之后感觉自己花了这么多时间,十分弟弟。总结一下问题:

1、平时深入思考的情况比较少,遇到这种需要认真思考的东西,思路就会很乱很乱。

2、自己思维方式一直存在很大问题,加上草稿打的十分乱,就让人做题的时候内心不安静。

要抓紧改正啊。虽然我觉得可能是我太困了

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
ll ans ;
int num[N] ;
int fac[N] ;
int inv[N] ;
int numx[N] ;
int numy[N] ;
int xnum[N] ;
int ynum[N] ;
int m, n, x, y ;

int expow(int a, int b){
int ret = 1 ;
while (b){
if (b & 1)
ret = (ll)ret * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return ret ;
}
int binom(int x, int y){//\binom{x}{y}
return (ll)fac[x] * inv[y] % P * inv[x - y] % P ;
}
int main(){
fac[0] = inv[0] = 1 ;
cin >> m >> n >> x >> y ; ans = 0 ;
for (int i = 1 ; i <= m + n + 1 ; ++ i)
fac[i] = (ll)fac[i - 1] * i % P ;
inv[m + n + 1] = expow(fac[m + n + 1], P - 2) ;
for (int i = m + n ; i >= 1 ; -- i)
inv[i] = (ll)inv[i + 1] * (i + 1) % P ;
if (!((n - x >= 0) ^ (n - y >= 0))){
x = x < n ? x : n - (x - n) + 1 ;
y = y < n ? y : n - (y - n) + 1 ;
if (x > y) swap(x, y) ; numx[0] = numy[0] = 1 ;
for (int i = 1 ; i <= m ; ++ i) numy[i] = binom(n - y + i, i) ;
for (int i = 1 ; i <= m ; ++ i) numx[i] = decn(binom(x + i - 1, i), binom(x + i - 2, i)) ;
for (int i = 1 ; i <= m ; ++ i) num[i] = addn(num[i - 1], decn(binom(n + i - 1, i), binom(n + i - 2, i))) ;
for (int i = 1 ; i <= m ; ++ i) add(ans, (ll)numx[i] % P * numy[m - i] % P) ;
ans = (ll)ans * num[m] % P ; cout << ans << '\n' ; return 0 ;
}
y = n - (y - n) + 1 ;
xnum[0] = ynum[0] = numx[0] = numy[0] = 1 ;
for (int i = 1 ; i <= m ; ++ i) numx[i] = decn(binom(x + i - 1, i), binom(x + i - 2, i)) ;
for (int i = 1 ; i <= m ; ++ i) numy[i] = decn(binom(y + i - 1, i), binom(y + i - 2, i)) ;
for (int i = 1 ; i <= m ; ++ i) xnum[i] = binom(n - x + i, i) ;
for (int i = 1 ; i <= m ; ++ i) ynum[i] = binom(n - y + i, i) ;
for (int i = 1 ; i <= m ; ++ i)
add(ans, (ll)numx[i] % P * numy[i] % P * ynum[m - i] % P * xnum[m - i] % P) ; //, cout << ans << '\n' ;
cout << ans << '\n' ; return 0 ;
}

E 简单子序列问题

给定一个长度为 $n$ 的正整数序列 $A_1$, $A_2$, $\cdots$, $A_n$。定义一个函数 $f(l,r)$ 表示:序列中下标在 $[l,r]$ 范围内的子区间中,不同的整数个数。换句话说,$f(l,r)$ 就是集合 $\{A_l,A_{l+1},\cdots,A_r\}$ 的大小,这里的集合是不可重集,即集合中的元素互不相等。

现在,请你求出

由于答案可能很大,请输出答案对 $10^9 +7$ 取模的结果。

对于 $100\%$ 的数据,满足 $1\leq n\leq 10^6$,集合中每个数的范围是 $[1,10^9]$。

这题似乎是普及题,但是我不知道为什么,就把这题转化到了这个题的对称问题上…导致这题做了很久很久很久…

以下是题解:


我来说一个很不正常的解法…不正常在他特别麻烦…特别难调…

我的做法是先算出全部区间的贡献:

也就是

然后考虑减掉那些不合法的。具体的,预处理出每个位置左边最近的那个相同颜色的下标 $pre_x$ 。那么 $x$ 和 $pre_x$ 会对左端点在 $1\sim pre_x$ ,右端点在 $x+1\sim n$ 的区间产生贡献。贡献怎么算呢?

考虑假设一个区间长为 $L$ 。那么第一组 $(pre_x,x)$ 出现时,会有

第二组出现时:

以此类推,当一个区间存在 $t$ 个重复颜色时(即假设某种颜色的数量为 $c$,那么这种颜色的「重复颜色数」为 $c-1$),他需要减去 $(2\cdot t\cdot L-t^2)$ 的贡献。

考虑拆成两半做:

1、$2\cdot t\cdot L$

需要枚举每个位置 $i$ ,设 $j=pre_i$ 。记 $p=\max\{(n-i+1),i\},q=\min\{i,(n-i+1)\}$ 。即 $p$ 是左右两边较长的那个区间,$q$ 是较短的那个。同时记当前区间长度为 $d$,即 $d=i-pre_i$ 。以下默认省略前面的系数 $2$ 。

那么需要再分三类讨论会被产生贡献的区间长度 $L$ ,以下在计算 $L$ 时,用 $d+\Delta$ 来代替:

(1)$d+1\leq L\leq q+d$

对于每个这样的 $L$ ,会存在 $L-d$ 个区间产生合法贡献,所以这部分贡献就是

可以通过预处理 $\sum i$ ,$\sum i^2$ 快速计算。

(2) $q+d+1\leq L\leq p+d$

对于每个这样的 $L$ ,由于不能全部取到,所以至多会有 $q$ 个。所以这部分贡献是:

这部分比较好算。

(3) $p+d+1\leq L\leq n$

对于每个这样的 $L$ ,发现最多只能取到 $n-L+1$ 次。所以这部分贡献是

这一部分同样可以通过预处理来快速计算。

综上,这一部分的复杂度是排序外线性。

2、$-t^2$

设 $i$ 右边第一个和 $i$ 同颜色的元素为 $r_i$ 。

也就是现在把问题转化成了「{区间内重复出现的数字个数 $-1$ 的平方和」。考虑扫描线。一开始将所有的数都加进线段树。从左开始,每次都删掉一个最左边的元素 $i$。如果这个元素的颜色依旧出现在后面的序列中,那么可以知道对于所有右端点 $\geq r_i$ 的区间,都会少掉一个 $(i, r_i)$ 组成的 pair,也就是会少掉一个重复颜色的元素。所以就是后缀减 $-1$ and 询问后缀的平方和,线段树维护即可。

这一部分复杂度 $O(n\log n)$ 。

如何卡常:

1、不要用 map .

2、(mayaohua 在 uoj 群里的高论)发现中间,一段区间内部的平方的和本质上是不会爆 long long 的,所以可以减少取模次数。


心路历程:

  • A 完 T1 之后,发现这题「不就是记一下上次出现的位置,然后减掉左端点在 $[1,pre_x]$、右端点在 $[x,n]$ 内的贡献吗?妥了妥了!」期间甚至嘲讽了一波这题很套路
  • 算了一下发现…这个平方和好像很难算。一波拆分之后,觉得应该分成两半做。比较难的似乎是后面的 $t^2$(很久很久的以后我才发现不是这样)。
  • 然后开始写写写,期间由于思路混乱(D里面提到的缺点集中展现),于是写了一会儿才写完(但此时,我只想到了前两部分,没有考虑第三部分)。
  • 写完之后才意识到…我似乎把这个问题转化到了一个和原问题等难的问题上…就很降智。然后决定先写 $50pts$ 的暴力做法。
  • 写完暴力才意识到原来扫描线就好了…于是开始写线段树。
  • 这个线段树我写的就…就很梦幻…我不记得我写过这么梦幻的线段树。大概就是 bug 满天飞…体验极差…
  • 最终总算是调完了,和 $50pts$ 暴力对着拍了几组觉得很稳。
  • 因为总觉得自己第一部分推的有问题,所以写了个 $n^3$ 暴力。写完才发现挂惨了…
  • 冷静了很久,发现是自己推挂了。于是推了推第三部分,发现展开之后式子很长。然后 main 函数中间的那个 for 就写了很长…
  • 最后在谷上测发现自己 TLE+取模挂了,于是把 map 改成 sort+lower_bound 就 A 掉了…

…技不如人,技不如人。

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
template <typename T>
il void add(T &x, T y, ll mod = P){
x += y ; x = x >= mod ? x - mod : x ;
}
template <typename T>
il void dec(T &x, T y, ll mod = P){
x -= y ; x = x < 0 ? x + mod : x ;
}
template <typename T>
il T addn(T x, T y, ll mod = P){
x += y ; return (x = x > mod ? x - mod : x) ;
}
template <typename T>
il T decn(T x, T y, ll mod = P){
x -= y ; return (x = x < 0 ? x + mod : x) ;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
int val[N] ;

ll s[N * 3] ;
ll t[N * 3] ;
ll tg[N * 3] ;

void build(int rt, int l, int r){
if (l == r){
s[rt] = val[l] ;
t[rt] = s[rt] * s[rt] ;
return ;
}
int mid = (l + r) >> 1 ;
build(ls, l, mid) ;
build(rs, mid + 1, r) ;
s[rt] = s[ls] + s[rs] ;
t[rt] = t[ls] + t[rs] ;
}
void _down(int rt, int l, int r){
if (tg[rt]){
ll p = tg[rt] * tg[rt] % P ;
ll pr = r - ((l + r) >> 1) ;
ll pl = ((l + r) >> 1) - l + 1 ;
tg[ls] += tg[rt], tg[rs] += tg[rt] ;
dec(t[ls], decn(2ll * s[ls] * tg[rt] % P, p * pl)) ;
dec(t[rs], decn(2ll * s[rs] * tg[rt] % P, p * pr)) ;
dec(s[ls], tg[rt] * pl % P) ; dec(s[rs], tg[rt] * pr % P) ; tg[rt] = 0 ;
}
}
void update(int rt, int l, int r, int ul, int ur){
if (ul <= l && r <= ur){
dec(t[rt], decn(2ll * s[rt] % P, 1ll * (r - l + 1))) ;
dec(s[rt], 1ll * (r - l + 1)) ; tg[rt] += 1 ; return ;
}
int mid = (l + r) >> 1 ; _down(rt, l, r) ;
if (ul <= mid) update(ls, l, mid, ul, ur) ;
if (ur > mid) update(rs, mid + 1, r, ul, ur) ;
s[rt] = s[ls] + s[rs] ; t[rt] = t[ls] + t[rs] ;
}
ll query(int rt, int l, int r, int ul, int ur){
if (ul <= l && r <= ur) return t[rt] ;
int mid = (l + r) >> 1 ; ll res = 0 ; _down(rt, l, r) ;
if (ul <= mid) res += query(ls, l, mid, ul, ur) ;
if (ur > mid) res += query(rs, mid + 1, r, ul, ur) ;
return res ;
}
int n ;
ll ans ;
ll res ;
ll sum1[N] ;
ll sum2[N] ;
int pos[N] ;
int nxt[N] ;
int buc[N] ;
int tmp[N] ;
int base[N] ;
ll fuck[M][M] ;

const ll Inv6 = 166666668ll ;

int main(){
cin >> n ; int len ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = tmp[i] = qr() ;
sort(tmp + 1, tmp + n + 1) ;
len = unique(tmp + 1, tmp + n + 1) - tmp - 1 ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = lb(tmp + 1, tmp + len + 1, base[i]) - tmp ;
for (int i = 1 ; i <= n ; ++ i){
if (buc[base[i]]) pos[i] = buc[base[i]] ; buc[base[i]] = i ;
}
for (ll i = 1 ; i <= n ; ++ i)
sum1[i] = addn(sum1[i - 1], i) ;
for (ll i = 1 ; i <= n ; ++ i)
sum2[i] = addn(sum2[i - 1], i * i) ;
for (ll i = 0 ; i <= n ; ++ i)
add(ans, (i + 1) * i * (2ll * i + 1ll) % P) ;
ans = ans * Inv6 % P ;
ll q, maxx, minx, m, p, len1, len2, d ;
for (int i = 1 ; i <= n ; ++ i){
if (!pos[i])
continue ;
q = n - i + 1 ;
maxx = q, minx = pos[i] ;
p = i - pos[i], m = n - p ;
d = decn(sum1[m], sum1[maxx]) ;
if (minx > maxx) swap(minx, maxx) ;
len2 = m - maxx, len1 = maxx - minx ;
//part1
add(res, sum2[minx]) ;
add(res, sum1[minx] * p) ;
//part2
add(res, p * minx * len1) ;
add(res, minx * decn(sum1[maxx], sum1[minx], P) % P) ;
//part3
dec(res, 2ll * p * d % P) ;
dec(res, p * p * len2 % P) ;
add(res, 1ll * (n + 1) * d % P) ;
dec(res, decn(sum2[m], sum2[maxx])) ;
add(res, 1ll * (n + 1) * p * len2 % P) ;
dec(ans, 2ll * res % P) ; res = 0 ;
}
if (n <= 1000){
for (int i = 1 ; i <= n ; ++ i){
fill(buc, buc + n + 1, 0) ;
for (int j = i ; j <= n ; ++ j){
buc[base[j]] ++ ;
fuck[i][j] = fuck[i][j - 1] + (buc[base[j]] > 1) ;
add(ans, fuck[i][j] * fuck[i][j]) ;
}
}
cout << ans << '\n' ; return 0 ;
}
fill(buc, buc + n + 1, 0) ;
for (int i = n ; i >= 1 ; -- i)
nxt[i] = buc[base[i]] ? buc[base[i]] : n + 1, buc[base[i]] = i ;
fill(buc, buc + n + 1, 0) ;
for (int i = 1 ; i <= n ; ++ i)
buc[base[i]] ++, val[i] = val[i - 1] + (buc[base[i]] > 1) ;
build (1, 1, n) ;
for (int i = 1 ; i < n ; ++ i){
add(ans, query(1, 1, n, i, n) % P) ;
if (nxt[i] <= n) update(1, 1, n, nxt[i], n) ;
}
cout << ans << '\n' ; return 0 ;
}

F 游戏

小 A 和小 B 正在玩一个游戏:有一棵包含 $n=2m$ 个点的有根树(点从 $1\sim n$ 编号),它的根是 $1$ 号点,初始时两人各拥有 $m$ 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点,若对手的点在自己的点的子树内,则该回合自己获胜;若自己的点在对方的点的子树内,该回合自己失败;其他情况视为平局。游戏共进行 $m$ 回合。

作为旁观者的你只想知道,在他们随机选点的情况下,第一次非平局回合出现时的回合数的期望值。

为了计算这个期望,你决定对于 $k=0,1,2,\cdots,m$,计算出非平局回合数为 $k$ 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 $x$,小 B 在 $x$ 被小 A 选择的那个回合所选择的点不同。

由于情况总数可能很大,你只需要输出答案对 $998244353$ 取模后的结果。

$n\leq 5000$ 。

第一眼看到「期望」字样其实我是想弃的。

不算十分有趣的题,比较中规中矩地考察了我没有的硬实力。

考虑因为是随机选点,先要计算一个 $f_{i,j}$ 表示子树 $i$ 内凑出 $j$ 个不同的「非平局点对」的方案数。转移考虑两部分:

1、子树之间的贡献:就是普通的树上背包那么转移。注意到如果界定的好是可以 $n^3\to n^2$ 的。

2、根与子树之间的贡献:加法原理一波带走即可。

然后考虑 $f_{1,i}$ 就是整棵树凑出 $i$ 个不合法对,也就是不平局 $i$ 次的方案数。考虑利用这个东西,本质上还是很难求出共非平局 $k$ 次的方案数,因为无法快速统计剩下那些平局的贡献。但是考虑,可以快速计算出非平局 $\geq k$ 次的方案数,就是 $f_{1,k}\cdot (\frac{n}{2}-k)! $ 。至于为什么呢…可以理解为剩下 $n-2\cdot k$ 个人,固定住一半个人,剩下一半的人随便找一个匹配,那么方案数就是剩下一半人的全排列,即 $(\frac{n-2\cdot k}{2})!$ 。

那么考虑令 $f_i$ 表示至少非平局 $i$ 次的方案数,设 $g_i$ 为恰好平局 $i$ 次的方案数,那么根据二项式反演有

于是复杂度 $O(n^2)$,略卡常数。

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
int n ;
ll F[N] ;
ll G[N] ;
ll fac[N] ;
ll tmp[N] ;
ll f[N][N] ;
int suma[N] ;
int size[N] ;
int base[N] ;
ll comb[N][N] ;

void do_dp(int x, int fa){
size[x] = 1 ; f[x][0] = 1 ;
for (int k = head[x] ; k ; k = next(k)){
if (to(k) == fa)
continue ; do_dp(to(k), x) ;
fill(tmp, tmp + size[to(k)] + size[x] + 1, 0) ;
for (int i = min(size[x], n / 2) ; i >= 0 ; -- i){
if (f[x][i]){
for (int j = min(size[to(k)], n / 2 - i) ; j >= 0 ; -- j){
if (f[to(k)][j])
add(tmp[i + j], f[x][i] * f[to(k)][j] % P, P) ;
}
}
}
for (int i = 0 ; i <= size[x] + size[to(k)] ; ++ i) f[x][i] = tmp[i] ;
suma[x] += suma[to(k)] ; size[x] += size[to(k)] ;
}
// cout << x << " & " ; debug(f[x], 0, 10) ;
if (!base[x]){
for (int i = min(suma[x], size[x] - suma[x]) ; i >= 1 ; -- i)
add(f[x][i], f[x][i - 1] * (ll)max(suma[x] - i + 1, 0) % P, P) ;
}
else {
for (int i = min(suma[x], size[x] - suma[x]) ; i >= 1 ; -- i)
add(f[x][i], f[x][i - 1] * (ll)max(size[x] - suma[x] - i + 1, 0) % P, P) ;
}
// cout << x << " & " ; debug(f[x], 0, 10) ;
}
int main(){
//freopen(".in", "r", stdin) ;
//freopen(".out", "w", stdout) ;
cin >> n, fac[0] = 1 ; int u, v ;
for (int i = 1 ; i <= n ; ++ i)
fac[i] = (ll)i * fac[i - 1] % P ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%1d", &base[i]), suma[i] = base[i] ;
// debug(base, 1, n) ;
// debug(suma, 1, n) ;
for (int i = 1 ; i < n ; ++ i)
u = qr(), v = qr(), add_e(u, v) ; do_dp(1, 0) ;
// debug(base, 1, n) ;
// debug(suma, 1, n) ;
for (int i = 0 ; i <= n ; ++ i) comb[i][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
comb[i][j] = addn(comb[i - 1][j], comb[i - 1][j - 1], P) ;
for (int i = 0 ; i <= n / 2 ; ++ i)
F[i] = f[1][i] * fac[n / 2 - i] % P ;
// debug(f[1], 0, n) ; debug(F, 0, n) ; debug(fac, 1, n) ;
for (int i = 0 ; i <= n / 2 ; ++ i)
for (int j = i ; j <= n / 2 ; ++ j)
(!(j - i & 1)) ? add(G[i], F[j] * comb[j][i] % P, P) : dec(G[i], F[j] * comb[j][i] % P, P) ;
debug(G, 0, n / 2, '\n', '\n') ; return 0 ;
}

总结

还是太弱啊…不过打这一场比赛确实很浪费精力,毕竟一道线段树+一道 xxs 组合加起来我能调 $7h$ 也是相当弱菜了…