题意

给定\(k\)个数,任意填在\(n\)个位置上,要求前\(\frac{n}{2}\)个数的和与后\(\frac{n}{2}\)个数的和相等,求方案数

分析

如果我们知道\(\frac{n}{2}\)个位置上填成和为\(x\)的方案数有\(ans_x\)种,那么显然最后的答案就是\(\sum ans_x^2\)。

于是现在的问题就是怎么求得\(ans_x\)。

引入生成函数\(\sum x^{d_i}\),那么显然\((\sum x^{d_i})^2\)的所有系数就是\(ans_x\)。

直接使用 FFT 似乎卡精度,又很难处理大浮点数取模的问题,所以就用 NTT 吧。

CF

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注