扑克牌分组方案计数 - C++ 代码实现

扑克牌分组方案计数 - C++ 代码实现

都知道，一副扑克里有四种花色（梅花、黑桃、方块、红桃）。假设每两张同花色的牌组成一组，求当手上有 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

C++ 代码实现cpp#include #include using namespace std;

const int mod = 10007;

int main() { int N; cin >> N; vector<vector> dp(N + 1, vector(N + 1, 0)); dp[0][0] = 1; for (int i = 1; i <= N; i++) { for (int j = 0; j <= i / 2; j++) { for (int k = 0; k <= i - j; k++) { dp[i][j] = (dp[i][j] + dp[i - j][k]) % mod; } } } for (int i = 1; i <= N / 2; i++) { cout << dp[N][i] << endl; } return 0