题目描述

难度分:$2099$

输入$n$，$k(1 \leq k \leq n \leq 3000)$。

输出有多少个多重集合，满足如下条件：

1. 恰好有$n$个元素。
2. 每个元素都是$\frac{1}{2^i}$，即$1,\frac{1}{2},\frac{1}{4},\frac{1}{8},…$中的一个。
3. 这 n 个数的和恰好等于$k$。

答案模$998244353$。

输入样例$1$

4 2

输出样例$1$

2

输入样例$2$

2525 425

输出样例$2$

687232272

算法

动态规划

代码很短，但是这思路真难啊，我太菜了！

状态定义

$dp[i][j]$表示$i$个数和为$j$的多重集合数量，在这个定义下答案就是$dp[n][k]$。初始化$dp[0][0]=1$，空集合算一种方案。

状态转移

分为两种情况考虑：

1. 如果这$i$个数里面有$1$，去掉这个$1$就变成一个子问题“$i-1$个数和为$j$的多重集合数量”，状态转移方程为$dp[i][j]=dp[i-1][j-1]$。
2. 如果这$i$个数里没有$1$，实际上就相当于求“$i$个数和为$2j$的多重集合数量”，因为$1=\frac{1}{2}+\frac{1}{4}+\frac{1}{4}$等价于$2=1+\frac{1}{2}+\frac{1}{2}$，这就又凑了个$1$出来，并且凑出目标和的数还是$\frac{1}{2^i}$。状态转移方程为$dp[i][j]=dp[i][2j]$。

以上两种情况加起来就是$dp[i][j]$，只需要枚举$j$的取值即可。由于$dp[i][j]$的转移来源为$dp[i][2j]$，所以要倒序遍历$j$。$j$不可能大于$i$，因为即使所有元素都取最大的$1$，也只能凑出$i$这个和，是不可能得到$j$的，所以$j$从$i$取到$0$。

复杂度分析

时间复杂度

状态数量是$O(n^2)$，单次转移是$O(1)$的，所以整个算法的时间复杂度为$O(n^2)$。

空间复杂度

空间消耗的瓶颈就是DP矩阵，所以额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353, N = 3010;
int n, k, dp[N][N];

int main() {
    scanf("%d%d", &n, &k);
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j >= 0; j--) {
            if(j >= 1) dp[i][j] = dp[i - 1][j - 1];
            if(j*2 <= i) {
                dp[i][j] = (dp[i][j] + dp[i][j<<1]) % MOD;
            }
        }
    }
    printf("%d\n", dp[n][k]);
    return 0;
}