自动搬运

查看原文

来自洛谷，原作者为

	Dreamunk **

搬运于2025-08-24 22:10:47，当前版本为作者最后更新于2020-02-22 15:20:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

冷静分析，冷静分析……

题目

加强前的详细思路见此处

为了方便，记 $M = 998244353$。

记 $F_k(n)=\sum_{1\le i<j\le n}(i+j)^k$，则答案就是 $\frac{2}{n}F_k(n)$。

发现 $F_k(n)$ 是个关于 $n$ 的 $(k+2)$ 次多项式，所以我们要拿 $(k+3)$ 个点值来插它。

根据拉格朗日插值，得到式子

$F_k(n)=\sum_{i=1}^{m+3}F_k(i)\prod_{j\ne i}\frac{n-j}{i-j}$

$=\sum_{i=1}^{m+3}F_k(i)\frac{1}{(i-1)!}\frac{1}{(m+3-i)!}(-1)^{m+3-i}\prod_{j=1}^{i-1}(n-j)\prod_{j=i+1}^{m+3}(n-j)$

。求和号后面的每个东西都可以预处理，于是我们就求出了 $F_k(n) \mod M$。

接下来还要乘个 $\frac{2}{n}$，分几种情况讨论：

一、$1\le n<M$

这时候 $n$ 存在逆元，直接乘就好了。于是我们解决了没加强的版本。

二、$n=M$

这时候算出的 $F_k(n) \mod M$ 其实也是对的（实际上，这时候 $F_k(n) \mod M=0$）。

问题在于最后还要乘个 $\frac{2}{n}$，而 $n$ 这时候没有逆元。

首先想到看看上面有没有可以消去的 $n$ ，但似乎并没有找到。

注意到这个拉格朗日插值，我们取的点是 $1$ 到 $k+3$。换成 $0$ 到 $k+2$ 试试看？

首先可以得到 $F_k(0)=0$。

然后发现式子变成这样：

$F_k(n)=\sum_{i=0}^{m+2}F_k(i)\frac{1}{i!}\frac{1}{(m+2-i)!}(-1)^{m+2-i}\prod_{j=0}^{i-1}(n-j)\prod_{j=i+1}^{m+2}(n-j)$

那 $\prod_{j=0}^{i-1}(n-j)$ 这里，不就有一个 $n$ 吗？把它消掉就行了。

Wait...你说 $i=0$ 的时候没有 $n$ 怎么办？$F_k(0)=0$，所以 $i=0$ 的时候对答案没有贡献，直接让循环从 $1$ 开始就好了。

（尽管在计算的时候没有贡献，但我们仍然是拿 $(k+3)$ 个点值来插的，只不过在 $0$ 处的点值为 $0$ 而已。）

于是得到的式子是

$\frac{1}{n}F_k(n)=\sum_{i=1}^{m+2}F_k(i)\frac{1}{i!}\frac{1}{(m+2-i)!}(-1)^{m+2-i}\prod_{j=1}^{i-1}(n-j)\prod_{j=i+1}^{m+2}(n-j)$

乘个 $2$ 就是答案了。

三、$n>M$

$n>M$ 时，$n$ 的答案和 $n\mod M+[n\mod M=0]\cdot M$ 的答案是一样的，输入的时候直接取模就好了。

这个证明其实并不像看起来一样简单，可以思考一下。

#include<cstdio>
typedef long long ll;
const int A=1e7+37,M=998244353;
inline int Pow(int a,int m){int s=1;for(;m;m>>=1)m&1?s=(ll)s*a%M:0,a=(ll)a*a%M;return s;}
int n,m,f[A+A],g[A],func[A],t0[A],t1[A],invf[A],np[A+A],p[1300000],k,ans;
inline int Read(){
	int a=0;char c=getchar();
	for(;c>57||c<48;c=getchar());for(;c>47&&c<58;a=(a*10ll+c-48)%M,c=getchar());
	return a;
}
int main(){
	n=Read();if(!n)n+=M;
	scanf("%d",&m);
	f[1]=1;
	for(int i=2;i<=m+m+3;i++){
	  if(!np[i])p[++k]=i,f[i]=Pow(i,m);
	  for(int j=1;j<=k&&i*p[j]<=m+m+3;j++){
		np[i*p[j]]=1;
		f[i*p[j]]=(ll)f[i]*f[p[j]]%M;
		if(i%p[j]==0)break;
	  }
	}
	for(int i=1;i<=m+m+3;i++)f[i]=(f[i]+f[i-1])%M;
	func[0]=1,t0[0]=1;
	for(int i=1;i<=m+2;i++){
	  t0[i]=(ll)t0[i-1]*(n-i)%M;
	  func[i]=(ll)func[i-1]*i%M;
	  g[i]=((ll)g[i-1]+f[2*i-1]-f[i]+M)%M;
	  if(n==i)return 0*printf("%lld\n",g[i]*2ll*Pow(n,M-2)%M);
	}
	invf[m+2]=Pow(func[m+2],M-2),t1[m+2]=n-(m+2),t1[m+3]=1;
	for(int i=m+2;i;i--){
	  t1[i-1]=(ll)t1[i]*(n-i+1)%M;
	  invf[i-1]=(ll)invf[i]*i%M;
	}
	for(int i=1;i<=m+2;i++)
	  ans=(ans+(ll)g[i]*t0[i-1]%M*t1[i+1]%M*invf[i]%M*invf[m+2-i]*(m+2-i&1?-1:1)%M+M)%M;
	printf("%d\n",ans*2%M);
	return 0;
}