【秦九韶算法】【字符串哈希】bzoj3751 [NOIP2014]解方程

时间：2022-09-02 10:31:18

在模意义下枚举m进行验证，多设置几个模数，而且小一些，利用f(x+p)%p=f(x)%p降低计算次数。UOJ AC，bzoj OLE。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

#define MAXV 4951

vector<int>v;

typedef unsigned int ull;

const ull prime[]={4931,4933,4937,4943,4951};

int n;

ull m,a[101][5],F[MAXV+1][5];

char s[10002];

ull f(const ull &x,const int &wh)

{

	if(x>=prime[wh]) return f(x%prime[wh],wh);

	if(F[x][wh]<MAXV) return F[x][wh];

	ull res=0;

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

	  res=(res*x%prime[wh]+a[i][wh])%prime[wh];

	return F[x][wh]=res;

}

int main()

{

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

	memset(F,0x7f,sizeof(F));

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

	  {

	  	scanf("%s",s);

	  	int len=strlen(s);

	  	for(int k=(s[0]=='-'?1:0);k<len;++k)

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

	  	    a[i][j]=((a[i][j]*10)%prime[j]+(s[k]-'0'))%prime[j];

	  	if(s[0]=='-')

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

	  	    a[i][j]=prime[j]-a[i][j];

	  }

	for(ull i=1;i<=m;++i)

	  {

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

		  if(f(i,j))

		    goto OUT;

	  	v.push_back((int)i);

		OUT:;

	  }

	printf("%d\n",v.size());

	for(int i=0;i<v.size();++i) printf("%d\n",v[i]);

	return 0;

}

相关文章