3654.poly
2026-10-20
题解
是我不会做的题了。
观察数据范围发现模数 p 很小,同时注意到 f(x)modp=f(xmodp)modp,而因为 m≤20,我们可以直接预处理出所有 f(x),x∈[0,p)。
这样的话由于无论从 0 还是 1 开始,都是 1,0,1,0,⋯ 循环,不妨令 g(x)=f0(f1(x)),那么直接把所有 g 倍增处理一下即可。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define LOCAL
namespace IO {
#ifndef LOCAL
#define SIZE (1<<20)
char in[SIZE] , *p1=in , *p2=in , out[SIZE] , *p3=out;
#define getchar() (p1==p2 && (p2=(p1=in)+fread(in,1,SIZE,stdin)) , p1==p2 ? EOF : *p1 ++)
#define flush() (fwrite(out,1,p3-out,stdout) , p3=out)
#define putchar(c) (p3==out+SIZE && flush() , *p3 ++ = c)
class Flush{public: ~Flush(){flush();} } ___;
#endif
inline int read() {
int x = 0 , f = 1;
int c = getchar();
while(c < '0' || '9' < c) {
if(c == '-') f = -1;
c = getchar();
}
while('0' <= c && c <= '9') {
x = (x<<3) + (x<<1) + c - '0';
c = getchar();
}
return x*f;
}
inline void write(int x , bool f = true) {
if(x < 0) x = -x , putchar('-');
static short stk[80] , top; top = 0;
do {stk[++ top] = x%10 , x/=10; } while(x);
while(top) putchar(stk[top --] | '0');
if(f) putchar('\n');
else putchar(' ');
}
#ifndef LOCAL
#undef getchar
#undef SIZE
#undef flush
#undef putchar
#endif
} using namespace IO;
const int M = 25 , P = 1e5+10;
int m[2] , q , p;
int a[2][M] , b[2][M];
int f[2][P] , g[P][30];
inline int qpow(int a , int b) {
int res = 1;
while(b) {
if(b&1) res = 1ll * res * a % p;
a = 1ll * a * a % p; b >>= 1;
}
return res;
}
inline void add(int& x , int y) {
x += y;
if(x >= p) x -= p;
}
int main() {
m[0] = read(); m[1] = read(); q = read(); p = read();
for(int i = 1 ; i <= m[0] ; i ++)
a[0][i] = read() , b[0][i] = read();
for(int i = 1 ; i <= m[1] ; i ++)
a[1][i] = read() , b[1][i] = read();
for(int k = 0 ; k <= 1 ; k ++)
for(int i = 0 ; i < p ; i ++)
for(int j = 1 ; j <= m[k] ; j ++)
add(f[k][i] , 1ll * a[k][j] * qpow(i,b[k][j]) % p);
for(int i = 0 ; i < p ; i ++)
g[i][0] = f[0][f[1][i]];
for(int j = 1 ; j <= 29 ; j ++)
for(int i = 0 ; i < p ; i ++)
g[i][j] = g[g[i][j-1]][j-1];
while(q --) {
int x = read() % p , y = read() , s = read();
if(!s) x = f[s][x] , y -- , s ^= 1;
for(int j = 29 ; j >= 0 ; j --) {
if(y >= (1<<(j+1))) {
x = g[x][j]; y -= (1<<(j+1));
}
}
if(y) x = f[1][x];
write(x);
}
return 0;
}