Skip to main content

__debug's Home Keep it simple, stupid

[BZOJ 2655] calc

康复训练… 小清新计数题.

定义一个序列的权值为所有元素之积. 现在给定 \(a, n, p\), 求所有由 \(n\) 个 \([1, a]\) 中的整数组成且无重复元素的序列的权值之和, 答案对一个质数 \(p\) 取模.

\(n \le 500, a < p \le 10^9\)

Solution #1

第一个想法就是容斥.

定义 \(S_d = \sum_{i=1}^{a} i^d\).

设长度为 \(i\) 的序列的答案为 \(f(i)\), 若直接用 \(S_1 f(i-1)\) 来表示 \(f(i)\), 会将"最后一个值出现两次"的贡献也算进去, 这显然是多余的. 不过显然可以用 \(S_2 f(i-2)\) 来把这个贡献容斥掉, 但是这样就引入了"最后一个值出现三次"的贡献…

"天长地久有时尽, 此恨绵绵无绝期."

不过没关系, 上面这个过程到了 \(S_i f(0)\) 便结束了. 但是还有容斥系数的问题. 仔细分析之后发现这里的容斥系数是下降幂(也就是排列). 最后式子如下:

$$f(i) = \sum_{j=0}^{i-1} (-1)^{i-j-1} (n-1)^{\underline{i-j}} S_{i-j} f(j)$$

Solution #2

由于 \(S_{i-j}\) 是一个关于 \(a\) 的 \(i-j+1\) 次多项式, \(f(i)\) 其实是一个 \(2i+1\) 次多项式!

于是关于 \(a\) 插值就好了… 新姿势 get.

Comments

Comments powered by Disqus