icontofig | 发布于 2019-10-12 15:07:44 | 阅读量 118 | NTT 数学 组合数 生成函数
发布于 2019-10-12 15:07:44 | NTT 数学 组合数 生成函数
HAOI2018 染色 NTT 组合数 生成函数
题解 首先声明……其实我们的答案跟Wi'>WiWiW_i没太大关系,这一部分只需要在最后的时候对应乘上即可,此题最核心的部分是计算选择了i种颜色的方案数。 首先我们来看如果我们选择了i种颜色使它们恰好出现了S次,那么选择颜色种类的方案数即为Cmi'>CimCmiC_m^i,然后我们去用这i个颜色涂这n个位置的时候,实际上就是一个可重排列的计算数,方案总数为n!(S!)i∗(n−i∗S)!'>n!(S!)i∗(n−i∗S)!n!(S!)i∗(n−i∗S)!\frac{n!}{{(S!)}^i * (n-i*S
继续阅读
icontofig | 发布于 2019-09-26 19:59:05 | 阅读量 510 | 生成函数 NTT
发布于 2019-09-26 19:59:05 | 生成函数 NTT
luogu P3321 BZOJ 3992 [SDOI2015]序列统计 NTT + 生成函数 + 快速幂
题解如果你曾经经过大量的FFT/NTT的生成函数训练,应该一眼能够看出这道题一定是个多项式卷积用NTT优化…… 如果是相加的话,我们可以直接设多项式S = Σaixi,(生成函数在这)其中ai表示数字i出现过多少次。 如果我们是选2个数的话,对于每一个和的方案数,很明显就是将S卷上S,然后取对应多项式项的系数即为方案数。 因为这个题是乘积,而且对于乘积还有对质数m取模操作,所以我们不能简单的按照上面的方法进行生成函数构造。 如何解决乘积问题呢? 我们知道多项式FFT/NTT都是建立在指数(下标)相加的基础上(也就是普通的多项式乘法的法则)进行的,所以我们想能不能把乘积变成加法,这样就可以按照经
继续阅读
icontofig | 发布于 2019-09-22 21:13:56 | 阅读量 392 | FFT 字符串 生成函数
发布于 2019-09-22 21:13:56 | FFT 字符串 生成函数
BZOJ 3160 万径人踪灭 FFT + 回文自动机 + 生成函数
题目大意 给定一个字符集仅含a和b的字符串s,求字符串中不连续的回文子序列个数mod 1000000007的值。 题解如果是连续的回文子序列,也就是回文串,那就很好求了,直接运用Manacher算法就可以了。 但是这题是让算所有的不连续的回文子序列…… 然而这个是没法直接算出来的…… 所以我们反过来想,我们可以把所有回文子序列的数量求出来,然后减去回文子串的数量,就是不连续的回文子序列的数量。 上面说了,如果是回文子串的数量,可以直接用Manacher算法算出来。 所以现在我们考虑的就是全体回文子序列的数量该怎么算。 对一个回文子序列,一定有一个中心,假设两个对应字符位置分别为x,y
继续阅读
icontofig | 发布于 2019-09-21 15:29:50 | 阅读量 350 | FFT 生成函数
发布于 2019-09-21 15:29:50 | FFT 生成函数
The Preliminary Contest for ICPC Asia Shanghai 2019 C.Triple FFT + 生成函数
题目大意给定一个正整数n,有三个数组A,B,C,每个数组有n个数,求问有多少个三元组(i,j,k)满足|Ai-Bj|≤Ck,|Ck-Bj|≤Ai,|Ai-Ck|≤Bj 题解首先我们发现,其实三元组满足的条件其实非常像三角形的构成条件,所以我们可以叙述成 “最小值 + 中间值 ≤ 最大值” 满足这样的三元组个数。 官方题解是正着算的,然后还有什么去重什么麻烦的东西,看起来令人头大…… 所以我们为何不反过来算呢? 首先所有的取法总数是n3,然后我们只需要计算以下不满足的三元组总数即可了。 但是怎么做? 大概的思路就是对于某一个数组中的所有数,我们对每一个进行枚举,把当前枚举的数作为三元组的最大值,
继续阅读