背景
B酱为NOIP 2014出了一道有趣的题目, 可是在NOIP现场, B酱发现数据规模给错了, 他很伤心, 哭得很可怜.....
为了安慰可怜的B酱, vijos刻意挂出来了真实的题目!
描述
已知多项式方程：
$$a_0+a_1x+a_2x^2+...+a_nx^n=0$$
求这个方程在[1, m]内的整数解（n 和 m 均为正整数）。
输入格式
输入共 n+2 行。
第一行包含 2 个整数 n、m，每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数，依次为$a_0,a_1,a_2,...a_n$。
输出格式
第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。
限制
对于20%的数据，$0<n\leq 100$，$|a_i|<=10^{100}$，$a_n \neq 0$，$m\leq 100$；
对于40%的数据，$0<n\leq 100$，$|a_i|<=10^{10000}$，$a_n \neq 0$，$m\leq 10000$；
对于70%的数据，$0<n\leq 100$，$|a_i|<=10^{10000}$，$a_n \neq 0$，$m\leq 1000000=10^6$；
对于100%的数据，$0<n\leq 100$，$|a_i|<=10^{10000}$，$a_n \neq 0$，$m\leq 100000000=10^8$。
[实际上来说就算m <= 10^10也是可以做的， 不过我把时间限制设定为0.5秒，感觉也差不多了。THU某人: O(m)的算法过不去了, 呜呜呜....]
刚把$noip$的欠账：解方程给补上，又发现了vijos上还有一道加强版。这道题主要就是把$m$的范围加强到了$10^8$，卡掉了$O(m)$的算法。题解戳这里
不过这道题我把解方程$O(m)$的算法稍微优化了一下，然后就这么过去了……
原题$O(m)$的算法主要就是自己设一个模数$p$，先把区间$[0,p)$中的解给算出来，然后方程在$x$处的取值就是方程在$x \bmod p$处的取值，于是可以在$O(pn)$的处理后，用$O(m)$的复杂度得到方程在$[1,m]$中的取值。然而这样其实是有非常多的冗余状态的，因为真正对我们有用的位置只是值为$0$的位置。于是我们可以只处理这些位置，分别存到数组中，最后判断一下某个值是否在每个模数下都出现即可。加了这一点优化后即可获得$AC$。
还有我的这份代码在BZOJ上A不了，需要换一组模数……果然我还是血统不行……
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 110
#define maxn 10010
#define maxm 1000010
#define zushu 4 using namespace std;
typedef long long llg; int p[zushu]={7757,11959,15121,20011},nn[N];
int n,m,l[N],mod,st[N],d[zushu][maxm],ld[zushu];
int ans[maxm],la,ci[maxm],nw[zushu];
char s[N][maxn];
bool fu[maxn<<1]; int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
} int suan(int x){
int ans=0,now=1;
for(int i=0;i<=n;i++){
ans+=nn[i]*now%mod,ans%=mod;
now*=x,now%=mod;
}
return ans;
} void work(){
for(int i=1;i<zushu;i++) nw[i]=1;
for(nw[0]=1;nw[0]<=ld[0];nw[0]++){
bool ww=1;
if(d[0][nw[0]]>m) break;
for(int i=1;i<zushu;i++){
while(d[i][nw[i]]<d[0][nw[0]]) nw[i]++;
if(d[i][nw[i]]!=d[0][nw[0]]) ww=0;
if(nw[i]>ld[i]) return;
}
if(ww) ans[++la]=d[0][nw[0]];
}
} int main(){
File("a");
n=getint(); m=getint();
for(int i=0;i<=n;i++){
scanf("%s",s[i]+1),l[i]=strlen(s[i]+1);
st[i]=(s[i][1]=='-'?2:1); fu[i]=(s[i][1]=='-');
}
for(int i=0;i<zushu;i++){
mod=p[i];
for(int j=0;j<=n;j++){
nn[j]=0;
for(int k=st[j];k<=l[j];k++) nn[j]=nn[j]*10+s[j][k]-'0',nn[j]%=mod;
if(fu[j]) nn[j]=-nn[j];
}
for(int j=0;j<mod;j++) if(!suan(j)) d[i][++ld[i]]=j;
for(int j=1;j<=ld[i];j++)
if(d[i][j]+mod<=m) d[i][++ld[i]]=d[i][j]+mod;
else break;
}
work();
printf("%d\n",la);
for(int i=1;i<=la;i++) printf("%d\n",ans[i]);
return 0;
}
后天就是$noip$了，我现在还感觉有各种板子没有复习……感觉药丸……
还有我在想我要不要也开一篇游记什么的……等我复习完了模板再说吧……也许我复习不完了。