ooooo
min_inf
·
·
个人记录
A
## B
枚举 $a,b$，根据题意直接设计 DP $f_i=f_{i-2},g_i=f_{i-3}+g_{i-3}$，矩阵快速幂优化。$O(\log n)$。
## C
容斥，钦定 $i$ 个数大于 $m$，容易插板法，贡献为 $(-1)^i\binom n i\binom{n-1+S-i(m+1)}{n-1}$。$O(n+S)$。
## D
每个数互不相同，可以最后答案乘上 $n!$。设 $f_{i,j,0/1}$ 表示前 $i$ 个数选了 $j$ 个，最后一个的奇偶性，矩阵快速幂 NTT 优化。$O(m\log m)$。
## E
直接 DP，设 $f_{i,j}$ 表示 $\le i$ 长度为 $j$ 的方案数。$O(nm\min(n,m))$。
## F
设 $f_{i,0/1,0/1}$ 表示 $i$ 个数，蓝色和黄色的奇偶性，矩阵快速幂。$O(\log n)$。
## G
双指针，维护当前的背包。删除一个数就是加入一个数倒过来 DP。$O(nm)$。
## H
DP，有 $f_{i,j}=\sum\limits_{k=0}^{j}2^{j-k}f_{i-1,k},f_{0,j}=2^{j-1}$。卷积的形式直接快速幂。$O(n\log n\log m)$。
## I
直接分治然后 NTT 合并选了几个数的答案。$O(n\log^2 n)$。
## J
$f_i=\sum\limits_{j=1}^m \frac 1 mf_{i-a_j}$，cdq 分治 NTT 转移。$O(n\log^2 n)$。
## K
容斥，有 $f_0=-1,f_i=-\sum\limits_{j=0}^{i-1}(i-j)!f_j$，cdq 分治 NTT 转移。$O(n\log^2 n)$。
## L
容斥，$a$ 个二元环 $b$ 个自环贡献为 $(-1)^{a+b}\frac{n!(2a-1)!!}{(2a)!b!}$，NTT 即可。$O(n\log n)$。
## M
设 $f_i=2^{\binom i 2}$ 为不要求连通的方案数，有答案 $g_i=f_i-\sum\limits_{j=0}^{i-1}\binom{i-1}{j-1}g_jf_{i-j}$，cdq 分治 NTT 转移。$O(n\log^2 n)$。