社区讨论

求最优复杂度+捞

wwuudii
灌水区参与者 6已保存回复 8

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@loy3ysbz
此快照首次捕获于
2023/11/14 17:05
2 年前
此快照最后确认于
2023/11/14 18:47
2 年前
查看原帖
原： https://www.luogu.com.cn/discuss/731286
求这个式子的最优复杂度，能不能做到优于 Θ(n2)\Theta(n^2)
完整过程：
fi=∑k=0iki2k+1f_i=\displaystyle\sum_{k=0}^i \frac{k^i}{2^{k+1}}
gi=∑j=0in!(n−i−j)!⋅i!⋅j!g_i=\displaystyle\sum_{j=0}^i \frac{n!}{(n-i-j)! \cdot i! \cdot j!}
ansn=∑i=1nfi⋅gi=∑i=1n∑j=1i∑k=1in!⋅ki(n−i−j)!⋅i!⋅j!⋅2k+1ans_n=\displaystyle\sum_{i=1}^n f_i \cdot g_i=\displaystyle\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^i \frac{n!\cdot k^i}{(n-i-j)!\cdot i!\cdot j!\cdot 2^{k+1}}
谢谢各位大佬！

回复

共 8 条回复，欢迎继续交流。

正在加载回复...