考点
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
static const int maxn = 1e3 + 50, mod = 1e9 + 7;
long long f[maxn];
int n;
long long ksm(long long x, int k) {
long long res = 1;
while (k) {
if (k & 1) res = (res * x) % mod;
x = (x * x) % mod;
k >>= 1;
}
return res;
}
int countPartitions(vector<int>& nums, int K) {
long long sum = 0;
for (int i = 0; i < nums.size(); ++i) sum = (sum + nums[i]) % mod;
if (sum < 2LL * K % mod) return 0;
memset(f, 0, sizeof(f));
n = nums.size();
f[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = K - 1; j >= nums[i]; --j) {
f[j] = (f[j] + f[j - nums[i]]) % mod;
}
}
sum = 0;
for (int i = 0; i <= K - 1; ++i) sum = (sum + f[i]) % mod;
return (ksm(2, n) - 2 * sum % mod + mod) % mod;
}
};
|
思路
先判定有没有解，即数组的和是否大于2 * K
由题，答案为选x个数，其和大于等于k放第一组，不选的数其和也大于等于k放第二组的选法乘一个2，乘2是因为两组可以交换顺序
但和的范围过大，考虑逆命题，两个组的和同时大于等于k的逆命题就是至少有一个组的和小于k
所以答案修正为：
1
| 2^n（每个数去第一组还是第二组） - 2 * 至少有一个组的和小于k的选法
|
这就是经典的01背包裸题，上模板即可