[洛谷 2312][NOIP2014]解方程

题目链接

https://www.luogu.org/problem/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)\) 进行如下处理:

$$ \begin{eqnarray} 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 \end{eqnarray}$$

计算时,我们先算出括号最里层的值,再一步步往外算,这样我们就可以只用 \(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;
}

发表评论

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