正解:数论
解题报告:
又是很妙的一道题呢,专门用来对付我这种思维僵化了的傻逼的QAQ
首先看题目的数据范围,发现a<=1010000,很大的一个数据范围了呢,那这题肯定不会常规方法做是趴
然后.首先我们思考30pts怎么做,因为这题的主要做法其实就30pts能解决主要问题在于数据范围很大嘛
然后30pts要用个听起来很牛逼其实很亲民的定理--秦九韶定理
我们思考那个算式怎么算嘛,如果最傻逼的,就每次ai×xi然后算一下,一般人应该不会这么傻逼?
然后就想到一个很容易想到的东西,就是变成a+(a+(a+(a+x)*x)*x)*x这样的形式,这样就很简单而且我们可以O(m)地做掉是趴
然后这个东西就是秦九韶定理...所以说只是听起来好像很厉害其实还是比较好想的趴
然后说亲*要读入优化会用到嘛,实在是天天用啊
接下来考虑更大的怎么做
首先如果实在想不出来了我们可以用高精度拿到点儿部分分(...话说我真的挺想有时间用高精码一发鸭,好久没写高精了...
但是NOIp好像很久没考高精了?我们就先不往这方面想
跑个题嗷,其实今天的话我觉得还是比较好想到正解的,所以说我没有想到还是很不应该,说明思维没有拓展,考试的意义没有最大程度地发挥出来鸭
就是今天不是做T3的时候没有膜法嘛,zsy学长就分享了一个方法--在做的过程中先把答案取膜然后最后输出的时候枚举一下i算出哪个i能满足取膜等于答案就好了!那时候我还觉得很妙来着!这时候居然就忘了!真的太傻逼了我!
对这里就是相同的想法鸭,我们也是对答案取膜如果取膜意义下最后的答案是0说明有很大的可能不取膜也是0对趴,如果不放心的话可以多膜几个数就没问题辣!
这里大概还是能明白的趴?
但是还有一个待解决的问题--a太大了怎么办
然后有个还是比较显然的玩意儿就是说 a*x≡(a%p)*x (mod p)
这个也太显然了?
然后推广一下就可以得到 ai*xi+ai-1*xi-1+...≡(ai%p)*xi+(ai-1%p)*xi-1+....(mod p)
这样的话相当于我们读入优化的时候直接读入的时候对每个a%p就成了,然后如果不放心多开了几个mod就多存到几个数组里就成了
大概就这样?overrrrr
放代码辽
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define rp(i,x,y) for(register ll i=x;i<=y;++i)
,mb=,mc=;
ll m,n,cjk,ans[],a[],b[],c[];
inline ll read1()
{
;;
'))ch=getchar();
;
)+(x<<)+(ch^'),ch=getchar();
return y?x:-x;
}
inline void read2(ll i)
{
;
'))ch=getchar();
;
)+(a[i]<<)+(ch^)+(b[i]<<)+(ch^)+(c[i]<<)+(ch^'))%mc,ch=getchar();
if(!y)a[i]=-a[i],b[i]=-b[i],c[i]=-c[i];
return;
}
inline bool check(ll x)
{
ll ansa=,ansb=,ansc=;
rp(j,,n){ll i=n-j;ansa=(ansa+a[i]+ma)*x%ma,ansb=(ansb+b[i]+mb)*x%mb,ansc=(ansc+c[i]+mc)*x%mc;}
&& ansb== && ansc==);
}
int main()
{
n=read1();m=read1();
rp(i,,n)read2(i);
rp(i,,m)if(check(i))ans[++cjk]=i;
printf("%lld\n",cjk);
rp(i,,cjk)printf("%lld\n",ans[i]);
;
}
点我!看!傻逼!灵巧!在线!做题!