题目描述    每种商品体积为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<=x<1时，当x>1时，不收敛   所以,   所以...

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

题意：   给定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),也是交点个数。   如果把圆看成一张图(圆弧也是边)，   点由直线交点...