一个式子

回复帖子

@ducati  2021-05-04 11:33 回复

$$\sum_{i=1}^n \sum_{j=1}^n {x \choose i} {i \choose j}{x-i \choose i-j} f_i^{\ 2} \times j^{n(m-2)}$$

$f$ 是一个给定的数组,然后上面这个式子怎么快速计算啊 /kk

求 $O(n \sqrt n)$ 或 $O(n \log^2 n)$ 或 $O(n \log n)$ 或 $O(n)$ 或 $O(1)$ 的做法。

@ducati  2021-05-04 11:35 回复 举报

感觉这个式子很难搞,我已经使出全身解数了依然推不出来

@ftiasch 2021-05-04 12:14 回复 举报

@ducati 先问问 111D 是哪个题,给个链接可好。

再问问 $x$ 是不是给定的常数?

@Verdandi 2021-05-04 12:20 回复 举报

随便胡的,不知道对不对

设 $g_k=k^{n(m-2)}$, $sum=\sum_{i=1}^n g_i$

$$ =\sum_{i=1}^n f_i^2{x\choose i}\sum_{j=1}^n{i\choose j}{x-i\choose i-j}g_j $$

易知 $j$只能枚举到 $i$终止,因此改写第二个 $\sum$的上标为 $i$。

然后由范德蒙德卷积 $\sum_{i=1}^n{n\choose i}{m\choose k-i}={n+m\choose k}$可得

$$ =\sum_{i=1}^nf_i^2{x\choose i}^2\sum_{j=1}^n g_j $$

$$ =\sum_{i=1}^n (f_i{x\choose i})^2\cdot sum $$

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。