自然数幂和

自然数幂和问题,是给定 $n, k$ ,求
$$ f_k(n)=\sum_{i=1}^{n}i^k $$
之前在伯努利数备忘录里面写了一点自然数幂和
后来又看到几个大爷在博客里面写了自然数幂和,所以又开一篇文章来引用一下其他的方法,我都只是简要提一下思路,具体方法在链接里

Miskcoo 的方法

以下思路与图片来自miskcoo 的博客
感觉思路新奇,明明看上去很简单,但是我怎么就想不到
首先考虑 $S_n=\sum_{i=1}^{n}i^2$ 应该怎样求解
1.png
继续阅读

BZOJ4475 子集选取

题解

此题正解是找规律
答案很好猜,就是 $2^{nk}$
思考推导过程
一个重要的技巧: 我们用二进制串表示一个子集,那么我们发现每一位都是相互独立的,且贡献只需要乘法原理乘起来就可以了
现在题目变成如果在 $\frac{(k+1)k}{2}$ 个位置上填 $0,1$ ,如果 $(i,j-1),(i-1,j)$ 都是 $1$ ,那么 $(i,j)$ 可 $1$ 可 $0$ ,否则只能填 $0$ ,求方案数
继续阅读