[CF622F]The Sum of the k-th Powers

题目大意：给你$n,k(n\leqslant10^9,k\leqslant10^6)$，求：
$$
\sum\limits_{i=1}^ni^k\pmod{10^9+7}
$$

题解：可以猜测是一个$k+1$次的多项式，可以求出$x$在$0,1,2,3,\dots,k+1$时的值，设为$s_0,s_1,\dots,s_{k+1}$，根据拉格朗日插值公式：

$$
\begin{align*}
f_n&=\sum\limits_{i=0}^{k+1}y_i\prod\limits_{j=0,j\not=i}^{k+1}\dfrac{n-x_j}{x_i-x_j}\\
&=\sum\limits_{i=0}^{k+1}(-1)^{k-i+1}s_i\dfrac{n(n-1)\cdots(n-k-1)}{(n-i)i!(k-i+1)!}\\
\end{align*}
$$
然后预处理出阶乘就可以了。注意，因为取了$0$这个点，若$k=0$会答案出错，可以选择特判或取$1\sim k+2$几个点，还有，当$k\leqslant n-1$时，式子为零，直接输出即可。

卡点：无

C++ Code：

#include <cstdio>

#define maxn 1000010

const int mod = 1e9 + 7;

inline int pw(int base, int p) {

	static int res;

	for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;

	return res;

}

inline int inv(int x) {return pw(x, mod - 2);}

inline void reduce(int &x) {x += x >> 31 & mod;}

int n, k, ans;

int fac[maxn], s[maxn], prod = 1;

int main() {

	scanf("%d%d", &n, &k);

	if (k == 0) {

		std::printf("%d\n", n);

		return 0;

	}

	for (int i = 0; i <= k + 1; i++) {

		prod = static_cast<long long> (n - i) * prod % mod;

		s[i] = pw(i, k);

	}

	fac[0] = 1;

	for (int i = 1; i <= k + 1; i++) {

		fac[i] = static_cast<long long> (fac[i - 1]) * i % mod;

		reduce(s[i] += s[i - 1] - mod);

		if (n == i) {

			std::printf("%d\n", s[i]);

			return 0;

		}

	}

	for (int i = 1; i <= k + 1; i++) {

		reduce(ans += s[i] * static_cast<long long> (prod) % mod * inv(n - i) % mod * inv(fac[i]) % mod * inv(fac[k - i + 1]) * (k - i + 1 & 1 ? -1 : 1) % mod - mod);

		reduce(ans);

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

[CF622F]The Sum of the k-th Powers

最新文章

热门文章