题解 P5050 【【模板】多项式多点求值】

脑子想想就知道这种两个log还常数大的题可以暴力艹啊 显然我们可以有一个O(nm)的秦九韶暴力，~~这个不会你就可以退役了~~ 开始卡常： 1.首先加register，能加的都加，出了存系数的那个不加 2.写快读快写，这个也不必非写fread，~~我就没写~~ 3.循环展开，实测4层最优 4.最后开个unsigned long long，你循环展开的过程量就不用取模了 5.写个unordered_map，如果已经算过了，就直接输出（这个貌似没卵用） 然后找个夜深人静的好时候，提交就好了，你就可以AC了 ```cpp #pragma GCC optimize("Ofast") #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<unordered_map> #define LL unsigned long long #define R register using namespace std; inline void read(int &x){ x=0;int f=1;char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); if(f==-1)x=-x; } char s[20];int cnt; inline void write(int x){ cnt=0; while(x){ s[++cnt]=x%10+'0'; x/=10; } for(R int i=cnt;i;--i)putchar(s[i]); putchar('\n'); } const int N=64005,mod=998244353; unordered_map<int,int> mp; int a[N]; int main(){ R int n,m,i,j,x; R LL b[17],c1,c2,c3,c4,now; read(n);read(m); for(i=0;i<=n;++i)read(a[i]); for(i=1;i<=m;++i){ read(x); if(mp[x]){write(mp[x]);continue;} b[0]=1; for(j=1;j<=16;++j)b[j]=b[j-1]*x%mod; now=a[n]; for(j=n-1;j-15>=0;j-=16){ c1=now*b[16]+a[j]*b[15]+a[j-1]*b[14]+a[j-2]*b[13]; c2=a[j-3]*b[12]+a[j-4]*b[11]+a[j-5]*b[10]+a[j-6]*b[9]; c3=a[j-7]*b[8]+a[j-8]*b[7]+a[j-9]*b[6]+a[j-10]*b[5]; c4=a[j-11]*b[4]+a[j-12]*b[3]+a[j-13]*b[2]+a[j-14]*b[1]; now=(c1+c2+c3+c4+a[j-15])%mod; } for(j=n%16-1;~j;--j)now=(now*x+a[j])%mod; write(mp[x]=now); } return 0; } ```