[RC-04] 01 背包
题目描述
有一个容积为 正无穷 的背包，你要往里面放物品。
你有 \(n\) 个物品，第 \(i\) 个体积为 \(a_i\)。
你有一个幸运数字 \(p\)，若放入的物品体积和为 \(k\)，你会得到 \(p^k\) 的收益。特别地，\(0^0=1\)。
求所有 \(2^n\) 种放入物品的方案的收益和。答案很大，因此请输出它对 \(998244353\) 取模的值。
输入格式
第一行两个整数 \(n,p\)。
接下来一行 \(n\) 个正整数 \(a_1\sim a_n\)，描述这 \(n\) 个物品的体积。
输出格式
输出一个整数，为所有 \(2^n\) 种方案的收益和对 \(998244353\) 取模的值。
样例 #1
样例输入 #1
2 2
1 4
样例输出 #1
51
提示
【样例解释】
答案为 \(2^0+2^1+2^4+2^5=51\)。
【数据范围】
对于所有数据，\(1\le n\le 10^6\)，\(0\le p,a_i<998244353\)。
详细数据范围如下表：
| 测试点编号 | \(n\) | \(p\) | \(\sum_{i=1}^na_i\) | 每测试点分数 |
|---|---|---|---|---|
| \(1\) | \(=0\) | \(2\) | ||
| \(2\sim 5\) | \(\le 22\) | \(6\) | ||
| \(6\sim 9\) | \(\le 1000\) | \(\le 1000\) | \(6\) | |
| \(10\sim 14\) | \(\le 100000\) | \(\le 100000\) | \(5\) | |
| \(15\) | \(25\) |
解析
递归枚举所有方案
所有的方案个数为 \(nums\le2^{1000000}\)
理想情况下，最多只能拿到测试点编号2~5的分数
注意要对MOD使用finnal关键字
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
static int n;
static int p;
static int[] w;
static long ans = 0;
static final int MOD = 998244353;//一定要用final关键字！！！
public static void main(String[] args) {
n = sc.nextInt();
p = sc.nextInt();
w = new int[n];
for (int i = 0; i < n; ++i) {
w[i] = sc.nextInt();
}
dfs(0,0);
System.out.println(ans);
}
static void dfs(int len, long sum) {
if (len == n) {
ans = (ans + pow(p, sum)) % MOD;
return;
}
dfs(len + 1, sum);//如果不选择当前物品
dfs(len + 1, sum + w[len]);//如果选择当前物品
}
static long pow(long x, long n) {//尽量使用位运算优化
long ans = 1;
for (; n != 0; n >>= 1, x = x * x % MOD) {
if ((n & 1) == 1) ans = ans * x % MOD;
}
return ans;
}
}
数学推导
前\(X\)个物品的总收益记为\(ans_x\)，前\(X-1\)个物品的总收益记为\(ans_{x-1}\)
以下关注\(ans_x\)的性质
设每种方案的总体积为\(k_i\)，其中 \(i\epsilon[1,2^x]\)
则\(ans_x=\sum_{i=1}^{2^x}p^{k_i}\)
对于所有方案都增加\(V\)体积
则总收益变为\(\sum_{i=1}^{2^x}p^{k_i+V}=p^{k_i+V}\times\sum_{i=1}^{2^x}p^{k_i}=p^{k_i+V}\times ans_x\)
所以，若每种方案的体积都增加\(V\)，相当于乘以\(p^{k_i+V}\)
考虑第\(X\)个物品的 \(ans_x\)
每种物品仅有两种情况
- 不选该物品，由于任意一种方案的物品总体积不变，则对\(ans_{x-1}\)无影响
- 选择该物品，对任意一种方案的物品总体积增加\(V_x\)，则\(ans_{x-1}\times p^{V_x}\)
\(ans_x\)为这两种情况的价值的和
则\(ans_x=ans_{x-1}+ans_{x-1}\times p^{V_x}=ans_{x-1}\times(1+p^{V_x})\)
\[\therefore \dfrac{ans_x}{ans_{x-1}}=1+p^{V_x} \]根据累乘法得：\(\dfrac{ans_x}{ans_0}=\)
而\(ans_0\)表示当前无任何物品，即\(V=0\)
\(\therefore ans_0=p^V=p^0=1\)
\(\therefore ans_x=\prod_1^x(1+p^{V_x})\)
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
static final long MOD = 998244353;
static int n;
static long ans = 1l, p;
static int[] V;
static long powMod(long a, int b) {
long ret = 1;
for (; b != 0; b >>= 1, a = a * a % MOD)
if ((b & 1) == 1) ret = ret * a % MOD;
return ret;
}
public static void main(String[] args) {
n = sc.nextInt();
p = sc.nextLong();
V = new int[n];
for (int i = 0; i < n; ++i) V[i] = sc.nextInt();
for (int v : V) ans = ans * (1l + powMod(p, v)) % MOD;
System.out.println(ans);
}
}