[洛谷 2312][NOIP2014]解方程

题目链接

https://www.luogu.org/problemnew/show/P2312

题解

基本思想是枚举所有解,但如果采用传统的方法计算多项式的值,计算量是无法承受的。

因此,我们需要使用更高效的多项式计算方法——秦九韶算法!

计算一个多项式\(f(x)=a_nx^n+a_{n-1}x^{n-1}+ \ldots +a_1x+a_0\),传统的计算方法是这样的:

long long calc(int x)
{
 long long ans=a[0],x1=x;
 for(int i=1;i<=n;i++)
 {
  x1=1;
  for(int j=1;j<=i;j++)
   x1=x1*x%MOD;
  ans=ans+a[i]*x1%MOD;
 }
 return ans;
}

即花费\(O(n^2)\)的时间求出所有\(x^i\)的值,再分别与系数相乘。采用这么慢的方法计算显然是无法解决问题的。

只需要采用一个小小的优化,就可以仅仅采用\(n\)次乘法就求出所有\(x^i\)的值:

long long calc(int x)
{
 long long ans=a[0],x1=x;
 for(int i=1;i<=n;i++)
 {
  ans=(ans+a[i]*x1)%MOD;
  x1=x1*x%MOD;
 }
 return ans;
}

这种方法利用了之前已经算出来的低次项的值,避免了重复计算,总的乘法次数达到了\(2n\)次,加法次数有\(n\)次,已经比刚才快了很多,在洛谷的评测机上已经足够通过这道题。

但还有效率最高的秦九韶算法。

我们对多项式\(f(x)\)进行如下处理:

\(f(x)
\\
=a_nx^n+a_{n-1}x^{n-1}+ \ldots +a_1x+a_0
\\
=(a_nx^{n-1}+a_{n-1}x^{n-2}+ \ldots +a_1)x+a_0
\\
=((a_nx^{n-2}+a_{n-2}x^{n-3}+ \ldots +a_2)x+a_1)x+a_0
\\
\ldots
\\
=(\ldots((a_nx+a_{n-1})x+a_{n-2})x+ \ldots +a_1)x+a_0
\)

计算时,我们先算出括号最里层的值,再一步步往外算,这样我们就可以只用\(n\)次乘法和\(n\)次加法,就高效地解决了问题!

在解决本题时,因为高精度的效率实在太低,我们需要对中间结果取模,这个过程中有被精心构造的hack数据卡的风险…(不过看出来出题人并没有卡,毕竟高精度实在太慢了…)

(偷偷说一句,其实各位一直写的读入优化也渗透了秦九韶算法的思想呢)

#include <cstdio>
#include <iostream>
#include <algorithm>
#define MOD 19260817
using namespace std;
long long a[105];
int res[1000005],cnt,n,m;
long long read()
{
 long long num=0,flag=1;
 char ch=getchar();
 while(ch<'0'||ch>'9')
 {
  if(ch=='-')flag=-1;
  ch=getchar();
 }
 while(ch>='0'&&ch<='9')
 {
  num=((num*10)+(ch-'0'))%MOD;
  ch=getchar();
 }
 return flag*num;
}
inline long long calc(int x)
{
 long long ans=0;
 for(int i=n;i;i--)
  ans=(ans+a[i])*x%MOD;
 ans=(ans+a[0])%MOD;
 return ans;
}
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=0;i<=n;i++)
  a[i]=read();
 for(int i=1;i<=m;i++)
  if(!calc(i))res[++cnt]=i;
 printf("%d\n",cnt);
 for(int i=1;i<=cnt;i++)
  printf("%d\n",res[i]);
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注