首页 > 其他分享 >[NOIP2014] 解方程

[NOIP2014] 解方程

时间:2024-07-12 13:32:16浏览次数:15  
标签:ch int nx 模数 cdots NOIP2014 解方程 mod

思路

首先我们可以观察到 \(n\) 和 \(m\) 与\(a_i\) 相比小的很多,所以我们可以考虑直接暴力求解
但是 \(a_i\) 太大了,所以如果需要直接计算的话需要全程使用高精度算法。
因为高精度算法代码量有大速度又慢我们可依考虑将 \(a_i\) 转化为一个极大的指数取模的结果,因为只有是模数的倍数或者本身就是 \(0\) 的数取模才会是 \(0\)。
为了避免出现模数的倍数,可以使用两个模数减小概率(像双哈希一样)但是也可以将模数设置的大一点减小几率。可是两个模数码量过大,我们可以直接使用一个大质数(相信出题人不会卡我们的)。
因为题目给出的式子过于的复杂,其实可以使用秦九韶算法进行化简

\(a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n\)
\(=a_0+(a_1+a_2x+a_3x^2+\cdots+a_nx^{n-1})x\)
\(=a_0+(a_1+(a_2+a_3x+\cdots+a_nx^{n-2})x)x\)
\(\cdots\)
\(=a_0+(a_1+(a_2+(a_3+(\cdots(a_{n-1}+a_nx)x\cdots)x)x)x\)

虽说名字叫秦九韶算法,但是其实就是将每一项内的因子提取了出来,即使不化简也一样可以做出来。
在简化之后,就可以从最里层的括号开始,逐层向外递推,码量就少了很多。经过递推,很快的就可以得到表示的值了,时间复杂度为 \(O(nm)\)。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m,a[105];
vector<int> v;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') f=-1,ch=getchar();
	while(ch<='9'&&ch>='0') x=((x<<1)+(x<<3)+ch-48)%mod,ch=getchar();
	return x*f;
}
void solve(int x){
	int cnt=a[n];
	for(int i=n;i>=1;i--) cnt=(cnt*x%mod+a[i-1]+mod)%mod;
	if(cnt==0) v.push_back(x); //储存答案
}
signed main(){
	n=read(),m=read();
	for(int i=0;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++) solve(i);
	cout<<v.size()<<endl;
	for(int i:v) cout<<i<<endl; //将数组v中的元素依次赋值给变量i
	return 0;
}

标签:ch,int,nx,模数,cdots,NOIP2014,解方程,mod
From: https://www.cnblogs.com/liudagou/p/18298189

相关文章

  • Lingo学习(一)——基本界面、解方程、变量
    一、Lingo基本界面【步骤】1.双击打开Lingo2.弹出一个对话框,点击Cancel左边的NeverRegister即可,其余内容用不到。3:界面自动弹出名为“LingoModel–Lingo1”的窗口,用于书写代码。4:以解方程的题目:x+1=2为例,写完代码后,点击“红色的靶心”运行程序。5:首......
  • P2239 [NOIP2014 普及组] 螺旋矩阵
    洛谷题面:题目分析本题需要一个旋转的数字矩阵,因为填数要求,首先考虑DFS。注意写题目时,一定一定要注意数据范围!在此题中,注意数据范围对于 50%的数据,1⩽......
  • # [NOIP2014 提高组] 生活大爆炸版石头剪刀布
    传送锚点:https://www.luogu.com.cn/problem/P1328题目背景NOIP2014提高组D1T1题目描述石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头......
  • 【NOIP2014普及组复赛】题4:子矩阵
    题3:子矩阵【题目描述】给出如下定义:1.子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。例如,下面左图中选取第2、......
  • 【NOIP2014普及组复赛】题3:螺旋矩阵
    题3:螺旋矩阵【题目描述】一个nnn行nnn列的螺旋矩阵可由如下方......
  • 640. 求解方程(中)
    目录题目题解:模拟题目求解一个给定的方程,将x以字符串"x=#value"的形式返回。该方程仅包含'+','-'操作,变量x和其对应系数。如果方程没有解或存在的解不为整数,请返回"Nosolution"。如果方程有无限解,则返回“Infinitesolutions”。题目保证,如果方程中只有一个解,则......
  • 复数范围内解方程
    前言相关知识【初中总结】实数系数的一元二次方程\(ax^2+bx+c=0\quad(a\neq0)\),当\(\Delta\geqslant0\)时,在实数范围内有实数根,其求根公式为\(x=\cfrac{-b\pm\sqrt{b^2-4ac}}{2a}\);根与系数的关系为\(x_1+x_2=-\cfrac{b}{a}\),\(x_1\cdotx_2=\cfrac{c}{a}\);当\(\Delta......
  • 一元二次方程ax2+bx+c=0,a、b、c的值由用户在三行中输入,根据用户输入的数值求解方程的
    输入格式输入三行数据每行输入一个实数输出格式方程的解示例1输入:852输出:该方程无实数解示例2输入:009输出:Dataerror!a=float(input())b=float(input())c=float(input())delta=b**2-4*a*c#德塔ifdelta<0:print("该方程无实数解")#ab==0elif......
  • 题解 NOIP2014 提高组-联合权值
    题解NOIP2014提高组-联合权值基本思路:以每个点为中转点,则与之相邻的点组成的点对都可产生联合权值,并且全覆盖。主要总结一下两种求权值和的思路:思路1(容斥):记与\(u\)相邻的点的集合为\(A\),则点\(u\)产生的贡献为\[ans_u=(\sum_{v\inA}w_i)^2-\sum_{v\inA}w_v\times......
  • 洛谷题单指南-模拟和高精度-P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布
    原题链接:https://www.luogu.com.cn/problem/P1328题意解读:非常简单的一道题,核心考点就是循环数组以及评分规则的构建。评分规则:甲vs乙,1表示甲赢,-1表示甲输,-0表示平转化为数组:intrule[5][5]={0,-1,1,1,-1,1,0,-1,1,-1,-1,1,0,-1,1,-1,......