P5553

Aryper · 2021-08-18 16:28:04 · 个人记录

电学实验

这是一道数学题。

我们可以知道这个条件：

对于 (n-1) 次多项式 f(x)，有 f(x)=\dfrac{1}{x}(\forall x\in Z,x\in[1,n])。

那么现在我们要求的就是 f(n+1) 在模质数意义下的值。

我们令 g(x)=xf(x)-1，显然，g(x)=0(\forall x\in Z,x\in[1,n])。

那么我们可以把 g(x) 用 f(x) 的零点来表示，写成一个 n 次多项式。

令 g(x)=k\prod_{i=1}^n(x-i)，其中 k 为常数。

那么这个式子的常数项为 kn!(-1)^n，将式子乘开易知。

而 g(x)=xf(x)-1 的常数项为 -1，所以说就有 -1=kn!(-1)^n。

那么我们就可以得到 k=\dfrac{-1}{n!(-1)^n}=\dfrac{(-1)^{n-1}}{n!}。

那么我们就可以得到 g(x)=\dfrac{(-1)^{n-1}}{n!}\prod_{i=1}^n(x-i)。

令 x=n+1，得到 g(x)=\dfrac{(-1)^{n-1}}{n!}\prod_{i=1}^n(n+1-i)=\dfrac{(-1)^{n-1}}{n!}n!=(-1)^{n-1}。

然后我们又知道 g(x)=xf(x)-1，所以 (-1)^{n-1}=(n+1)f(n+1)-1。

所以 f(x)=\dfrac{(-1)^{n-1}+1}{n+1}。

快速幂算乘法逆元即可。

然后注意这个题的逆元不仅要求答案中的逆元有意义，还要求之前数据中的答案的逆元都有意义，所以说只要判断 n+1\ge 998244353 就能输出 -1 了；而 n+1<998244353 时，[1,n+1] 的所有整数都是与模数互质的，那么它们的逆元都有意义。

所有说我们并不需要判定互质还是不互质，直接与模数比较大小即可。

然而这个题还比较的神奇，就是说如果 n=998244352 时，按出题人的意思就是这个时候不应输出 -1，毕竟 \dfrac{0}{998244353}=0，而 0 本身在模意义下是有意义的。

所以说我们直接按照 n\ge 998244353 和 n<998244353 划分即可。

时间复杂度 O(T\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll mo=998244353;

ll T,n,b,p,ans;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    T=read();

    while(T--) {
        n=read();
        if(n>=mo) {
            write(-1);putchar('\n');
        }
        else
        if(n%2==0) {
            write(0);putchar('\n');
        }
        else {
            ans=2;p=mo-2;b=n+1;
            while(p>0) {
                if(p&1) ans=(ans*b)%mo;
                b=(b*b)%mo;p>>=1;
            }
            write(ans%mo);putchar('\n');
        }
    }

    return 0;
}