ooooo

$0,1,0,1,1,0,1$ 卷积 $n$ 次的结果，直接 NTT 快速幂。$O(n \log n)$。

枚举 $a,b$，根据题意直接设计 DP $f_i=f_{i-2},g_i=f_{i-3}+g_{i-3}$，矩阵快速幂优化。$O(\log n)$。

容斥，钦定 $i$ 个数大于 $m$，容易插板法，贡献为 $(-1)^i\binom n i\binom{n-1+S-i(m+1)}{n-1}$。$O(n+S)$。

每个数互不相同，可以最后答案乘上 $n!$。设 $f_{i,j,0/1}$ 表示前 $i$ 个数选了 $j$ 个，最后一个的奇偶性，矩阵快速幂 NTT 优化。$O(m\log m)$。

直接 DP，设 $f_{i,j}$ 表示 $\le i$ 长度为 $j$ 的方案数。$O(nm\min(n,m))$。

设 $f_{i,0/1,0/1}$ 表示 $i$ 个数，蓝色和黄色的奇偶性，矩阵快速幂。$O(\log n)$。

双指针，维护当前的背包。删除一个数就是加入一个数倒过来 DP。$O(nm)$。

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)$。

直接分治然后 NTT 合并选了几个数的答案。$O(n\log^2 n)$。

$f_i=\sum\limits_{j=1}^m \frac 1 mf_{i-a_j}$，cdq 分治 NTT 转移。$O(n\log^2 n)$。

容斥，有 $f_0=-1,f_i=-\sum\limits_{j=0}^{i-1}(i-j)!f_j$，cdq 分治 NTT 转移。$O(n\log^2 n)$。

容斥，$a$ 个二元环 $b$ 个自环贡献为 $(-1)^{a+b}\frac{n!(2a-1)!!}{(2a)!b!}$，NTT 即可。$O(n\log n)$。

设 $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)$。