什么都别说了,咱心态已经炸了...

question

题目戳这里的说...

其实就是叫你求下面这个式子的导函数:

noteskey

其实是道板子题呢~

刚好给我们弄个多项式合集的说...

各种板子粘贴的不亦乐乎结果一交发现自己 T 掉了,心态爆炸

斗胆把 YYB 大仙的代码交上去发现 A 掉了...(会不会被棕掉丫)

然后调了半天代码甚至还加了更多的优化结果发现跑得还是巨慢无比...

然后继续查 bug ,发现各种函数里面都没有区别,函数运行速度也差不了多少

于是只剩 NTT 里面的锅了,于是两份代码各跑 30 遍 NTT 看了看,发现自己的代码比 YYB 大仙的慢三倍! 然后各种心态爆炸...

于是终于怀疑起了最基本的函数: mul、inc、dec...

最后发现居然是 inc 和 dec 函数跑慢了! 心态怎能不炸!多年的信仰丫~

本以为取模速度超级慢三目速度超级快,结果...啪啪打脸(好吧其实是取模相对加减乘除慢,三目相对 if 语句快)

于是...就把三目改成取模瞬间 A 了此题 TAT

长教训了(但是感觉 inc 和 dec 的写法都改不了了怎么办...在线等)

code

总之和那位大佬说的一样,这种题拿来练手 (抄板子) 还行,比赛里面出来就准备好锤子把出题人胖揍一顿吧...

