文章目錄

• 前言
• 力
• • 代碼
• 禮物
• • 代碼
• 差分和前綴和
• • 代碼
• 開拓者的知識(shí)
• • 代碼
• 總結(jié)

前言

這兩天由于國(guó)慶集訓(xùn)全是陰間的生成函數(shù)，所以就學(xué)了一點(diǎn)點(diǎn)相關(guān)的內(nèi)容
其實(shí)就學(xué)了個(gè)FFT和NTT
也算是點(diǎn)開了一個(gè)小小的技能點(diǎn)吧
進(jìn)入多項(xiàng)式才發(fā)現(xiàn)里面世界的廣闊
然而由于這玩意沒有一個(gè)是NOIP考點(diǎn)，而且似乎對(duì)于提高級(jí)的題目解決不會(huì)有太大的輔助作用 （不像某些神仙的數(shù)據(jù)結(jié)構(gòu)） 所以覺得后面的先放放吧
但是這幾天多項(xiàng)式也水了四紫兩藍(lán)嘛awa

力

入門題
裸且簡(jiǎn)單
但是我當(dāng)時(shí)實(shí)在是根本沒明白多項(xiàng)式是啥
所以還是看了題解
…不丟人！（理直氣壯）
一個(gè)技巧是把函數(shù)翻轉(zhuǎn)
但這本身甚至幾乎不配叫做技巧
qwq

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline const int N=1e6+100; const int M=150; const int mod=998244353; const double pi=acos(-1.0); inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,lim,k; struct node{double x,y;node(double a=0,double b=0){x=a;y=b;} }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.y+a.y*b.x}; } il node operator + (node a,node b){return (node){a.x+b.x,a.y+b.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 i=0;i<=lim;i++){if(i<r[i]) swap(x[i],x[r[i]]);}for(int l=1;l<lim;l<<=1){node o(cos(pi/l),flag*sin(pi/l));for(int st=0;st<=lim;st+=l<<1){node t(1,0);for(int j=0;j<l;j++,t=t*o){node u=x[st+j],v=t*x[st+j+l];x[st+j]=u+v;x[st+j+l]=u-v;}}}return; } int main(){n=read();for(int i=1;i<=n;i++){scanf("%lf",&A[i].x);B[i].x=(double)(1.0/i/i);C[n-i].x=A[i].x;}int L=0,lim=1;while(lim<=n<<1){lim<<=1;L++;}for(int i=1;i<=lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));fft(A,lim,1);fft(B,lim,1);fft(C,lim,1);for(int i=0;i<=lim;i++){A[i]=A[i]*B[i];C[i]=C[i]*B[i];}fft(A,lim,-1);fft(C,lim,-1);for(int i=1;i<=n;i++) printf("%lf\n",(A[i].x-C[n-i].x)/lim);return 0; } /**/

禮物

這個(gè)題是自己做的
顯然要把平方拆開
然后發(fā)現(xiàn)加上的亮度是可以O(shè)1算的
然后是變成最小化一個(gè)奇怪的東西
由于循環(huán)的性質(zhì)倍長(zhǎng)一下即可

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline const int N=2e6+100; const double pi=acos(-1.0); ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m; struct node{double x,y;node (double a=0,double b=0){x=a;y=b;} }A[N],B[N]; il node operator *(node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; } il node operator +(node a,node b){return (node){a.x+b.x,a.y+b.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 i=1;i<lim;i++){if(i<r[i]) swap(x[i],x[r[i]]);}for(int l=1;l<lim;l<<=1){node o(cos(pi/l),flag*sin(pi/l));for(int st=0;st<lim;st+=l<<1){node t(1,0);for(int i=0;i<l;i++,t=t*o){node u=x[st+i],v=t*x[st+l+i];x[st+i]=u+v;x[st+l+i]=u-v;}}} } ll x[N],y[N],tot,Sx,Sy,ans=2e18; int main(){n=read();m=read();for(int i=1;i<=n;i++) x[i]=read();for(int i=1;i<=n;i++) y[i]=read();for(int i=1;i<=n;i++){tot+=x[i]*x[i]+y[i]*y[i];Sx+=x[i];Sy+=y[i];}if(Sy<Sx) swap(Sy,Sx);ll a=(Sy-Sx)/n,b=a+1;if(a*a*n+2*a*(Sx-Sy)>b*b*n+2*b*(Sx-Sy)) swap(a,b);tot+=a*a*n+2*a*(Sx-Sy);//printf("a=%d\n",a);for(int i=1;i<=n;i++){A[i].x=x[i];B[n+n-i].x=B[n-i].x=y[i];}int lim=1,L=0;while(lim<3*n+2){lim<<=1;L++;}for(int i=1;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));fft(A,lim,1);fft(B,lim,1);for(int i=0;i<lim;i++) A[i]=A[i]*B[i];fft(A,lim,-1);for(int i=0;i<n;i++){ll now=(ll)(A[n-i+n].x/lim+0.5);ans=min(ans,tot-2*now);}printf("%lld\n",ans); }

差分和前綴和

看起來完全的裸題然鵝我就是不會(huì)
本題的一個(gè)關(guān)鍵思想是卷積滿足結(jié)合律
所以你只要把k=1的柿子找到無腦k次方即可
前綴和和模擬考試的式子一模一樣
主要是卡在了差分
就是卷了一個(gè)$1?x$
其實(shí)不必“發(fā)現(xiàn)”，可以生成函數(shù)很方便的求出來
然后k次方二項(xiàng)式就像喝水一樣了

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e6+100; const int mod= 1004535809; #define il inline inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();x%=mod;}return x*f; } ll n,k; ll A[N],B[N],r[N],lim,L; ll ksm(ll x,ll k){ll res=1;while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; } void ntt(ll *x,int flag){for(int i=0;i<lim;i++){if(i<r[i]) swap(x[i],x[r[i]]);}for(int l=1;l<lim;l<<=1){ll t0=ksm(3,(mod-1)/(l<<1));if(flag==-1) t0=ksm(t0,mod-2);for(int st=0;st<lim;st+=l<<1){ll t=1;for(int i=0;i<l;i++,t=t*t0%mod){ll u=x[st+i],v=t*x[st+i+l]%mod;x[st+i]=(u+v)%mod;x[st+i+l]=(u-v+mod)%mod;}}}if(flag==-1){ll ni=ksm(lim,mod-2);for(int i=0;i<lim;i++) x[i]=x[i]*ni%mod;} } int main(){n=read();k=read();int op=read();for(int i=1;i<=n;i++) A[i]=read();if(op==0){B[0]=1;for(int i=1;i<=n;i++){B[i]=B[i-1]*(k+i-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 i=1;i<=n;i++){B[i]=-1*B[i-1]*(k-i+1)%mod*ksm(i,mod-2)%mod;//B[i]=(B[i]+mod)%mod;//printf("i=%d %lld\n",i,B[i]);}for(int i=0;i<=n;i++) B[i]=(B[i]+mod)%mod;}lim=1;while(lim<n+n+1) lim<<=1,L++;for(int i=1;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));ntt(A,1);ntt(B,1);for(int i=0;i<lim;i++) A[i]=A[i]*B[i]%mod;ntt(A,-1);for(int i=1;i<=n;i++) printf("%lld ",A[i]);return 0; } /* 3 1 1 1 1 1 */

開拓者的知識(shí)

題面的圖好可愛丫！
雖然還是不太難，但對(duì)于剛?cè)腴T的我而言，也可以作為一道暫時(shí)的畢業(yè)題了
我的做法：

