BZOJ 3751 [NOIP2014]解方程 百年老坑填坑计划QAQ--Hash

题意:
已知多项式方程：
a0+a1∗x+a2∗x2+a3∗x3+....+an∗xn
求这个方程在[1,m]内的整数解（n和m均为正整数）。
解析:
记得我在去年的考场上看完这道题的表情是这样的->
好像骗到了一元二次那部分的分？
这题看完Po姐当年的题解感觉好简单啊…
BZ的这个题是加强了数据的。
我们考虑做法。
如果 f(x)=0 那么有 f(x mod p)mod p=0,p为质数
这个hash的冲突性应该取决于你所取的质数以及数据…
如果我们只考虑一个质数的话，那么显然可能被卡，但是如果我们选5,6个质数的话，只需要判断 f(x mod p) 在这些模意义下是否都是零就可以了！
不妨设我们选了a个质数
复杂度的话，首先我们计算模意义下的值应该是O(n*p*a)
然后我们枚举1~m中的数，检验的复杂度是O(m*a)
其中需要注意的是，取模的费时比较高，所以我们可以考虑把相乘的部分开成long long减少取模次数。
代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 110
#define M 11000
#define K 1001101
using namespace std;
typedef int ll;
ll prime[6]={0,10007,11261,19997,21893,20947};
long long num[N][6];
long long ans[21893][6];
char s[M];
ll n,m;
void read(ll now)
{
scanf("%s",s+1);
    ll len=strlen(s+1);
bool flag=0;
for(ll i=1;i<=len;i++)
    {
if(s[i]=='-'){flag=1;continue;}
        ll tmp=s[i]-'0';
for(ll j=1;j<=5;j++)
        {
            num[now][j]=((num[now][j]<<1)+(num[now][j]<<3)+tmp)%prime[j];
        }
    }
if(flag)
    {
for(ll j=1;j<=5;j++)
            num[now][j]=prime[j]-num[now][j];
    }
}
ll calc(ll number,ll no)
{
    ll ret=num[n][no];
for(ll i=n-1;i>=0;i--)
    {
        ret=(num[i][no]+ret*number)%prime[no];
    }
return ret;
}
ll sta[K];
ll top;
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=0;i<=n;i++)read(i);
for(ll i=1;i<=5;i++)
for(ll j=0;j<prime[i];j++)
            ans[j][i]=calc(j,i);
for(ll i=1;i<=m;i++)
    {
bool flag=1;
for(ll j=1;j<=5;j++)
if(ans[i%prime[j]][j]!=0)
            {flag=0;break;}
if(flag)sta[++top]=i;
    }
printf("%d\n",top);
for(ll i=1;i<=top;i++)
printf("%d\n",sta[i]);
return 0;
}