ZigZagK的博客
[生成函数+分治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的位置的权值为下标的相反数,那么只...