用快速幂算出n个人的所有方案数, 为2^n, 再用0-1背包的思想求出所有能力值小于k的方案数

二者之差就是最终答案

计蒜客上的一道题, 思考了很久终于想到一个解决方案 题目

题目描述

蒜头君作为蒜厂篮球队的经理，要从 n 名队员中选出若干人组队参加篮球争霸赛。为了获得参赛资格，球队中所有队员的能力值 p 之和不得小于 k。

现在给出你所有球员的能力值，请问蒜头君共有多少种组队方案。这个方案数可能很大，需要对 10007 取模。每个组队方案的人数没有任何限制。

输入格式
输入为 2 行：

第一行是两个空格隔开的整数 n, k (1 <= n <= 100, 1 <= k <= 10^4)
分别表示队员的数目和球队总能力值的下限；
第二行是 n 个空格隔开的整数 p (1 <= p <= 100)为每个球员的能力值；

输出格式
输出为 1 个整数，为蒜头君的组队方案数，结果对 10007 取模。

样例

样例输入
5 10
2 4 6 8 10

样例输出
25

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, K = 10010, MOD = 10007;

int n, k;
int p[N];
int f[N][K];

int qmi(int a, int b) {
    int res = 1 % MOD;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];

    for (int i = 0; i <= n; i++) f[i][0] = 1;
    for (int i = 0; i <= k - 1; i++) f[0][i] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k - 1; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= p[i])
                f[i][j] = (f[i][j] + f[i - 1][j - p[i]]) % MOD;
        }
    }

    cout << (qmi(2, n) - f[n][k - 1] + MOD) % MOD << endl;
    return 0;
}