[十二省联考2019]皮配

首先我们可以看成两个变量的生成函数,答案就是每一个城市对应的生成函数乘积中的合法部分,合法部分只有$O(M^2)$个,在可接受范围内。
先考虑$k=0$怎么做,我们写出生成函数,发现$x$和$y$分别独立,我们分别做一次分治FFT或者暴力乘法即可。
当$k>0$时,我们可以把不相关的项提出来,也就是说我们现在只有$O(k)$个只有两项的多项式的乘积要特殊处理,而且第二维生成函数的总位数是$O(\max(s_i)k)$的,我们可以直接暴力乘起来。
至于怎么合并两个矩阵,就是只需要枚举其中一个,另外一个用二维前缀和直接统计进答案即可。

Tagged with:

发表评论