瞪眼觀察（失敗）

暴力打表

尋找規(guī)律

卷積

tmd模數(shù)用的樓上那題的1004535809忘改了WA了3次

AC

打表真香
但是我們還是要給那個(gè)通項(xiàng)一個(gè)來頭
我是根本沒有理解這個(gè)柿子的性質(zhì)
關(guān)鍵性質(zhì)：sum往上遞歸時(shí)，區(qū)間只會(huì)減小不會(huì)增大
挺顯然的
那么考慮對(duì)于一個(gè)固定的$r$,$a_i$會(huì)對(duì)其產(chǎn)生多少貢獻(xiàn)
顯然就是你取k個(gè)端點(diǎn)不能往外移，且最終（也就是每個(gè)）區(qū)間都包含i的方案數(shù)
這玩意其實(shí)就是(1,i)選可重的k個(gè)做左端點(diǎn)，(i,r)選可重的k個(gè)做右端點(diǎn)
經(jīng)典的可重復(fù)放置的計(jì)數(shù)
就可以辣

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e6+100; const int mod= 1004535809; #define il inline inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } ll n,k; ll A[N],B[N],r[N],lim,L; ll ksm(ll x,ll k){ll res=1;while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; } void ntt(ll *x,int flag){for(int i=0;i<lim;i++){if(i<r[i]) swap(x[i],x[r[i]]);}for(int l=1;l<lim;l<<=1){ll t0=ksm(3,(mod-1)/(l<<1));if(flag==-1) t0=ksm(t0,mod-2);for(int st=0;st<lim;st+=l<<1){ll t=1;for(int i=0;i<l;i++,t=t*t0%mod){ll u=x[st+i],v=t*x[st+i+l]%mod;x[st+i]=(u+v)%mod;x[st+i+l]=(u-v+mod)%mod;}}}if(flag==-1){ll ni=ksm(lim,mod-2);for(int i=0;i<lim;i++) x[i]=x[i]*ni%mod;} } ll f[N]; int main(){n=read();k=read();for(int i=1;i<=n;i++) A[i]=read()%mod;f[0]=1;for(int i=1;i<=n;i++) f[i]=f[i-1]*(k+i-1)%mod*ksm(i,mod-2)%mod;for(int i=1;i<=n;i++){A[i]=A[i]*f[i-1]%mod;}for(int i=0;i<=n;i++){B[i]=f[i];}lim=1;while(lim<n+n+2) lim<<=1,L++;for(int i=1;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));ntt(A,1);ntt(B,1);for(int i=0;i<lim;i++) A[i]=A[i]*B[i]%mod;ntt(A,-1);for(int i=1;i<=n;i++) printf("%lld ",A[i]);return 0; } /* 3 1 1 1 1 1 */

總結(jié)

說實(shí)話上道之后這些剛?cè)腴T的多項(xiàng)式的題確實(shí)不算很難
但多項(xiàng)式真的是路漫漫其修遠(yuǎn)兮…
我可能會(huì)noip之后開始系統(tǒng)的搞一搞吧
那時(shí)候時(shí)間就充裕了
現(xiàn)在還是要重點(diǎn)在提高級(jí)內(nèi)容
辣么，再見~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的多项式乘法：练习总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。