//by Judge
#include<bits/stdc++.h>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define ll long long
using namespace std;
const int mod=998244353;
const int iG=332748118;
const int M=3e5+3;
typedef int arr[M];
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline int inc(int x,int y){return (x+y)%mod;}
inline int dec(int x,int y){return (x-y+mod)%mod;}
inline int Dec(int x,int y){return x<y?x-y+mod:x-y;}
inline int Inc(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int read(){ int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int CCF=-1,Z;
inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}
inline void print(int x,char chr=' '){
if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;
} int n,k,d,limit; arr a,b,r[21],lg,inv,G[2];
inline int qpow(Rg int x,Rg int p=mod-2,Rg int s=1){
for(;p;p>>=1,x=mul(x,x)) if(p&1) s=mul(s,x); return s;
}
inline void prep(int n){
inv[1]=1; for(limit=1;limit<=n;limit<<=1);
fp(i,2,limit) inv[i]=mul(mod-mod/i,inv[mod%i]);
fp(d,1,19){ lg[1<<d]=d; fp(i,0,(1<<d)-1)
r[d][i]=(r[d][i>>1]>>1)|((i&1)<<(d-1));
}
for(Rg int t=(mod-1)>>1,i=1,x,y;i<262144;i<<=1,t>>=1){
x=qpow(3,t),y=qpow(iG,t),G[0][i]=G[1][i]=1;
fp(k,1,i-1) G[1][i+k]=mul(G[1][i+k-1],x),G[0][i+k]=mul(G[0][i+k-1],y);
}
}
inline void NTT(int* a,int tp){
fp(i,0,limit-1) if(i<r[d][i]) swap(a[i],a[r[d][i]]);
for(Rg int mid=1;mid<limit;mid<<=1){ int I=mid<<1;
for(Rg int j=0,x,y;j<limit;j+=I) fp(k,0,mid-1)
x=a[j+k],y=mul(G[tp][mid+k],a[j+k+mid]),
a[j+k]=(x+y)%mod,a[j+k+mid]=(x-y+mod)%mod;
}
if(tp) return ; fp(i,0,limit-1) a[i]=mul(a[i],inv[limit]);
}
inline void init(Rg int n){ d=0;
for(limit=1;limit<=n;limit<<=1)++d;
}
void Inv(int* a,int* b,int n){
static arr C,D; if(n==1) return b[0]=qpow(a[0]),void();
Inv(a,b,n>>1),init(n); fp(i,0,n-1) C[i]=a[i],D[i]=b[i];
fp(i,n,limit-1) C[i]=D[i]=0; NTT(C,1),NTT(D,1);
fp(i,0,limit-1) C[i]=mul(C[i],mul(D[i],D[i])); NTT(C,0);
fp(i,0,n-1) b[i]=dec(inc(b[i],b[i]),C[i]); fp(i,n,limit-1) b[i]=0;
}
void Sqrt(int* a,int* b,int n){
static arr D,F; if(n==1) return b[0]=sqrt(a[0]),void();
Sqrt(a,b,n>>1); fp(i,0,n<<1) F[i]=0;
Inv(b,F,n),init(n); fp(i,0,n-1) D[i]=a[i];
fp(i,n,limit-1) D[i]=0; NTT(D,1),NTT(b,1),NTT(F,1);
fp(i,0,limit-1) b[i]=mul(inc(b[i],mul(D[i],F[i])),inv[2]);
NTT(b,0); fp(i,n,limit-1) b[i]=0;
memset(D,0,limit<<2),memset(F,0,limit<<2);
}
inline void Direv(int* a,int* b,int n){
fp(i,1,n-1) b[i-1]=mul(a[i],i); b[n-1]=b[n]=0;
}
inline void Inter(int* a,int* b,int n){
fp(i,1,n-1) b[i]=mul(a[i-1],inv[i]); b[0]=0;
}
inline void Ln(int* a,int* b,int n){
static arr A,B; Direv(a,A,n),Inv(a,B,n);
init(n),NTT(A,1),NTT(B,1);
fp(i,0,limit-1) A[i]=mul(A[i],B[i]);
NTT(A,0),Inter(A,b,limit);
memset(A,0,limit<<2),memset(B,0,limit<<2);
}
inline void Exp(int* a,int* b,int n){
static arr F; if(n==1) return b[0]=1,void();
Exp(a,b,n>>1),Ln(b,F,n),init(n);
F[0]=dec(a[0]+1,F[0]); fp(i,1,n-1) F[i]=dec(a[i],F[i]);
NTT(F,1),NTT(b,1); fp(i,0,limit-1) b[i]=mul(b[i],F[i]);
NTT(b,0); fp(i,n,limit-1) b[i]=0; memset(F,0,limit<<2);
}
inline void Pow(int* a,int* b,int n,int k){
static arr F; memset(F,0,n<<2),Ln(a,F,n);
fp(i,0,n-1) F[i]=mul(F[i],k); Exp(F,b,n);
}
int main(){
#ifndef Judge
freopen("polynomial.in","r",stdin);
freopen("polynomial.out","w",stdout);
#else
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
n=read(),k=read(),prep(n<<1);
fp(i,0,n-1) a[i]=read(); int len;
for(len=1;len<=n;len<<=1);
Sqrt(a,b,len),memset(a,0,len<<2);
Inv(b,a,len),memset(b,0,len<<2);
Inter(a,b,n),memset(a,0,len<<2);
Exp(b,a,len),memset(b,0,len<<2);
Inv(a,b,len),memset(a,0,len<<2);
b[0]=inc(b[0],1);
Ln(b,a,len),memset(b,0,len<<2);
a[0]=inc(a[0],1);
Pow(a,b,len,k),memset(a,0,len<<2);
Direv(b,a,n);
fp(i,0,n-1) print(a[i]); return Ot(),0;
}

最新文章

  1. linux 学习 12 服务管理
  2. Oracle12c:安装后新建用户及其默认表空间,并创建表测试
  3. set QUOTED_IDENTIFIER ON事故记录
  4. xcode6.3插件失效
  5. 【SpringMVC】SpringMVC系列11之Restful的CRUD
  6. android listview综合使用示例_结合数据库操作和listitem单击长按等事件处理
  7. SWPFILE实现(增加swap空间)
  8. Thread的第三天学习
  9. 1650. Billionaires(线段树)
  10. JavaScript-Jquery实现全选反选
  11. 运行错误:Application Error - The connection to the server was unsuccessful
  12. ts文件分析(纯c解析代码)
  13. 使用User Primary Email作为GUID的问题
  14. Docker镜像仓库Harbor搭建及配置
  15. SPOJ1811 LCS - Longest Common Substring(后缀自动机)
  16. Elasticsearch之配置详解
  17. FormatMessage
  18. 复制数组之System.arraycopy()的使用
  19. Docker修改本地镜像与容器的存储位置
  20. Hadoop记录-hadoop介绍

热门文章

  1. 五、Redis持久化配置
  2. IP地址、子网掩码、默认网关是什么意思?
  3. sprigboot recontroller 是responsebody与controller结合 这样 就使每个方法默认返回json
  4. springdata jpa查询用like时候需要输入该属性的类型字节码
  5. Day 2 上午
  6. Navicat 连接远程服务器mysql 长时间不操作会连接很久
  7. Python基础学习笔记4-28(持续更新)
  8. 【CF1157F】Maximum Balanced Circle
  9. 如何隐藏overflow: scroll的滚动条
  10. 基于 Markdown 编写接口文档