浙江微信网站建设,网站维护目标,店铺店面装修,书香气的域名做网站文章目录前言力代码礼物代码差分和前缀和代码开拓者的知识代码总结前言
这两天由于国庆集训全是阴间的生成函数#xff0c;所以就学了一点点相关的内容 其实就学了个FFT和NTT 也算是点开了一个小小的技能点吧 进入多项式才发现里面世界的广阔 然而由于这玩意没有一个是NOIP考…
文章目录前言力代码礼物代码差分和前缀和代码开拓者的知识代码总结前言
这两天由于国庆集训全是阴间的生成函数所以就学了一点点相关的内容 其实就学了个FFT和NTT 也算是点开了一个小小的技能点吧 进入多项式才发现里面世界的广阔 然而由于这玩意没有一个是NOIP考点而且似乎对于提高级的题目解决不会有太大的辅助作用 不像某些神仙的数据结构 所以觉得后面的先放放吧 但是这几天多项式也水了四紫两蓝嘛awa
力
入门题 裸且简单 但是我当时实在是根本没明白多项式是啥 所以还是看了题解 …不丢人理直气壮 一个技巧是把函数翻转 但这本身甚至几乎不配叫做技巧 qwq
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define il inline
const int N1e6100;
const int M150;
const int mod998244353;
const double piacos(-1.0);
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m,lim,k;
struct node{double x,y;node(double a0,double b0){xa;yb;}
}A[N],B[N],C[N];
il node operator * (node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x};
}
il node operator (node a,node b){return (node){a.xb.x,a.yb.y};
}
il node operator - (node a,node b){return (node){a.x-b.x,a.y-b.y};
}
int r[N];
il void fft(node *x,int lim,int flag){for(int i0;ilim;i){if(ir[i]) swap(x[i],x[r[i]]);}for(int l1;llim;l1){node o(cos(pi/l),flag*sin(pi/l));for(int st0;stlim;stl1){node t(1,0);for(int j0;jl;j,tt*o){node ux[stj],vt*x[stjl];x[stj]uv;x[stjl]u-v;}}}return;
}
int main(){nread();for(int i1;in;i){scanf(%lf,A[i].x);B[i].x(double)(1.0/i/i);C[n-i].xA[i].x;}int L0,lim1;while(limn1){lim1;L;}for(int i1;ilim;i) r[i](r[i1]1)|((i1)(L-1));fft(A,lim,1);fft(B,lim,1);fft(C,lim,1);for(int i0;ilim;i){A[i]A[i]*B[i];C[i]C[i]*B[i];}fft(A,lim,-1);fft(C,lim,-1);for(int i1;in;i) printf(%lf\n,(A[i].x-C[n-i].x)/lim);return 0;
}
/**/
礼物
这个题是自己做的 显然要把平方拆开 然后发现加上的亮度是可以O1算的 然后是变成最小化一个奇怪的东西 由于循环的性质倍长一下即可
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define il inline
const int N2e6100;
const double piacos(-1.0);
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m;
struct node{double x,y;node (double a0,double b0){xa;yb;}
}A[N],B[N];
il node operator *(node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x};
}
il node operator (node a,node b){return (node){a.xb.x,a.yb.y};
}
il node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};
}
int r[N];
il void fft(node *x,int lim,int flag){for(int i1;ilim;i){if(ir[i]) swap(x[i],x[r[i]]);}for(int l1;llim;l1){node o(cos(pi/l),flag*sin(pi/l));for(int st0;stlim;stl1){node t(1,0);for(int i0;il;i,tt*o){node ux[sti],vt*x[stli];x[sti]uv;x[stli]u-v;}}}
}
ll x[N],y[N],tot,Sx,Sy,ans2e18;
int main(){nread();mread();for(int i1;in;i) x[i]read();for(int i1;in;i) y[i]read();for(int i1;in;i){totx[i]*x[i]y[i]*y[i];Sxx[i];Syy[i];}if(SySx) swap(Sy,Sx);ll a(Sy-Sx)/n,ba1;if(a*a*n2*a*(Sx-Sy)b*b*n2*b*(Sx-Sy)) swap(a,b);tota*a*n2*a*(Sx-Sy);//printf(a%d\n,a);for(int i1;in;i){A[i].xx[i];B[nn-i].xB[n-i].xy[i];}int lim1,L0;while(lim3*n2){lim1;L;}for(int i1;ilim;i) r[i](r[i1]1)|((i1)(L-1));fft(A,lim,1);fft(B,lim,1);for(int i0;ilim;i) A[i]A[i]*B[i];fft(A,lim,-1);for(int i0;in;i){ll now(ll)(A[n-in].x/lim0.5);ansmin(ans,tot-2*now);}printf(%lld\n,ans);
}差分和前缀和
看起来完全的裸题然鹅我就是不会 本题的一个关键思想是卷积满足结合律 所以你只要把k1的柿子找到无脑k次方即可 前缀和和模拟考试的式子一模一样 主要是卡在了差分 就是卷了一个1−x1-x1−x 其实不必“发现”可以生成函数很方便的求出来 然后k次方二项式就像喝水一样了
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e6100;
const int mod 1004535809;
#define il inline
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();x%mod;}return x*f;
}
ll n,k;
ll A[N],B[N],r[N],lim,L;
ll ksm(ll x,ll k){ll res1;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}
void ntt(ll *x,int flag){for(int i0;ilim;i){if(ir[i]) swap(x[i],x[r[i]]);}for(int l1;llim;l1){ll t0ksm(3,(mod-1)/(l1));if(flag-1) t0ksm(t0,mod-2);for(int st0;stlim;stl1){ll t1;for(int i0;il;i,tt*t0%mod){ll ux[sti],vt*x[stil]%mod;x[sti](uv)%mod;x[stil](u-vmod)%mod;}}}if(flag-1){ll niksm(lim,mod-2);for(int i0;ilim;i) x[i]x[i]*ni%mod;}
}
int main(){nread();kread();int opread();for(int i1;in;i) A[i]read();if(op0){B[0]1;for(int i1;in;i){B[i]B[i-1]*(ki-1)%mod*ksm(i,mod-2)%mod;//printf(i%d %lld\n,i,B[i]);}}else{//B[0]k%2?-1:1;B[0]1;for(int i1;in;i){B[i]-1*B[i-1]*(k-i1)%mod*ksm(i,mod-2)%mod;//B[i](B[i]mod)%mod;//printf(i%d %lld\n,i,B[i]);}for(int i0;in;i) B[i](B[i]mod)%mod;}lim1;while(limnn1) lim1,L;for(int i1;ilim;i) r[i](r[i1]1)|((i1)(L-1));ntt(A,1);ntt(B,1);for(int i0;ilim;i) A[i]A[i]*B[i]%mod;ntt(A,-1);for(int i1;in;i) printf(%lld ,A[i]);return 0;
}
/*
3 1 1
1 1 1
*/开拓者的知识
题面的图好可爱丫 虽然还是不太难但对于刚入门的我而言也可以作为一道暂时的毕业题了 我的做法
瞪眼观察失败暴力打表寻找规律卷积tmd模数用的楼上那题的1004535809忘改了WA了3次AC
打表真香 但是我们还是要给那个通项一个来头 我是根本没有理解这个柿子的性质 关键性质sum往上递归时区间只会减小不会增大 挺显然的 那么考虑对于一个固定的rrr,aia_iai会对其产生多少贡献 显然就是你取k个端点不能往外移且最终也就是每个区间都包含i的方案数 这玩意其实就是(1,i)选可重的k个做左端点(i,r)选可重的k个做右端点 经典的可重复放置的计数 就可以辣
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e6100;
const int mod 1004535809;
#define il inline
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
ll n,k;
ll A[N],B[N],r[N],lim,L;
ll ksm(ll x,ll k){ll res1;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}
void ntt(ll *x,int flag){for(int i0;ilim;i){if(ir[i]) swap(x[i],x[r[i]]);}for(int l1;llim;l1){ll t0ksm(3,(mod-1)/(l1));if(flag-1) t0ksm(t0,mod-2);for(int st0;stlim;stl1){ll t1;for(int i0;il;i,tt*t0%mod){ll ux[sti],vt*x[stil]%mod;x[sti](uv)%mod;x[stil](u-vmod)%mod;}}}if(flag-1){ll niksm(lim,mod-2);for(int i0;ilim;i) x[i]x[i]*ni%mod;}
}
ll f[N];
int main(){nread();kread();for(int i1;in;i) A[i]read()%mod;f[0]1;for(int i1;in;i) f[i]f[i-1]*(ki-1)%mod*ksm(i,mod-2)%mod;for(int i1;in;i){A[i]A[i]*f[i-1]%mod;}for(int i0;in;i){B[i]f[i];}lim1;while(limnn2) lim1,L;for(int i1;ilim;i) r[i](r[i1]1)|((i1)(L-1));ntt(A,1);ntt(B,1);for(int i0;ilim;i) A[i]A[i]*B[i]%mod;ntt(A,-1);for(int i1;in;i) printf(%lld ,A[i]);return 0;
}
/*
3 1 1
1 1 1
*/总结
说实话上道之后这些刚入门的多项式的题确实不算很难 但多项式真的是路漫漫其修远兮… 我可能会noip之后开始系统的搞一搞吧 那时候时间就充裕了 现在还是要重点在提高级内容 辣么再见~
