题解：P5553 电学实验

题解区大佬们的拉格朗日插值看的本蒟蒻一脸恐慌，那就写一篇亲民的题解吧。

题意

题面较长，核心是要用一个 n-1 次多项式 P(x) 拟合点 (i,\frac{1}{i})，然后计算 P(n+1) 在模 998244353（以下简称 MOD）意义下的值。

思路

直接求该多项式的值是困难的，我们不妨先判一下下无解的情况。

以上不懂的请自行查阅有关逆元的知识。

判完无解之后如何考虑呢？我们可以分类讨论。考虑能覆盖所有情况的分类——奇偶性讨论。

在讨论之前，我们不妨先通过构造转化一下。

令 Q(x)=x\times P(x)-1，其中 P(x) 是我们要拟合的多项式。根据题意，P(i)=\frac{1}{i}，所以 Q(i)=i\times\frac{1}{i}-1=0 对于 i=1,2,\dots,n 成立。因此，我们可以将 Q(x) 转化为：Q(x)=C\times(x-1)(x-2)\dots(x-n)，其中 C 是一个常数。

我们构造 Q(x) 有什么用呢？当然是为了方便计算 P(n+1) 啦！根据 Q(x) 的定义，有：

Q(n+1)=(n+1)\times P(n+1)-1

所以：

P(n+1)=\frac{Q(n+1)+1}{n+1} P(n+1)=\frac{C\times(n+1-1)(n+1-2)\dots(n+1-n)+1}{n+1} P(n+1)=\frac{C\times n!+1}{n+1}

经过以上推导，我们就可以开始愉快的分类讨论了。

• n 为偶数：

当 n 为偶数时，我们考虑 Q(0) 的值。

Q(0)=C\times(-1)\times(-2)\times\dots\times(-n)=C\times(-1)^n\times n!

由于 n 是偶数，所以 (-1)^n=1，因此：

Q(0)=C\times n!

同时，根据 Q(x) 的定义，Q(0)=0\times P(0)-1=-1。因此：

C=\frac{-1}{n!}

带入 P(n+1) 的表达式：

P(n+1)=\frac{(\frac{-1}{n!})\times n!+1}{n+1}=\frac{-1+1}{n+1}=0

所以，当 n 为偶数时，P(n+1)=0。

• n 为奇数：

同理，当 n 为奇数时，考虑 Q(0) 的值。

Q(0)=C\times(-1)^n\times n!=-C\times n!

又因为 Q(0)=-1，所以 -C\times n!=-1，C=\frac{1}{n!}。

带入 P(n+1)，得：

P(n+1)=\frac{\frac{1}{n!}\times n!+1}{n+1}=\frac{2}{n+1}

所以，当 n 为奇数时，P(n+1)=\frac{2}{n+1}（模 MOD 意义下）。

注意此时要先计算 n+1 的逆元。

Code

以下是短的吓人的代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=998244353;
ll ksm(ll a,ll b,ll mod){
    ll res=1;
    a%=mod;
    while(b>0){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin>>T;
    while(T--){
        ll n;
        cin>>n;
        //判断n+1是否大于等于模数
        if(n>=MOD){
            cout<<"-1\n";
            continue;
        }
        //如果n是偶数，输出0
        if(n%2==0){
            cout<<"0\n";
            continue;
        }
        //如果n是奇数，计算2/(n+1) mod 998244353
        //先计算逆元
        ll inv=ksm(n+1,MOD-2,MOD);
        ll ans=(2*inv)%MOD;
        cout<<ans<<"\n";
    }
}