[生成函数+分治NTT+多项式ln]洛谷4705【玩游戏】题解
题目概述Luogu4705解题报告二项式展开后：$$
{t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a_i^k){1\over(t-k)...
[生成函数+多项式除法求系数]2021牛客暑期多校训练营8 H【Scholomance Academy】题解
题目概述Scholomance Academy解题报告伪装成数论题的多项式全家桶题。首先我们可以把 $\varphi(n)$ 拆成 $\prod\varphi(p_i^{a_i})$ ，因此不难...
[生成函数+记忆化搜索]HDU7057【Buying Snacks】题解
题目概述HDU7057解题报告首先这道题很显然可以用生成函数做，但是 $n$ 太大了，因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$ 表示花费 $i$ 时的生成函数，那么不...
[容斥+生成函数+分治NTT]ACL Beginner Contest F【Heights and Pairs】题解
题目概述ACL Beginner Contest F解题报告直接求不太可做，我们考虑容斥，用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……$2n$ 个元素两两组合的方案数为 $f_...
[指数型生成函数+倍增+NTT]BZOJ5381【or】题解
题目概述求多少序列 $\{A_n\},A_i\in[1,2^K)$ 满足 $B_1=A_1,B_i=B_{i-1}\ or\ A_i$ 的序列 $\{B_n\}$ 严格递增。解题报告不难转化成这...
[指数型生成函数+分治NTT+广义容斥]LOJ6503(雅礼集训 2018 Day4)【Magic】题解
题目概述有 $n$ 种颜色的膜法卡，每种颜色有 $a_i$ 种，总共有 $m$ 张。现在要把所有卡片排成一排，如果相邻两个卡片颜色相同则产生一个膜法对，求膜法对个数为 $k$ 的排列个数...
[生成函数+多项式开根+多项式求逆]Codeforces438E【The Child and Binary Tree】题解
题目概述求用集合 $S$ 中的点权构造点权和为 $[1,m]$ 的二叉树的方案数。解题报告生成函数什么的好大啊，我好菜啊。令 $C(x)$ 表示所有点权的生成函数，我想的是：$$
F(x)=\s...
[指数型生成函数+多项式ln]BZOJ3456【城市规划】题解
题目概述求 $n$ 个点简单无向连通图的个数。解题报告我感觉好像重新学了一遍指数型生成函数的样子……普通型生成函数解决的是组合问题，而指数型生成函数解决的是排列问题，比如把 $n$ 个不同的物...
[生成函数+FFT]计蒜客NAIPC2016E【K-Inversions】题解
题目概述有一个AB字符串，问间距为 $k$ 的BA对有多少，其中 $k\in[1,n-1]$ 。解题报告emm……应该算是生成函数吧？令A的位置的权值为下标，B的位置的权值为下标的相反数，那么只...
