题目描述 每种商品体积为vi，都有105件，输出凑成1~m的体积的总方案数，输出可能会很大，请对大质数19260817取模 n,m,v<=5*10^4 解题思路 前置技能：FFT，多项式求逆，求ln，求exp，生成函数，牛顿迭代，泰勒展开，任意模数FFT等多项式基础姿势 推荐博客：https://blog.csdn.net/oi_Konnyaku/article/details/79682528 由于每种物品都有10^5件，就相当于这无限背包 所以可以对每种物品都做一个生成函数 当0&lt...

题意： 有m组，每组si个人(两两不同)，满足，求有多少种方案使得在每组中至少挑一人，可以凑出k个人来。 思路： n≤105说明这个数据范围支持log方的做法 考虑对每组都单独做一个生成函数 第j组的生成函数为， 这样的aixi表示的是选i个人时有ai种方案， 对于任意Fj(x)中的a0=0可以满足每组中至少挑一人的要求。 因此答案为， 就是把所有生成函数乘起来，取第k项系数，即为答案。 这里的多项式乘法可以做分治FFT 复杂度为O(n*logn*logm) 内容板块 数学 ： 生成函数 多项式 分治FFT ...

题意： 给定n个点的一棵树，根为1。每次操作随机选点，把选中的点的子树删去。当所有点被删去则停止。求操作次数的期望。 思路： 按照套路，根据期望的线性性，和的期望等于期望的和， ,期望步数可以等价于对每个点的期望贡献单独算后求和。 考虑一个点被删除时只有两种情况(默认根的深度为1)： (1).选中自己被删除，此时贡献为1，概率为。 (2).选中该点的祖先，此时贡献为0，贡献应该被算在祖先处，概率为。 PS：删除其他点并不会导致该点被删除，不会对它的概率产生影响。 因此单点的期望贡献为 所以 复杂度O(nlog mod),dfs求...

题目大意 一个圆上有n个点，在n个点中间两两连边，求最多产生多少个区域？ 视频讲解： 3B1B视频讲解 https://www.bilibili.com/video/av19849697 力推3B1B视频 思路： 首先在圆上去n个点， 要是n个点产生的区域数最大， 就必须是任意3条直线不交于一点。 也就是园内任意一点最多只有两条直线经过。 在圆上的n个点会连出C(n,2)条直线。 任意一个圆内交点都可以有圆上四点构成的四元组唯一对应， 那么无序四元组的个数为C(n,4),也是交点个数。 如果把圆看成一张图(圆...