D - Number of Multisets

之前寫過一個類似表示的題（2018CCPC吉林賽區——C - Justice），也是讓用$\frac{1}{2},\frac{1}{4},\frac{1}{8}\dots$湊數，我效仿之前的思路寫了個復雜度不清楚的東西（非常爆炸）最終沒能過此題

記一下自己寫的垃圾代碼

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=3110; const int mod=998244353; int n,k; int f[20][N][N]; ll dfs(int u,int cnt,int now) { if(now+cnt>n) return 0;if(!cnt) return now==n;if(u>12) return 0;if(f[u][cnt][now]!=-1) return f[u][cnt][now];f[u][cnt][now]=0;for(int i=0;i<=cnt;i++)f[u][cnt][now]=(f[u][cnt][now]+dfs(u+1,(cnt-i)*2,now+i))%mod;return f[u][cnt][now]; } int main() {//IO;int T=1;//cin>>T;while(T--){memset(f,-1,sizeof f);cin>>n>>k;cout<<dfs(1,k,0)<<'\n';}return 0; }

這題的正解時劃分dp，之前有一個整數劃分的題，我用的完全背包做的，一直沒用劃分dp做，這次遇到題目就不會了hh
大佬題解

狀態表示：$f_{(i,j)}$當前需要選出$i$個數的和時$j$的方案數
狀態轉移：我們把方案劃分成兩種情況：①至少選擇一個1。②不選擇1

• 對于①：$f_{(i,j)}=f_{(i?1,j?1)}$
• 對于②：不選擇$1$，此時問題轉化為：問有多少種選出 $i$ 個數的方案，滿足 i 個數的和為 $j$ 。這 $i$ 個數都須是 $\frac{1}{2^i}(i\in [1,\infty ))$ 的形式。我們考慮這個子問題的限制條件與原問題的限制條件的關系。如果我們將這 $i$ 個數同時$\times 2$，那么子問題的限制條件就和原問題的限制條件一致了。此時問題轉化為求解 $f_{(i,2j)}$

然后考慮一下邊界條件記憶化搜素即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=3010; const int mod=998244353; int f[N][N]; int n,k; int dfs(int i,int j) {if(i<=j) return i==j;if(!j) return 0;if(f[i][j]!=-1) return f[i][j];return f[i][j]=(dfs(i-1,j-1)+dfs(i,2*j))%mod; } int main() {//IO;int T=1;//cin>>T;while(T--){memset(f,-1,sizeof f);cin>>n>>k;cout<<dfs(n,k)<<'\n';}return 0; }

總結：dp的本質時遞推，如果能夠設計某種表示能夠有一種遞推關系，那么有可能該解就可以得出答案。

總結

以上是生活随笔為你收集整理的ARC107——D - Number of Multisets的全部內容，希望文章能夠幫你解決所遇到的問題。

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