本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}