【题解】[GenshinOI Round 3] P9816 少项式复合幂

题目链接

分析

首先这题给了很大的提示信息 注意 m 和 p 的范围 , 很自然的想到可以先把所有可能的 $f(x)$ 算出来.

思维误区

有些人在算完 $f(x)$ 之后可能就会去思考找环的问题，然后一些码力弱的大佬就会祭掉.

在经过仔细的观察之后 (大多数人其实一眼就看出来了罢 , 可以发现最终答案的计算是符合结合律的，或者说具有传递性？ 所以考虑倍增.

令 $fa[i][j]$ 表示 $f_{1<<j}(i)$ 的值，初始时把 $f[i][0]$ 算出来，后面就可以直接倍增了.

Code

#include <bits/stdc++.h>
#define int long long
const int N = 1e5+10;using namespace std;
int m,q,p;
int ksm(int a, int b){int ans = 1;while(b){if(b&1){ans = ans * a % p;}a = a*a%p;b >>= 1;}return ans;
}
int a[30],b[30];
int f[N];
int get(int x){int ans = 0;for(int i = 1; i <= m; i++){ans = (ans + a[i]*ksm(x,b[i])%p) % p;}return ans;
}
bool vis[N];
int belong[N];
vector<int> e[N];
int fa[N][30]; 
void init(){for(int i = 0; i < p; i++){fa[i][0] = get(i);}for(int i = 1;i <= 25; i++){for(int j = 0; j < p; j++){fa[j][i] = fa[fa[j][i-1]][i-1];}}
}
signed main(){cin >> m >> q >> p;for(int i = 1; i<= m; i++){cin >> a[i] >> b[i];a[i] %= p;} init();while(q--){int x,y;cin >> x >> y;x %= p;for(int i = 25; i >= 0; i--){if((1 << i) <= y) x = fa[x][i],y -= (1<<i);}cout << x << endl;}return 0;
}