題目鏈接：點擊查看

題目大意：給出 $n$ 個連續的小球，每次可以選擇單獨的一個或者相鄰的兩個小球分成一組，允許有剩余的小球，問恰好分成 $k\in \{1,2,3,?,m\}$ 組的方案數分別是多少。

題目分析：設 $dp[i][j]$ 為前 $i$ 個小球分成 $j$ 組的方案數，不難推出：
$$dp[i][j]=dp[i?1][j]+dp[i?1][j?1]+dp[i?2][j?1]$$

由于不會特征方程求解通項公式，只會用矩陣快速冪套多項式優化上述過程，時間復雜度 $O(m\log n\log m)$，比賽時無論如何卡常都 $TLE$，但是補題的時候交了一發很神奇的卡常卡過去了，離譜。

然后這個模板在矩陣自乘的時候做了一些小優化，將原本 $8$ 次的 $DFT$ 下降成了 $4$ 次，可以說是優化了很多了。

具體推導可以參考：2021HDU多校8 - 7057 Buying Snacks

一份常數更小的代碼：

#include<bits/stdc++.h> using namespace std; #define SZ(x) ((int)(x).size()) #define rep(i,a) for(int i=0;i<(a);++i) #define repi(i,a) for(int i=1;i<=(a);++i) template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } typedef long long ll; const int Inf=0x3f3f3f3f; const int jt=998244353,rg=3,mlg=20; void inline add(int &a,int b) {a+=b-jt;a+=(a>>31)&jt; } void inline sub(int &a,int b) {a-=b;a+=(a>>31)&jt; } void inline mul(int &a,int b) {a=(ll)a*b%jt; } int inline Add(int a,int b) {return a+b>=jt?a+b-jt:a+b; } int inline Sub(int a,int b) {return a-b<0?a-b+jt:a-b; } int inline Mul(int a,int b) {return (ll)a*b%jt; } typedef vector<int>Poly; int inline ksmii(int a,int b) {int res=1;while(b) {if(b&1) {mul(res,a);}mul(a,a);b>>=1;}return res; } namespace Fourier {int ho[mlg+1][1<<mlg],omg[mlg+1][1<<mlg],in[mlg+1];void init() {rep(lg,mlg+1) {int N=1<<lg;if(lg) {rep(i,N) {ho[lg][i]=(ho[lg][i>>1]>>1)|((i&1)<<(lg-1));}}int omega=ksmii(rg,(jt-1)>>(lg+1)),ome=1;rep(i,N) omg[lg][i]=ome,mul(ome,omega);in[lg]=ksmii(N,jt-2);}}void inline fft(int a[],int lg,int inv) {int N=1<<lg;rep(i,N) {if(ho[lg][i]<i) {swap(a[i],a[ho[lg][i]]);}}rep(l,lg) {int i=1<<l;for(int j=0;j<N;j+=i<<1) {int *x=a+j,*y=x+i,*o=omg[l],tmp;rep(k,i) {tmp=Mul(*y,*o);*y=Sub(*x,tmp);add(*x,tmp);++x,++y,++o;}}}if(!~inv) {reverse(a+1,a+N);rep(i,N) {mul(a[i],in[lg]);}}} }int N,M; int tmp[2][2][1<<mlg],tmq[2][2][1<<mlg],tmr[2][2][1<<mlg];struct Matrix {Poly a[2][2];inline Poly *operator[](int x) {return a[x];}inline const Poly *operator[](int x) const {return a[x];}inline Matrix operator*(const Matrix &b) const {int ts1=0,ts2=0;rep(i,2) rep(j,2) ts1=max(ts1,SZ(a[i][j]));rep(i,2) rep(j,2) ts2=max(ts2,SZ(b[i][j]));int ts=ts1+ts2,lg=0;while((1<<lg)<ts) ++lg;int N=1<<lg;rep(i,2) rep(j,2) {rep(k,N) tmp[i][j][k]=k<SZ(a[i][j])?a[i][j][k]:0;Fourier::fft(tmp[i][j],lg,1);}rep(i,2) rep(j,2) {rep(k,N) tmq[i][j][k]=k<SZ(b[i][j])?b[i][j][k]:0;Fourier::fft(tmq[i][j],lg,1);}rep(i,2) rep(j,2) rep(k,N) tmr[i][j][k]=0;rep(p,N) rep(i,2) rep(j,2) rep(k,2) add(tmr[i][k][p],Mul(tmp[i][j][p],tmq[j][k][p]));rep(i,2) rep(j,2) Fourier::fft(tmr[i][j],lg,-1);Matrix res;if(ts>M+5) ts=M+5;rep(i,2) rep(j,2) {res[i][j].resize(ts);rep(k,ts) res[i][j][k]=tmr[i][j][k];}return res;} }; void MUL(Matrix &a){int ts=0;rep(i,2) rep(j,2) ts=max(ts,SZ(a[i][j]));int lg=0;ts*=2;while((1<<lg)<ts) ++lg;int N=1<<lg;rep(i,2) rep(j,2) {rep(k,N) tmp[i][j][k]=k<SZ(a[i][j])?a[i][j][k]:0;Fourier::fft(tmp[i][j],lg,1);}rep(i,2) rep(j,2) rep(k,N) tmr[i][j][k]=0;rep(p,N) rep(i,2) rep(j,2) rep(k,2) add(tmr[i][k][p],Mul(tmp[i][j][p],tmp[j][k][p]));rep(i,2) rep(j,2) Fourier::fft(tmr[i][j],lg,-1);if(ts>M+5) ts=M+5;rep(i,2) rep(j,2) {a[i][j].resize(ts);rep(k,ts) a[i][j][k]=tmr[i][j][k];} } inline Matrix ksmii(Matrix a,int b) {Matrix res;rep(i,2) rep(j,2) res[i][j]=i==j?Poly{1}:Poly{};while(b) {if(b&1) {res=res*a;}MUL(a);b>>=1;}return res; } Matrix tr,ntr,ini; void solve() {scanf("%d%d",&N,&M);ntr=ksmii(tr,N);Matrix res=ntr*ini;Poly &ans=res[1][0];repi(i,M) write(ans[i]),putchar(' ');puts(""); } int main() {Fourier::init();tr[0][0]=Poly{1,1};tr[0][1]=Poly{0,1};tr[1][0]=Poly{1};tr[1][1]=Poly{};ini[0][0]={1,1};ini[1][0]={1};int T=1;while(T--) solve();return 0; }

總結

以上是生活随笔為你收集整理的2021-2022年度第三届全国大学生算法设计与编程挑战赛（秋季赛）- 分组(矩阵快速幂套NTT优化dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。