不會五邊形數的菜雞的分塊亂搞

LOJ #6268

---

題意

求前$ n$個數的整數劃分方案數，$ n \leq 10^5$

---

$ Solution$

考慮暴力$ DP$

$ f(x,y)$表示放了$ x$個物品總體積為$ y$的方案數

轉移分增加一個物品和將前面所有物品的體積均增加$ 1$兩種

?

$ g(x,y)$表示用大小不超過$x$的物品裝出體積為$y$的方案數

類似完全背包轉移即可

?

對$ n$分塊

對大小不超過$ \sqrt{n}$的物品采取第二種轉移方式，時間復雜度$ O(n \sqrt{n})$

對大小超過$ \sqrt{n}$的物品由于數量不超過$ \sqrt{n}$種，采取第一種轉移方式，時間復雜度同上

然后用$ NTT$合并即可

總復雜度可被看成$ O(n \sqrt{n})$

---

$ my \ code$

#include<ctime> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define p 998244353 #define rt register int #define ll long long using namespace std; inline ll read(){ll x = 0; char zf = 1; char ch = getchar();while (ch != '-' && !isdigit(ch)) ch = getchar();if (ch == '-') zf = -1, ch = getchar();while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf; } void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);} void writeln(const ll y){write(y);putchar('\n');} int i,j,k,m,n,x,y,z,cnt; int A[270010],B[270010],R[270010],b[335][100010]; int ksm(int x,int y){int ans=1;for(rt i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*x*ans%p;return ans; } void NTT(int n,int *A,int fla){for(rt i=0;i<n;i++)if(i>R[i])swap(A[i],A[R[i]]);for(rt i=1;i<n;i<<=1){int w=ksm(3,(p-1)/2/i);for(rt j=0;j<n;j+=i<<1){int K=1;for(rt k=0;k<i;k++,K=1ll*K*w%p){int x=A[j+k],y=1ll*K*A[i+j+k]%p;A[j+k]=(x+y)%p,A[i+j+k]=(x-y)%p;}}}if(fla==-1){reverse(A+1,A+n);int invn=ksm(n,p-2);for(rt i=0;i<n;i++)A[i]=1ll*A[i]*invn%p;} } int main(){n=read();int blo=(int)sqrt(n);A[0]=1; for(rt i=1;i<=blo;i++)for(rt j=i;j<=n;j++)(A[j]+=A[j-i])%=p;b[0][0]=1;for(rt i=1;i*blo<=n;i++)for(rt j=1;j+i*blo<=n;j++){b[i][j]=(b[i-1][j-1]+((j>=i)?b[i][j-i]:0))%p;(B[j+i*blo]+=b[i][j])%=p;}A[0]=B[0]=1;int lim=1;while(lim<=n+n)lim<<=1;for(rt i=1;i<lim;i++)R[i]=(R[i>>1]>>1)|(i&1)*(lim>>1); NTT(lim,A,1);NTT(lim,B,1);for(rt i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%p;NTT(lim,A,-1);for(rt i=1;i<=n;i++)writeln((A[i]+p)%p);return 0; }

?

轉載于:https://www.cnblogs.com/DreamlessDreams/p/10079374.html

總結

以上是生活随笔為你收集整理的LOJ #6268 分拆数的全部內容，希望文章能夠幫你解決所遇到的問題。

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