不知名题目

这个是当时考试碰见的。

题目描述

已知n\in[0,10^{18}].b,k\in[1,10^5]\sum_{i=1}^{n}{C_i^kb^i}

解题报告

当时有的人用什么奇怪的解法过去了记不清了,只记得讲的解法,大概是构造数列使复杂度化为k线性相关。
S_k=\sum_{i=1}^{n}{C_i^kb^i}

\to bS_k=\sum_{i=2}^{n+1}{C_{i-1}^kb^i}

\to (1-b)S_k=\sum_{i=2}^{n}{C_{i-1}^{k-1}b^i-C_n^kb^{n+1}}
\to S_k=\frac{1}{1-b}[-C_n^kb^{n+1}+b\sum_{i=1}^{n-1}C_{i}^{k-1}b^i]
\to S_k=\frac{1}{1-b}[-C_n^kb^{n+1}+bS_{k-1}-b^{n+1}C_n^{k-1}]
\to S_k=\frac{1}{1-b}[-C_{n+1}^{k}b^{n+1}+bS_{k-1}]

 

发表评论

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