【hash】BZOJ3751-[NOIP2014]解方程

【题目大意】

已知多项式方程：a0+a1*x+a2*x^2+...+an*x^n=0。求这个方程在[1,m]内的整数解（n和m均为正整数）。

【思路】

*当年考场上怒打300+行高精度，然而没骗到多少orz 然而正解只有60+行

[前铺]f(n) mod p=f(n mod p) mod p

取四个素数，分别对每个ai取模。先预处理x=0..p-1的情况，直接代入多项式计算即可。再在O(m)时间内检验1..m，对于≥p的利用前铺公式可得。如果模四个素数结果均能得到0，说明这个数是方程的解。

P.S.这个的前提是你的脸好……我一开始随便取的四个就WA了QAQ

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN=+;

 const int MAXM=+;

 const int MAXP=;

 typedef long long ll;

 int prime[]={,,,};

 int n,m,a[MAXN],hash[MAXN][],table[MAXP][],ans[MAXM],cnt=;

 ll get_table(int j,int x)

 {

     ll ret=;

     for (int i=n;i>=;i--)

         ret=(ret*x+hash[i][j])%prime[j];

     return ret;

 }

 int read(int x)

 {

     char str[];

     scanf("%s",str);

     int negative=;

     for (int i=;str[i];i++)

     {

         if (str[i]=='-') negative=;

             else for (int j=;j<;j++)

                     hash[x][j]=((hash[x][j]*)%prime[j]+(str[i]-''))%prime[j];

     }

     if (negative)

         for (int j=;j<;j++)

             hash[x][j]=(prime[j]-hash[x][j])%prime[j];

 }

 void init()

 {

     memset(hash,,sizeof(hash));

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++) read(i);

     for (int i=;i<;i++)

         for (int j=;j<prime[i];j++) table[j][i]=get_table(i,j);

 }

 void solve()

 {

     for (int i=;i<=m;i++)

     {

         int flag=;

         for (int j=;j<;j++)

             if (table[i%prime[j]][j])

             {

                 flag=;

                 break;

             }

         if (flag) ans[++cnt]=i;

     }

     printf("%d\n",cnt);

     for (int i=;i<=cnt;i++) printf("%d\n",ans[i]);

 }

 int main()

 {

     init();

     solve();

     return ;

 }

巴特西

【hash】BZOJ3751-[NOIP2014]解方程

最新文章

热门文章