luogu P5442 【XR-2】约定 (加强版)
Dreamunk
·
·
题解
冷静分析，冷静分析……
题目
加强前的详细思路见此处
为了方便，记 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
这个证明其实并不像看起来一样简单，可以思考一下。
```cpp
#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;
}
```