https://atcoder.jp/contests/abc295/tasks

E - Kth Number

给长n数组a, $a[i]\in[0,M]$

对于每个$a[i]=0$,等概率修改$a[i]\in[1,M]$

所有修改完后, sort a

问 exp(A[k]) mod 998244353

N 2000

M 2000

4s

1024mb

我的思路

$ans = \sum_{v=1\to m} v\cdot p(v)$

其中$p(v)$表示 $v$是排序后第$k$小的概率

有$z$个0,其中$z_1$个改为$< v$,$z_2$个改为$=v$,剩下$z-z_1-z_2$个改为$> v$

$p(v) \cdot z^m = \sum_{z_1,z_2} \binom{z}{z_1}\binom{z-z_1}{z_2} (v-1)^{z_1}1^{z_2}(m-v)^{z-z_1-z_2}$, 其中 $z_1 + count(<v) < k$且$z_1+z_2+count(\le v) \ge k$

看上去是$O(m n^2)$的

https://atcoder.jp/contests/abc294/tasks

Ex - K-Coloring

n点无向图

m 边

点赋值 [1,k] 相邻点值不同的方案数 mod 998244353

n 30

m [0,30]

k 1e9

8s

1024mb

我的思路

m 30, n 30, 想到的30相关的就是2^{30/2} 的meet-in-the-middle, 但没什么具体的想法

方案统计

对于一个具体方案，考虑按照 点的index顺序从小到大交换

例如 1染色x , u染色1, 那么把所有x和1染色的交换成1和x, 那么得到的依然合法

这样 index顺序虫小到大 染色c个的方案数 f(c)

ans = sum f(c) A(Permutation)(k,c)

1
2
3
4

dfs(u, cntcolor){
  color[u] = [1..cntcolor+1] and !=color[v in connect[u]]
  dfs(u+1, max(cntcolor,color[u]);
}

感觉复杂度会爆炸?吧?

不同难搞，要不然就是反过来容斥 相同

属性i = 边i连的两点颜色相同

ans = sum (-1)^count(属性…) g(属性…)

这个问题就是 $2^{30}$太大, 需要拆分

右侧的g()=k^{未连通块个数}

https://atcoder.jp/contests/abc293/tasks

Ex - Optimal Path Decomposition

n 点树

找最小整数k，使得有方案满足染色

• 每个相同具体颜色，连通且简单路径
• 树里所有简单路径 最多K种颜色

n 2e5

2s

1024mb

我的思路

这第一眼上去像是重轻儿子

第二眼上去像是树上DP

虽然具体的染色的情况 不和 K直接相关

但是 当两个不同颜色链的端点相邻，那么把它们染成同样的颜色，得到的K不会比之前的更差

dp[u][u是否可以向上连] = {u的子树中最多颜色的路径，从u向下最多颜色的路径}

显然 子树cnt >= u向下

看起来是一个 O(n^2) 的状态

而从u 向下最多颜色的路径 <= u到最深叶子的

如果有办法 把这个缩减这个向下颜色的路径的维度

然而根据轻重儿子的链式方法，根到任何叶子最多经过O(log(n)) 条不同的重链

所以如果直接 轻重链方案，那么方案 <= 2log n

所以 dp[u][u是否可以向上连][u向下最多的颜色的路径 <= 2log n] = u子树中最多颜色的路径

似乎就能做了?

https://codeforces.com/contest/1830

B - The BOSS Can Count Pairs

长度n数组 a,b

计算多少对 i < j 满足 ai * aj = bi + bj

t 1e4

sum n 2e5

ai,bi [1,n]

4s

512mb

我的思路

加的范围保证了 <= 2n

所以 对于同样的a 直接整合

然后 2n (1+1/2+1/3+…), 所以真的枚举的 乘法对是满足范围的

然后对于具体的 v0=ai,v1=aj

那么对应 bi/bj 是两个集合, 或者map[b]=count

每次选小的 去大的里面搜, 这复杂度不知道多少, 过了pretest,被hack tle了

https://codeforces.com/contest/1830/submission/207625447

https://atcoder.jp/contests/abc291/tasks

Ex - Balanced Tree

给定n点树T

构建n点新的有根树R满足

• lca(u,v) 在 T中的path(u,v)上

• 所有非根点u, 2sz[u] <= sz[fa[u]]

(题目保证有解)

输出R

n 1e5

2s

1024mb

我的思路

显然 性质2说明所有向下分叉至少是2叉

性质一怎么用?

如果在R中u是v的祖先节点

lca(u,v) = u

u一定在路径T(u,v)上

…

v1,v2 在 u 两个分支, lca(v1,v2) = u

u要在(v1,v2) 路径上

…

如果u选作 R的根, 那么在T 中u的一个分支中的所有点一定在R中也是同一个分支中

所以要在T中找一个点，使得它的所有分支的点数 * 2 都 <= n

注意到 任意点最多一个分支 点数 * 2 > n, 所以沿着这个方向走，这个方向的点数单调递减

而 …-u-(v > n/2), 则从选择u移动到选择v: (…-u < n/2)-v-(…)

所以总可以找到一个点

那么选作为根以后，直接按它切开，剩余的连通块就是子问题了

但是如何 优化每次寻找?

还是直接暴力复杂度就够了

注意到第一次是O(n)

那么第二次每个块 <= n/2, 而总复杂度依然是O(n)

所以 O(n log n) 暴力就没了

写完以后发现，不一定是 所有二叉，因为 两点的话 ，叶子是1, 带叶子的一个是2也是合法的，所以二不二叉不重要，重要的是所有分叉 <= n/2