给定多项式 \(f(x)=\sum_{i=1}^ma_ix^{b_i}\)。定义 \(f_1(x)=f(x)\)，\(f_n(x)=f(f_{n-1}(x))\)。
就是初始将 \(x\) 代入多项式，再将结果代入，总共代入 \(y\) 次。
根据提示发现模数 \(p\) 是 \(10^5\) 级别的，于是对于 \(x\in[0,p-1]\) 暴力计算出 \(f(x)\bmod p\) 的值。然后既然知道了每个 \(x\) 带入一次的值，之后倍增处理一下即可。时间复杂度 \(O(mp\log p+(p+q)\log y)\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
int m,q,p,a[25],b[25],f[MAXN][25];
inline long long ksm(long long a,int b)
{
long long ans=1;
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p,b>>=1;
}
return ans;
}
int main()
{
#ifdef ONLINE_JUDGE
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
#endif
cin>>m>>q>>p;
for(int i=1;i<=m;++i) cin>>a[i]>>b[i];
for(int x=0;x<p;++x)
{
long long sum=0;
for(int i=1;i<=m;++i)
sum+=ksm(x,b[i])*a[i]%p;
f[x][0]=sum%p;
}
for(int j=1;j<25;++j)
for(int i=0;i<p;++i)
f[i][j]=f[f[i][j-1]][j-1];
while(q--)
{
int x,y;cin>>x>>y;x%=p;
for(int j=24;j>=0;--j)
if(y&(1<<j)) x=f[x][j];
cout<<x<<'\n';
}
return 0;
}