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