LuoguLOJ分析考虑容斥,问题变为计算至少有 $i$ 组人讨论 cxk 的方案数。首先我们需要选出 $i$ 个位置 $p_{1..i}$ 满足 $[p_j,p_j+3]$ 不交,容易算出方案数为 ${n-3i\choose i}$。对于剩下的位置,枚举每种学生的个数,方案数是一个多重集排列数,式子是可以看成四个生成函数卷起来,用 NTT 可以 $\mathcal{O}(n\log n)$...
Luogu分析答案显然是直接分治把所有 $1-a_ix$ 卷起来,然后多项式 $\ln$ + 多项式求导即可求出 $G(x)$,再推回 $A(x)$ 后卷积即可。代码不想写 vector,于是从鱼那里蒯了一个分治 /kel// ==================================== // author: M_sea // website: https://m-sea...
LOJ分析无。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freo...
咕,咕咕,咕咕咕
Luogu分析先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为多项式求逆即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <...
Luogu分析设 $f_i$ 为 $i$ 个点的 DAG 数量。一个想法是枚举入度为 $0$ 的点的数量,有多项式求逆即可。现在还要求弱连通,那么把 $F(x)$ 求个多项式 $\ln$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ /...
LuoguLOJ分析显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数,不难得到可以发现是一个差卷积的形式,于是直接 NTT 即可。代码// =======================...
CodeforcesLuogu分析设 $s_i$ 表示 $i$ 是否在集合中,$f_i$ 表示权值和为 $i$ 的二叉树数量,那么多项式开根+多项式求逆即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ================...
Luogu分析设 $f_i$ 为 $i$ 个点的无向连通图个数,$g_i$ 为 $i$ 个点的无向图个数,那么显然有多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com...
LuoguLOJ分析后面显然是卷积的形式,直接 NTT 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h&...