【Codeforces 1155E】Guess the Root | Mrsrz's blog

拉格朗日插值

题目大意：

这是一道交互题。给定一个不超过 $10$ 次的多项式 $F(x)$，你可以询问不超过 $50$ 次某个点的点值。求 $x$ 满足 $F(x)=0$。在模 $10^6+3$ 意义下进行。

题解：

我们并不需要知道这个多项式的次数，由于至多 $10$ 次，我们就当它是 $10$ 次多项式。然后求出 $12$ 个点的点值后，就可以拉格朗日插值，得到多项式的各项系数了。

然后由于模数较小，直接代入所有 $x$ 求值即可。

实际上如果插值时点值连续，也可以不得到多项式的各项系数，可以直接做到线性求值。

Code：

#include<iostream>
using namespace std;
const int md=1e6+3;
typedef long long LL;
int a[14],iv[md+1],pre[14],suf[14],fac[14];
inline int lagrange(int x){
    int ret=0;
    pre[0]=suf[13]=1;
    for(int i=1;i<=12;++i)pre[i]=(LL)pre[i-1]*(x-i+md)%md;
    for(int i=12;i>=1;--i)suf[i]=(LL)suf[i+1]*(x-i+md)%md;
    for(int i=1;i<=12;++i){
        int fz=pre[i-1]*(LL)suf[i+1]%md*a[i]%md;
        int fm=fac[12-i]*fac[i-1]%md*((i&1)?(md-1LL):1LL)%md;
        ret=(ret+(LL)fz*iv[fm])%md;
    }
    return ret;
}
int main(){
    iv[1]=1;
    for(int i=2;i<=md;++i)
        iv[i]=(md-md/i)*(LL)iv[md%i]%md;
    for(int i=*fac=1;i<=12;++i)fac[i]=fac[i-1]*i%md;
    for(int i=1;i<=12;++i){
        cout<<"? "<<i<<'\n';
        cout.flush();
        cin>>a[i];
    }
    for(int x=0;x<md;++x){
        int s=lagrange(x);
        if(s==0){
            cout<<"! "<<x<<endl;
            cout.flush();
            return 0;
        }
    }
    cout<<"! -1"<<endl;
    cout.flush();
    return 0;
}