nowcoder 牛客挑战赛73

發表於 更新於 分類於 Disqus： 文章字數： 2.5k 所需閱讀時間 ≈ 8 分鐘
D(贡献统计，期望，树，生成函数,NTT)E()F(DP,树)

https://ac.nowcoder.com/acm/contest/76652

D S 老师的虚树

给n点定树T，边有颜色

对于 点集S,包含点集S的最小连通点集V’对应的树为生成树T’

w(S)=T’中不同颜色边个数

对于 i=1..n

计算 |S|=i的w的期望Exp(w(S)),结果mod 998244353

n 2e5

2s

512mb

我的思路

感觉就是算贡献，对于点为i的 点集合，对于颜色c的所有边来说，如果有横跨 边的两个点，那么贡献1,否则贡献0

那么考虑不跨边更简单，也就是 贡献i,c=所有情况 - 不跨边

$= \binom{n}{i}-\sum_{blk_j} \binom{blk_j}{i}$ 其中 blk是按照指定颜色切割的块

那么 $ans_i= C\binom{n}{i}-\sum_{blk_j} \binom{blk_j}{i}$,其中C是颜色总个数,blk是所有颜色独立的切割

那么问题来了，每个颜色切割的块数 = 当前颜色边数+1,

所以右侧有 n+C个 <=2n, 但是直接计算，对于每个i来说复杂度也是 $O(n)$的,总的复杂度会tle

生成函数我也想过没想过怎么简化

题解

一样的思路

$ans_i=\sum_{j} \binom{sz_j}{i} = [x^i]\sum_{j}(1+x)^{sz_j}$

$a_i=$大小为i的块的个数

$[x^i]\sum_{j}a_j(1+x)^j$

$=\sum_{j}x^j\sum_{i=j}^n\binom{i}{j}a_i$

$=\sum_{j}x^j\sum_{i=j}^n\frac{i!}{j!(i-j)!}a_i$

$=\sum_{j}\frac{x^j}{j!}\sum_{i=j}^n(a_ii!)\frac{1}{(i-j)!}$

所以需要处理的是右侧

$r_j=\sum_{i=j}^n(a_ii!)\frac{1}{(i-j)!}$

$t_j=r_{n-j}=\sum_{i=n-j}^n(a_ii!)\frac{1}{(i-n+j)!}$

令$k=n-i$有$i=n-k$

$=\sum_{k=n-n}^{n-(n-j)}(a_{n-k}(n-k)!)\frac{1}{(j-k)!}$

$=\sum_{k=0}^{j}(a_{n-k}(n-k)!)\frac{1}{(j-k)!}$

即令 $[x^k]f(x)=a_{n-k}(n-k)!$

$[x^k]g(x)=\frac{1}{k!}$

$r_j=t_{n-j}=[x^{n-j}]f * g(x)$

$ans_i= \frac{1}{i!} r_i=\frac{1}{i!} [x^{n-i}]f * g(x)$

E S 老师的礼物

n个节点的树，只给定 每个节点i的最小邻居 ai

你需要判断

  • 该树唯一存在 （需要输出具体树）
  • 存在多个方案
  • 该树不存在

t 2e5组

n 5e5

1s

512mb

我的思路

首先 如果是合法的树，那么 上面的n条边（i-ai) 一定存在重边

如果只存在一条重边且全部连通，那么树唯一，但不一定满足条件（检验一下每个点实际的最小邻居是否满足）

然而这充要吗？

如果给你一个树，你会怎么统计所有点的最小节点呢？

首先是1, 把所有1相连的节点u,令 au=1

情况1： 这些点里包含2

情况2： 这些点里不包含2

1
2
3
4
1-2-3: (a1=2,a2=1,a3=2)
1-3-2: (a1=3,a2=3,a3=1)
2-1-3: (a1=2,a2=1,a3=1)
发现是可以区分的
1
2
3
4-1-3-2 （a1=3,a2=3,a3=1,a4=1)
3-1-4-2 （a1=3,a2=4,a3=1,a4=1)
也是能区分的

上面核心在于 有且只有1条重复边

1
2
3
4
5
6
7
8
9
1-3-4-2 （a1=3,a2=4,a3=1,a4=2)
也是可以区分的！！！！！！！！ 这个例子很神奇，感觉上了一些排除法的感觉，这里有2个重边

然而

3-1-4-5-2 (a1=3,a2=5,a3=1,a4=1,a5=2)
4-1-3-5-2 (a1=3,a2=5,a3=1,a4=1,a5=2)

也是两个重边，却没有唯一方案

如何评价呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
（a1=3,a2=4,a3=1,a4=2)得到的是
1-3, 2-4 其中 额外连接需求是

1(>=3)-3(>=1)
2(>=4)-4(>=2)

需要的是 对于后一个连通，有且只有一个点能在前置的点中找到连接方案，而注意到连接后 不会影响 每个点的连接需求，

而后面的
(a1=3,a2=5,a3=1,a4=1,a5=2)得到的是
3(>=1)-1(>=3)-4(>=1)
2(>=5)-5(>=2)

会发现 3,4 都能 和 5 配对

然后这里不是 前置，应该是其它连通块中找

而且最终 所有的要连接到一起

而且连接时 是 不能一个块有两个方案，但是可以块a的点 同时连块B和块C

换句话说 链接 发生时，原本两个块不是同一块

那么用二维坐标表示就是

