博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj 3992 [SDOI2015]序列统计——NTT(循环卷积&&快速幂)
阅读量:5868 次
发布时间:2019-06-19

本文共 1983 字,大约阅读时间需要 6 分钟。

题目:

有转移次数、模M余数、方案数三个值,一看就是系数的地方放一个值、指数的地方放一个值、做卷积的次数表示一个值(应该是表示转移次数)。

可以余数和方案数都要求相乘,指数只能相加,怎么办?

然后看题解,原来可以用M的原根的幂来表示余数那个信息!因为原根的几次幂和%M剩余类可以一一对应(除了%M==0!!!),所以用原根的幂表示%M余几,两个余数相乘就变成原根的指数相加了!把该余数对应的原根的指数放在多项式指数的位置,就可以NTT啦!

原根是 1~P-1 次幂的值%P各不相同的,所以可以用 0次项~M-2次项 或者 1次项~M-1 次项来表示。

n的范围要求快速幂。但不是把点值拿出来之后对点值快速幂一番再用点值还原回系数,因为每次卷积那个多项式的长度都要翻倍,所以最后n个点的个数就不够了。

所以要快速幂中每次卷积了一下后把它翻倍的长度手动循环一番变回原长M。这样就行啦!

注意数据范围!!!求的那个 x 不能为0,而给出的元素可以为0!而原根的那些幂都不会为0!(仔细一想,只有0或M的倍数才会%M==0)考虑到那个 x 不会为0、而数列中放入一个0的话值就变成0了,所以给出0以后要认为没有那个元素!!!!!

快速幂时,ans的初值应该像1一样;也就是一个多项式卷积它之后还是该多项式本身。想一想,就是在0次项赋1、其他项赋0即可。

发现>(M<<1)的项的值一定是0;所以循环的时候可以直接减掉1个(M-1)而不用模什么的。

#include
#include
#include
#include
#define ll long longusing namespace std;const int N=8005; const ll mod=1004535809;int n,m,M,pn,s[N],zb[N],pri[N],len,r[N<<2];int a[N<<2],ans[N<<2];int rdn(){ int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){
if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret;}void upd(int &x,int md){x>=md?x-=md:0;}int pw(int x,int k,int md){
int ret=1;while(k){
if(k&1)ret=(ll)ret*x%md;x=(ll)x*x%md;k>>=1;}return ret;}int gtrt(){ int k=M-1,tot=0; for(int i=2;i*i<=k;i++) if(k%i==0){pri[++tot]=i;while(k%i==0)k/=i;} if(k>1)pri[++tot]=k; for(int g=2;;g++) { int i; for(i=1;i<=tot;i++) if(pw(g,(M-1)/pri[i],M)==1)break; if(i>tot)return g; }}void ntt(int *a,bool fx){ for(int i=0;i
>1; int Wn=pw(3,(mod-1)/R,mod); fx?Wn=pw(Wn,mod-2,mod):0; for(int i=0;i
>1]>>1)+((i&1)?len>>1:0); for(int i=1;i<=m;i++)if(s[i])a[zb[s[i]]]=1;////if ans[0]=1;/// while(n) { ntt(a,0); if(n&1) { ntt(ans,0); for(int i=0;i
(M<<1) surely have no value ans[i]+=ans[i+M-1],ans[i+M-1]=0,upd(ans[i],mod); } for(int i=0;i
>=1; } printf("%d\n",ans[zb[pn]]); return 0;}

 

转载于:https://www.cnblogs.com/Narh/p/10033817.html

你可能感兴趣的文章
建立低权限的ftp帐号
查看>>
htpasswd
查看>>
微软整合实验(七):布署Exchange2010 Mailbox高可用(DAG)
查看>>
spring定时器----JobDetailBean
查看>>
我的友情链接
查看>>
XP下如何删除附件中的游戏组件
查看>>
我的友情链接
查看>>
emma的几个不足之处
查看>>
Java工具类——UUIDUtils
查看>>
使用Node搭建reactSSR服务端渲染架构
查看>>
文件缓存
查看>>
转 博弈类题目小结(hdu,poj,zoj)
查看>>
Java NIO学习笔记八 Pipe
查看>>
远程协助
查看>>
Scrum实施日记 - 一切从零开始
查看>>
关于存储过程实例
查看>>
配置错误定义了重复的“system.web.extensions/scripting/scriptResourceHandler” 解决办法...
查看>>
AIX 7.1 install python
查看>>
PHP盛宴——经常使用函数集锦
查看>>
重写 Ext.form.field 扩展功能
查看>>