扑克牌组合方案计数 - 算法竞赛题解

【题目描述】 都知道，一副扑克里有四种花色（梅花、黑桃、方块、红桃）。 假设每两张同花色的牌组成一组，求当手上有 N 张牌时，至少组成 1 到 N/2(向下取整)组牌时有多少种不同的方案？ 例如：手中可有 N 张牌，可以构成： 梅花 黑桃 方块 红桃 a 张 b 张 c 张 d 张 a+b+c+d=N,其中 0<=a,b,c,d<=n 即：求上表格中所有不同方案能组成 1 到 N/2 组的方案数。 例如 n=5 时，只能构成 1 组、2 组，不能构成 3 组；构成举例如下： 梅花 黑桃 方块 红桃 构成方案说明 0 张 2 张 3 张 0 张 黑桃或方块可构成 1 组，没有能构成 2 组的花色 2 张 2 张 0 张 1 张 梅花或黑桃可构成 1 组，没有能构成 2 组的花色 4 张 0 张 1 张 0 张 梅花可构成 1 组，（梅花也能构成 2 组 0 张 5 张 0 张 0 张 黑桃有 5 张可构成 1 组，也能构成 2 组，但不能构成 3 组 „„„„„„ „„„„„„ 由于最后答案可能会很大，请输出答案 mod 10007 的结果。 【输入格式】 一个数，N。 【输出格式】 共 N/2(向下取整)行，第 i 行表示至少组成 i 组牌时有多少种不同的方案。 【输入样例 1】 3 【输出样例 1】 5 16 【样例解释 1】 以下列举当手中有 3 张牌时，每种花色的张数，可能有以下 16 种情况： 梅花 黑桃 方块 红桃 0 0 0 3 0 0 1 2 0 0 2 1 0 0 3 0 0 1 0 2 0 1 2 0 0 2 0 1 0 2 1 0 0 3 0 0 1 0 0 2 1 0 2 0 1 2 0 0 2 0 0 1 2 0 1 0 2 1 0 0 3 0 0 0 【输入样例 2】 4 【输出样例 2】 34 10 【数据范围】 30% N<=1000 100% N<=10000 cpp code内容：#include #include using namespace std;

const int MOD = 10007;

int main() { int N; cin >> N;

vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
dp[0][0] = 1;

for (int i = 1; i <= N; i++) {
    dp[i][0] = 1;
    for (int j = 1; j <= i / 2; j++) {
        for (int k = 0; k <= i; k++) {
            dp[i][j] = (dp[i][j] + dp[i - k][j - 1]) % MOD;
        }
    }
}

for (int i = 1; i <= N / 2; i++) {
    cout << dp[N][i] << endl;
}

return 0;