ARC107D

lsj2009 · 2023-10-27 21:04:18 · 题解

好题！

考虑到一个集合的元素是无序的，我们不妨将其按从小到大排序，例如这么一个集合：\{\frac{1}{8},\frac{1}{2},\frac{1}{2},1\}，他是如何得到的？先得到一个集合 \{1,1,1,1\}，然后将 1\sim 1 的前缀乘两个 \frac{1}{2}，再将 1\sim 3 的前缀乘一个 \frac{1}{2}。

也就是说，任意一个题目所求的集合均可以表示成先加入 n 个 1，然后对于每个前缀乘上若干个 \frac{1}{2}。

通过上面那个思路，我们每一次拓展集合，我们不妨先加入一个 1，然后可以选择将 1\sim i 这个前缀乘上若干个 \frac{1}{2}，再考虑如何实现。

设 f_{i,j} 表示前 i 个数和为 j 的方案总数，加入 1 相当于 f_{i,j}\gets f_{i-1,j-1}。

而乘 \frac{1}{2}，则是将 j 减半，即 f_{i,j}\gets f_{i,j\times 2}。需要注意的是，这里之所以是 f_{i,j\times 2} 而不是 f_{i-1,j\times 2}，是因为我们可以选择若干个 \frac{1}{2}，也就是相当于一个完全背包。

然后就做完了，复杂度 \Theta(n^2)。

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=3e3+5,MOD=998244353;
int f[N][N];
signed main() {
    int n,k;
    scanf("%d%d",&n,&k);
    f[0][0]=1;
    rep(i,1,n) {
        per(j,i,0) {
            f[i][j]=f[i-1][j-1];
            if(j*2<=i)
                f[i][j]=(f[i][j]+f[i][j*2])%MOD;
        }
    }
    printf("%d\n",f[n][k]);
    return 0;
}