(x(>=y)) 放置时，add(点(x,y))

(x(>=y))查询时，查询所有点(>=y,<=x) 并做并查集操作

这样如果最后不是1个并查集那么 则该树不存在

这样 如果出现了 已经合并的再次合并那么说明 至少2棵树，（注意最多合并n-1次，但中间如果跳过的话，可能无法合成所有该合并的点

问题1，如果可行，这复杂度是 2d segtree + 并查集

问题2，当不满足时，如何在时间复杂度内判断是 不存在 还是 不唯一

题解

先判断不存在：也就是连通性

对所有$a_u\le v,a_v\le u$的$(u,v)$二元组连边

1
2
3
4
5
6
7
8
9
10
大根堆 = maxpq{i,并查集标识}
小根堆 = minpq{并查集中a[i]最小的，并查集标识}

for u =1...n:
	那么 这时 所有 < u的已经处理好了
	首先 把 minpq中 所有 a[i] <= u的点移动到大根堆里
	也就是大根堆里的点 都满足 a[i] <= u, 而大根堆里的比较项是i
	然后对大根堆里的 a[u] <= i的点 完成合并，这里从大到小合并，所以合并后的点除了最大点都可以删除（因为未来这些点全在大根堆里 也属于同一个并查集，而且比较核心是 a[v] <= i）
	最后 把 {a[u],uf[u]} 放入小根堆（因为可能a[u] > u, 虽然并查集上是一块，但是不能参与和后面的直接合并）
	所以这里有清除操作 可以set,也可以先取出来再放回去

emmmmmmmmmm 这样做的话 的确复杂度就很小了不会多个log了

我看题解这里 for v(ai)=n...1, for i in ai2i[v]

然后 堆里的 都满足 u >= v(a[i]), 找堆里a[u] <= i

这样的话 我的第二个问题就解决了，也就是能判断 无方案的情况了

对于第一个问题 就是 无脑线段树

存储时键为u,值为a[u]

所以每次查询 都是query(a[u]~n, <= u), 那么线段树维护区间最小值

注意到这样做 单次复杂度最高是O(n) 但如果真的这样 会让 边超过n-1,也就是有效的 查询和合并次数 一定是 <= n-1的，否则 一旦某次 > n-1 那么直接就退出了，而单次最多n, 所以 不会超时

F S 老师的合并

两个树T1,T2分别有n1,n2个节点,

第一个树 根1,节点编号1~n1

第二个树 根n1+1,节点编号n1+1~n1+n2

问有多少个n1+n2点的有根树T满足，对于Ti中 任意两个点

  • Ti中有 祖先关系的点 当且仅当 在T中也有祖先关系，
  • 在Ti中x的dfs序小于y, 当且仅当 在T中x的序小于y

求满足的树T的个数 mod 998244353

n1,n2 [1,100]

3s

512mb

我的思路

首先T的根一定是1或n1+1,因为如果是其它节点，那么根据第一个 祖先的当且仅当关系，那它们的祖先有1或n1+1必定不对

考虑最简单的图

1
2
  1         4
2   3     5   6

当钦定1是根以后，讨论4是否直接和1连，那么有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4不和1的直接子节点穿插 = 1的子节点个数+1

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


4 和1的直接子节点穿插 = f([4],[2]) + f([4],[3]) + f([4],[2 3])

    1          1          1
4[2]  3     2  4[3]     4[2 3]

4 不和1直接相连 = f([2],[4]) + f([3],[4])

   1           1
2[4]  3      2   3[4]

有什么 发现，有什么问题呢

这里 感觉上 点一定是连续的某个点的子节点的一段

问题是

1
2
3
4
f([4],[2 3])
    1
    4
[2 3] [5 6]

这里 感觉 不如虚拟一个0节点为T的根

那么g([...],[....]) 就是 在两组根，内部保持顺序的情况下的方案数

ans=g([1],[n1+1])

如果这个能快速算出，那么似乎就是$O(n^4)$的问题了

1
2
3
4
5
6
g(a[...],b[...])

那么大概的形状是 这样的，也就是 对于a中 直接和祖先x相连的来说 他们未相连的 一定是对应b的后代
      x
  aaa bbbb aaaa bbbb
  bbb aaaa bbbb aaaa

所以这里想的是dp

1
2
3
4
5
6
7
dp[i][j] = a消耗了前i个b消耗了前j个的方案数

dp[i][j] += dp[i-1][j0<=j] * g(a[i].child, b[j0+1..j]) # 这里a[i]和根连

dp[i][j] += dp[i0<=i][j-1] * g(a[i0+1..j],b[j].child) # 这里b[j]和根连

g(a,b) = dp[len(a)][len(b)][a+b]

也就是 状态转移 总代价是n^4 就ac了

题解

参考

https://www.nowcoder.com/discuss/598273393213923328

总结

D - 虽然主拆解想到了，但是后面的没在草稿纸上展开，展开还是应该能发现是卷积的形式，我也感觉像但就是自己没 去做把下标逆转的操作，这应该是自己就能做出来的题目

E- (u,v) 对于$a_u\le v,a_v\le u$的所有连线 检查连通性 没想到简单的并查集+堆就可以实现！！！！！ 后面也是，感觉主体的逻辑想的没问题，但是细节的复杂度还是没卡死，没卡到位。

F - 这对知识要求比D和E小啊， 感觉也比D和E简单，就是个有点小怪的树上DP