淄博免费网站建设,生产企业网站欣赏,濮阳网络科技有限公司,最新办公室设计题目链接
这个挑战赛的 F F F是我出的#xff0c;最后 zhoukangyang 爆标了。。。orzorz
记所有有颜色的边的属性集合 S S S 。
首先在外层容斥#xff0c;枚举 S ∈ [ 0 , 2 w ) S\in [0,2^w) S∈[0,2w)#xff0c;计算被覆盖的的边中不包含 S S S 中属性#xff0c…题目链接
这个挑战赛的 F F F是我出的最后 zhoukangyang 爆标了。。。orzorz
记所有有颜色的边的属性集合 S S S 。
首先在外层容斥枚举 S ∈ [ 0 , 2 w ) S\in [0,2^w) S∈[0,2w)计算被覆盖的的边中不包含 S S S 中属性并且没有被覆盖的边的数目恰好为 i i i 的配对方案数。
暴力的 DP 做法是记录子树内还没有被匹配的点的数目复杂度 O ( n 5 ) O(n^5) O(n5)不能通过。出题人特意卡了这种做法。
如果一条边没有覆盖那么所有点对间的路径都不能经过这条边这样我们可以把一个连通块分成两个子联通块进行求解。但是这样就要记录连通块里面所有的点无法通过
考虑二项式反演。记 g ( i ) g(i) g(i) 表示钦定断了 i i i 条边即 i i i条边没有被覆盖的方案数 f ( i ) f(i) f(i) 表示恰好断了 i i i 条边的方案数注意这里的下标 i i i 不包含一定不被覆盖的边。那么有 g ( i ) ∑ j i n − 1 ( j i ) f ( j ) ⇒ f ( i ) ∑ j i n − 1 ( − 1 ) j − i ( j i ) g j g(i)\sum _{ji}^{n-1}\binom{j}{i}f(j)\Rightarrow f(i)\sum_{ji}^{n-1}(-1)^{j-i}\binom{j}{i}g_j g(i)∑jin−1(ij)f(j)⇒f(i)∑jin−1(−1)j−i(ij)gj
而 g ( i ) g(i) g(i) 是好算的也就是剩下的每个连通块内部任意连边的方案数的乘积
记 h ( n ) h(n) h(n) 表示大小为 n n n 的连通块任意连边的方案数如果 n n n 为奇数那么答案是 0 0 0如果 n n n 为偶数那么答案是 ( n − 1 ) × ( n − 3 ) × . . . × 1 (n-1)\times (n-3)\times ...\times 1 (n−1)×(n−3)×...×1
考虑 DP。设 d p ( u , i , j ) dp(u, i, j) dp(u,i,j) 表示以 u u u 为根的子树已经断了 i i i 条边连通块大小为 j j j 的方案数。对于一条边 ( u , v , w ) (u,v,w) (u,v,w) 转移式子如下 1.1 1.1 1.1 d p ( u , i , j ) × d p ( v , i 2 , j 2 ) × h ( j 2 ) → d p ( u , i i 2 1 , j ) dp(u, i, j) \times dp(v, i_2, j_2) \times h(j_2) \to dp(u, i i_21, j) dp(u,i,j)×dp(v,i2,j2)×h(j2)→dp(u,ii21,j) 1.2 1.2 1.2 如果 w ∉ S w\notin S w∈/S d p ( u , i , j ) × d p ( v , i 2 , j 2 ) → d p ( u , i i 2 , j j 2 ) dp(u,i,j)\times dp(v,i_2,j_2)\to dp(u,ii_2,jj_2) dp(u,i,j)×dp(v,i2,j2)→dp(u,ii2,jj2)
这个 DP 的时间复杂度上界是 O ( n 4 ) O(n^4) O(n4) 的因此总复杂度 O ( 2 w n 4 ) O(2^wn^4) O(2wn4) 。
但是注意到每个连通块大小都是必须偶数因此常数极小实测单次 DP 计算量在 1 0 6 10^6 106 左右链的情况可以卡满。注意要把 DP 值为 0 的状态跳过否则无法通过
数据里面造了一些几条链并起来的情况暴力要跑 4s 以上std 能稳定在 0.5s 内出解。随机数据下基本卡不了。如果有人暴力冲过去了或者正解被卡常了出题人在这里谢罪:(
考虑到打这场比赛的大佬肯定还是比较多的如果场切这道题的大佬们有更精确的分析复杂度的方式欢迎赛后分享。
updF 存在 O ( 2 w n 3 ) O(2^wn^3) O(2wn3) 的做法具体是将DP状态的第一维看成多项式并用点值来维护。详见zhoukangyang的代码。
