首页 > 其他分享 >「NOIP2014」解方程 题解

「NOIP2014」解方程 题解

时间:2023-11-14 17:58:33浏览次数:47  
标签:... ch int 题解 nx NOIP2014 text 解方程 mod

思路

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

\(a_0+a_1x+a_2x^2+a_3x^3+\text{...}+a_nx^n\)
\(=a_0+(a_1+a_2x+a_3x^2+\text{...}+a_nx^{n-1})x\)
\(=a_0+(a_1+(a_2+a_3x+\text{...}+a_nx^{n-2})x)x\)
\(\text{...}\)
\(=a_0+(a_1+(a_2+(a_3+(\text{...}(a_{n-1}+a_nx)x\text{...})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,NOIP2014,text,解方程,mod
From: https://www.cnblogs.com/liudagou/p/17832116.html

相关文章

  • Q7.4.1.2. 奇怪的方格涂色 题解
    原题链接首先想到暴力网络流:考虑最小割,\(S\)表示染黑色,\(T\)表示染白色。每个格子\(i\),连\((S,i,b_i)\),\((i,T,w_i)\)。怎么处理“奇怪的方格”?连\((i,i^\prime,p_i)\)和\((i^\prime,j,+\infty)\)。表示如果\(i\)归属于\(S\)(染黑色),那么就只能忍受奇怪所带来的\(p_i\)......
  • AT_abc230_f [ABC230F] Predilection 题解
    prelogue各位在比赛的时候一定要坚信自己的式子,然后去考虑自己的实现是不是挂了。本人在今天模拟赛的时候质疑自己的式子然后不看实现100->0。analysis考虑对这个给定数组进行前缀和,然后就将问题转化成为了求这个前缀和数组的子序列的个数。对于求子序列,我们很轻松可以写出......
  • Codeforces Round 809 (Div. 2) D1. Chopping Carrots (Easy Version) 题解
    题意CodeforcesRound809(Div.2)D1.ChoppingCarrots(EasyVersion)给两个整数\(n,k\),一个数组\(a\),要求构造一个同样长度的数组\(p\),使得\(\max\limits_{1\lei\len}\left(\left\lfloor\frac{a_i}{p_i}\right\rfloor\right)-\min\limits_{1\lei\l......
  • [USACO23FEB] Equal Sum Subarrays G 题解
    [USACO23FEB]EqualSumSubarraysG题解题目链接\(O(n^5)\)暴力显然,如果修改\(a_i\)的值,只会影响包含\(a_i\)的区间的区间和。于是对于每个\(a_i\),可以将所有区间分成两类,即包含\(a_i\)的区间和不包含\(a_i\)的区间。这两种区间的区间和中最小的差值即为答案。......
  • 【洛谷 P1307】[NOIP2011 普及组] 数字反转 题解(字符串)
    [NOIP2011普及组]数字反转题目描述给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零(参见样例2)。输入格式一个整数。输出格式一个整数,表示反转后的新数。样例#1样例输入#1123样......
  • AGC041D-Problem Scores 题解
    题目链接luoguatcoder分析令\(k=\left\lfloor\frac{n}{2}\right\rfloor\)对于第三个条件,只需要满足\(\sum_{i=1}^{k+1}a[i]<\sum_{i=n-k+1}^{n}a[i]\)即可有一个\(trick\):构造一个单调不降或不增的序列可以转化为每次做一次前缀加操作例如本题要求构造一个单调......
  • [题解] CF1748E Yet Another Array Counting Problem
    YetAnotherArrayCountingProblem给你一个长度为\(n\)的序列和一个数\(m\),求有多少个长度为\(n\)的序列\(b\)满足:\(\foralli\in[1,n],b_i\in[1,m]\)。对于每个区间\([l,r]\),\(b\)中最大值最靠左的位置和\(a\)相同。\(n,m\le2\times10^5,n\ti......
  • [题解] P4435 [COCI2017-2018#2] ​​Garaža
    P4435[COCI2017-2018#2]Garaža给你一个长度为\(n\)的序列\(a\),单点改,查询区间\(\gcd\)不为1的子区间个数。\(n,Q\le10^5,a_i\le10^9\)。先看单次全局查询怎么做。考虑一个分治,每次我们要计算跨过分治中心\(mid\)的答案。因为这个是单调的,所以可以双指针做......
  • 【题解】P4768 [NOI2018] 归程 / Kruskal 重构树
    补补以前懒得总结的零碎东西。kruskal重构树使用条件:求无向图中两点之间所有路径的最大边权的最小值构造:依kruskal得到最小生成树从小到大考虑生成树中的边\((u,v)\)对于\((u,v)\),新建一个结点,作为重构树中\(u,v\)的父结点该结点的点权为\((u,v)\)的......
  • SPOJ1805 HISTOGRA - Largest Rectangle in a Histogram 题解
    LinkSPOJ1805HISTOGRA-LargestRectangleinaHistogramQuestion在一条水平线上有\(n\)个高为\(a_i\)的矩形,求包含于这些矩形的最大子矩形面积。Solution我们定义\(L_i\)表示有\(a_i\)这个高度的一根悬线,往左最多能平移到什么位置初始化显然,\(a_i=i\)考虑转移......