问题：

求从 $1$ 到 $N$ 的 $K$ 次方和，即： $$ \sum_{i=1}^ni^k $$

1、线性筛法

首先 $id^k(x)$ 是一个完全积性函数，所以可以线性筛，然后再求一个前缀和。

时间复杂度： $O(n\log k/\ln n+n)$

不需要逆元。

2、递推差分表法

$$ (n+1)^{k+1}-n^{k+1}=C_{k+1}^kn^k+C_{k+1}^{k-1}n^{k-1}++\cdots+C_{k+1}^1n^1+C_{k+1}^0n^0 $$

累加得到： $$ (n+1)^{k+1}-1=C_{k+1}^1\sum_{i=1}^ni^k+C_{k+1}^2\sum_{i=1}^ni^{k-1}+\cdots+C_{k+1}^k\sum_{i=1}^ni+n $$ 移项再做一次除法： $$ \sum_{i=1}^ni^k=\frac{1}{k+1}[(n+1)^{k+1}-(C_{k+1}^2\sum_{i=1}^ni^{k-1}+\cdots+C_{k+1}^k\sum_{i=1}^ni+n+1)] $$ 设： $$ S(n,k)=\sum_{i=1}^ni^k $$ 那么有递推式： $$ S(n,k)=\frac1{k+1}[(n+1)^{k+1}-(C_{k+1}^2S(n,k-1)+\cdots+C_{k+1}^kS(n,1)+n+1)] $$ 这样递推就可以了。

时间复杂度 $O(k^2)$ 。

需要逆元。

时间复杂度不是很优秀。

3、拉格朗日插值法

观察差分表法的式子，我们发现 $S(n,k)$ 一定可以表示为一个 $n$ 的 $k+1$ 次多项式，共 $k+2$ 项。

那我们如果构造出了这个多项式，就可以把 $n$ 代入求和。

考虑不经过差分表法的转化，直接用拉格朗日插值把原多项式插出来。

设 $\begin{align}f(n)=\sum_{i=1}^ni^k\end{align}$ $$ f(n)=\sum_{i=0}^{k+1}f(i)\times \frac{\begin{align}\prod_{j=0,i\ne j}^{k+1}(n-j)\end{align}}{\begin{align}\prod_{j=0,j\ne i}^{k+1}(i-j)\end{align}} =\sum_{i=0}^{k+1}f(i)\times \frac{n!/(n-i)!\times(n-i-1)!/(n-k-2)!}{i!/(k+1-i)!\times(-1)^{k+1-i}} $$ 于是 $f(i),i\in[0,k+1]$ 可以暴力求，或者线性筛也可以，但是快速幂常数小，后面那个东西维护一下连乘积还有阶乘的逆元就可以了。

时间复杂度 $O(n+k)$ 。

需要逆元。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll L,R,k;

#define MAXK 1000010

ll pows[MAXK];

ll fac[MAXK],inv[MAXK];

#define MOD 998244353

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

ll p[MAXK];

ll lagrange(ll n)

{

	ll ans = 0;

	if(n <= k + 1)ans = pows[n];

	else

	{

		p[0] = n;

		for(ll i = 1;i <= k + 1;++i)

		{

			p[i] = p[i - 1] * (n - i) % MOD;

		}

		for(ll i = 0;i <= k + 1;++i)

		{

			ll res = pows[i];

			res = res * p[k + 1] % MOD;

			res = res * power(n - i,MOD - 2) % MOD;

			res = res * inv[i] % MOD;

			res = res * inv[k + 1 - i] % MOD;

			ans = ((ans + res * (((i + k) & 1) ? 1 : MOD - 1)) % MOD + MOD) % MOD;

		}

	}

	return ans;

}

int main()

{

	freopen("count.in","r",stdin);

	freopen("count.out","w",stdout); 

	scanf("%lld%lld%lld",&L,&R,&k);

	for(ll i = 1;i < MAXK;++i)pows[i] = power(i,k);

	for(ll i = 1;i < MAXK;++i)pows[i] = (pows[i] + pows[i - 1]) % MOD;

	fac[0] = 1;

	for(ll i = 1;i < MAXK;++i)fac[i] = fac[i - 1] * i % MOD;

	inv[MAXK - 1] = power(fac[MAXK - 1],MOD - 2);

	for(ll i = MAXK - 2;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % MOD;

	cout << (lagrange(R) - lagrange(L - 1) + MOD) % MOD << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}