ABC137F Polynomial Construction题解

Iceturky · 2024-07-16 23:12:10 · 题解

有两种做法。

第一种：

观察问题，等价于求一个 p-1 次函数 f(x) 满足 f(i)\equiv a_i\pmod{p} 。用拉格朗日插值法求即可。

第二种：

费马小定理 ：x^{p-1}\equiv 1\pmod{p}(p\ is\ prime\land p \nmid x) 。

考虑通过这个来构造 g_i(x)=[x=a_i] 。

也很简单，对于 a_i=1 ， g_i(x)=1-(x-i)^{p-1} ，a_i=0 ， g_i(x)=0 即可。

然后答案即为 f(x)=\sum_{i=0}^{p-1}g_i(x) 。

只写了第二种。

code

const int N=3e3+5;
int mod;

int a[N];

int J[N],inv[N];

int qp(int x,int y){
    int ans=1;
    for(int i=1;i<=y;i<<=1){
        if(i&y)
            ans=ans*x%mod;
        x=x*x%mod;
    }return ans;6
}

int b[N];

int C(int n,int m){
    return J[n]*inv[n-m]%mod*inv[m]%mod;
}

signed main(){
    int p=read();
    mod=p;
    J[0]=inv[0]=1;
    for(int i=1;i<p;i++)
        J[i]=J[i-1]*i%mod;
    inv[p-1]=qp(J[p-1],mod-2);
    for(int i=p-2;i>=1;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=0;i<p;i++){
        if(read()){
            for(int j=p-1;j>=0;j--)
                b[j]-=qp(-i,p-1-j)*C(p-1,j)%mod;
            b[0]+=1;
        }
    }
    for(int i=0;i<p;i++)
        print((b[i]%mod+mod)%mod),pc(' ');pc('\n');
    return 0;
}