题解：P5553 电学实验

· · 题解

思路

这道题就是定义 f(x) = x^{-1} \pmod{998244353} ，求 f(n + 1) \mod{998244353} ，很容易就可以发现是拉格朗日插值法，但是每次都做一遍拉格朗日插值法会超时，我们就可以把拉格朗日插值法的公式化简一下：

\begin{aligned} f(n + 1) &= \sum_{i=1}^n \frac{1}{i} \prod_{j \ne i}^n \frac{n + 1 - j}{i - j} \\ f(n + 1) &= \sum_{i=1}^n \frac{1}{i} \sdot \frac{n!/(n + 1 - i)}{(i - 1)! \sdot (-1)^{n - i} \sdot (n - i)!} \\ f(n + 1) &= \sum_{i=1}^n \frac{n!}{i! \sdot (n - i)!} \sdot \frac{(-1)^{n - i}}{(n + 1 - i)} \\ f(n + 1) &= \sum_{k=0}^{n - 1} \binom{n}{k} \sdot \frac{(-1)^k}{k + 1} \\ f(n + 1) &= \int_0^1 \sum_{k=0}^{n - 1} \binom{n}{k}(-x)^k \mathop{}\!\mathrm{d} x \\ f(n + 1) &= \int_0^1 [(1 - x)^n - (-x)^n ]\mathop{}\!\mathrm{d} x \\ f(n + 1) &= \frac{1}{n + 1} - \frac{(-1)^n}{n + 1} \\ f(n + 1) &= \frac{1 - (-1)^n}{n + 1} \end{aligned}

当 n + 1 为偶数时 f(n + 1) = 0 ，当 n + 1 为奇数时 f(n + 1) = \frac{2}{n + 1} ，但是当 n \ge 998244353 时，逆元未定义，输出 -1 。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;
int g,n;
int ksm(int a,int b,int mod=MOD)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>g;
    while(g--)
        cin>>n,cout<<(n>=MOD?-1ll:((n&1)?2*ksm(n+1,MOD-2)%MOD:0ll))<<'\n';
    return 0;
}