by 学军中学

1001

1003

给出一张图,求其所有子图的最少染色数

状压DP

$d_{s} = min(d_{s-s’} + 1)$
$s’$ 是相互之间没有连边的点集
我们可以暴力预处理出$s’$

复杂度$3^n$

1006

1008

给定一个序列$A_i$,求其所有子集中前k大的数的和

NTT

定义 $f(k)$ 为每个数作为第k大的数的贡献(设A从大到小有序)
$f(k) = \sum_{i = k}^n C_{i-1}^{k-1}2^{n-i}A_i$

令$i’ = i + k$,$f(k) = \sum_{i’ = 0}^{n-k} \frac{(i’ + k - 1)!}{i’!(k-1)!}2^{n-k-i}A_{i’+k}$
$f(k) = \frac{1}{(k-1)!2^k}\sum_{i’ = 0}^{n-k} \frac{(i’ + k - 1)!}{i’!}2^{n-i’}A_{i’+k}$

令$x1_{i’} = (i’-1)! a_{i’},x2_{i’} = \frac{2^{n-i’}}{i’!}$
则$f(k) = \frac{1}{(k-1)!2^k}\sum_{i’ = 0}^{n-k} x1_{i’ + k}x2_{i’}$
将$x_1$ reverse一下,$g(k) = \sum_{i’ = 0}^{n-k} x1_{n-k-i’}x2_{i’}$,就是一个卷积的形式了
$f(k) = \frac{1}{(k-1)!2^k}g(n - k + 1)$

最后答案就是前k个前缀和

1011

判断交换两个不同位置(必须且仅一次)的括号序列是否合法

匹配过程中如果有两个以上的右括号不匹配
那么肯定不合法,左右括号数量不同也不合法
注意特判 () 是不合法的