骨牌2

形式化题目

本题的材料里存在两套互不相同的数学结构，先把它们分别写清楚。

题面语义：给定整数 $N \geqslant 0$ ，求用若干块 $1 \times 2$ 骨牌（可横放、可竖放）无重叠、无溢出地铺满 $2 \times N$ 棋盘（共 $2N$ 个格子）的方案数。

随题测试数据语义：给定整数 $n, k$ ，求把 $n$ 表示成 $k$ 个正整数之和的方案数，其中两个表示只要加数集合相同就算同一种（不考虑顺序）：

\sum_{i=1}^{k} x_i = n, \qquad x_i \in \mathbb{Z}^{+}, \qquad (x_1, \dots, x_k) \text{ 不计排列}

前者是骨牌覆盖计数（ROJ 官方标签「动态规划、状态压缩」与它一致），后者是经典的整数划分计数。两者的关系见 ## 数据说明。

$2 \times 3$ 的棋盘共有 $3$ 种铺法。下面用 ASCII 图列出全部三种，相同字母表示同一块骨牌（每两行是一张棋盘）：

text

1
2
3
4
5
6
7铺法一：三块都竖放        铺法二：第 1 列竖放，后两列上下各横放一块
A B C                     A B B
A B C                     A C C

铺法三：前两列上下各横放一块，第 3 列竖放
A A C
B B C

这三类恰好对应递推的两个分支：铺法一、二的最左列都被一块竖放的骨牌独占（剩下 $2 \times 2$ ，对应 $f(N-1)=f(2)=2$ ），铺法三的最左两列被上下两块横放的骨牌一起占满（剩下 $2 \times 1$ ，对应 $f(N-2)=f(1)=1$ ）， $2+1=3=f(3)$ 。把全部铺法按"最左列怎么盖"分类，正是下面解法一的出发点。

解法总览

本题的两个解法解决不是同一个问题，没有"朴素 → 优化"的递进关系：

解法一按题面语义求解： $2 \times N$ 棋盘被 $1 \times 2$ 骨牌铺满的方案数，答案是斐波那契型递推。参考实现放在 domino.py。
解法二按随题测试数据的实际语义求解： $n$ 分成 $k$ 份正整数的无序划分方案数，用完全背包计数。这是本题的正式主解，放在 main.py。

之所以两个都给出：只看题面会写出解法一，但它与随题数据（整数划分）对不上；只看数据会失去题面想教的内容。两个解法都列出，读者才能同时理解题意和数据。

解法一：题面语义—— $2 \times N$ 骨牌覆盖

思路

朴素想法是把棋盘当成 $2N$ 个格子的集合，枚举"放一块骨牌 → 找下一个空格 → 再放"的所有铺法。它能给出正确答案，但搜索树规模随 $N$ 指数增长， $N$ 稍大就跑不完。

瓶颈在于重复：同一个结果会被不同的放置顺序反复枚举。棋盘是规则长条，铺放可以按列从左往右推进，一旦前若干列被铺满，剩余问题只取决于"还剩多少列"，与前面具体怎么铺的细节无关。于是状态只需一个参数。

优化思路：只看最左边一列（前面列已全部铺满）。设左上是 $(1,1)$ ，它必被某块骨牌覆盖，而这块骨牌的另一格只有两种可能：

在正下方 $(2,1)$ ，即竖放：占满第 1 列，问题缩小为 $2 \times (N-1)$ ；
在右侧 $(1,2)$ ，即横放：此时 $(2,1)$ 也必须被覆盖，而它的另一格只能是 $(2,2)$ （ $(2,0)$ 越界、 $(1,1)$ 已被占用），于是上下两块横放的骨牌一起占满前两列，问题缩小为 $2 \times (N-2)$ 。

两种情形互斥且穷尽了 $(1,1)$ 的所有覆盖方式，因此

f(N) = f(N-1) + f(N-2), \qquad f(0) = 1,\quad f(1) = 1

其中 $f(0)=1$ 表示空棋盘（"什么都不铺"这一种方案）， $f(1)=1$ 表示只能竖放一块。

递推数值从 $f(0)$ 起为 $1, 1, 2, 3, 5, 8, 13, \dots$ ；因为 $f(0)=f(1)=1$ ，它与常见的斐波那契数列 $(F_1, F_2, F_3, \dots) = (1, 1, 2, \dots)$ 只差一个下标，即 $f(N) = F_{N+1}$ 。其中 $f(0)=1$ 对应空棋盘、 $f(1)=1$ 对应唯一那种竖放，而 $f(3)=3$ 正好对应上面画出的三种铺法。

代码

题面语义的参考实现（不是本题的提交文件；提交解见解法二）。

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 02:17
# update_at: 2026-10-01 02:33
#
# 本题面语义（2×N 棋盘用 1×2 骨牌铺满）的参考实现，对应 index.md 的「解法一」。
# 注意：随题测试数据实际考查的是整数划分，提交解必须用 main.py。

import sys


def count_tilings(width: int) -> int:
    """求 2×width 棋盘被 1×2 骨牌铺满的方案数（滚动变量，只保留前两项）。"""
    prev, cur = 1, 1                          # f(0) = 1（空棋盘）、f(1) = 1（竖放一块）
    for _ in range(width):
        prev, cur = cur, prev + cur            # f(i) = f(i-1) + f(i-2)
    return prev


def solve() -> None:
    width = int(sys.stdin.buffer.read().split()[0])   # 题面只说"2×N 的棋盘"，N 是唯一输入
    print(count_tilings(width))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(N)$ ，一次循环 $N$ 轮、每轮常数次加法。若 $N$ 达到 $10^9$ 级别，把递推写成矩阵形式 $\begin{pmatrix} f(i) \\ f(i-1) \end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix} f(i-1) \\ f(i-2) \end{pmatrix}$ 的快速幂可降为 $O(\log N)$ ；题面没有给 $N$ 的范围，随题数据也不涉及这一层。
空间复杂度： $O(1)$ ，只用 prev、cur 两个滚动变量。

解法二：评测数据语义——整数划分

这一层才是随题测试数据真正考查的问题，main.py 实现的就是它。

思路

朴素想法沿用评测程序 std.cpp 的做法：枚举单调不降的 $k$ 元组 $(x_1 \leqslant x_2 \leqslant \dots \leqslant x_k)$ 且 $\sum x_i = n$ ，因为固定了"不降"，每个无序划分恰好被枚举一次，答案正确。 $n \leqslant 200, k \leqslant 7$ 时可以跑完。

瓶颈是搜索树里没有子问题复用：处在"已放 $j$ 份、和为 $s$ 、下一份不小于 $v$ "这一状态的不同分支，会各自重新枚举同一批后续方案。状态数远小于搜索树节点数，说明存在大量重复。

优化思路分三步。

消掉"每份至少 1"。每份先各分 1，共消耗 $k$ ；剩下的 $m = n - k$ 可以任意分配，于是问题等价于把 $m$ 分成至多 $k$ 份（可以为 0、可以重复）。若 $n < k$ ，无解，答案为 0。
认出这是完全背包。"把 $m$ 拆成不超过 $k$ 的部分、每部分可重复"与 "用面额 $1, 2, \dots, k$ 的硬币凑出 $m$ 、每种面额可用无限次"是同一个计数：把一个大小为 $c$ 的部分记作一枚面额 $c$ 的硬币即可。
确认"不计顺序"被自动满足。外层按面额升序枚举、内层按目标值升序滚动，每个划分只会沿"面额从小到大"这唯一一条路径被构造出来， $\{1,3\}$ 与 $\{3,1\}$ 不会各算一次。

转移方程就是完全背包的计数形式：

dp[x] \mathrel{+}= dp[x - \text{coin}] \qquad (\text{coin} = 1, 2, \dots, k;\ x = \text{coin}, \dots, m)

$n = 7, k = 3$ （即 $m = 4$ ）的滚动过程：

已处理面额	$dp[0]$	$dp[1]$	$dp[2]$	$dp[3]$	$dp[4]$
初始（还没处理任何面额）	1	0	0	0	0
$\text{coin}=1$	1	1	1	1	1
$\text{coin}=2$	1	1	2	2	3
$\text{coin}=3$	1	1	2	3	4

行列含义：行是"已经考虑过哪些面额"，列是目标值 $x$ ，单元格 $dp[x]$ 表示 只用这些面额凑出 $x$ 的方案数。初始只有 $dp[0]=1$ （空方案）；每处理一种面额，其右侧格子都可以"再用一枚该面额"累加。最后 $dp[4]=4$ ，对应 $7$ 拆成 3 份的四种划分 $\{1,1,5\},\{1,2,4\},\{1,3,3\},\{2,2,3\}$ 。

内层必须升序：dp[x - coin] 用的是本轮刚更新过的值，代表"还能再用一枚同面额硬币"，这正是完全背包与 0/1 背包的唯一区别。写成降序则每种面额最多用一次，上面 $n=7,k=3$ 的四种划分里只剩 $\{1,2,4\}$ （另三种都需要重复面额），答案变成 1 而不是 4。

代码

Python 版：

python

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
32
33
34
35
36
37
38
39
40#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 02:17
# update_at: 2026-10-01 02:33
#
# 数据说明：本题源仓库随题的测试数据与评测程序 std.cpp 实际考查的是「整数划分」，
# 而不是题面写的 2×N 骨牌覆盖 —— 上游 roj/1677 的 data/、data.py、std.cpp 与
# roj/1675 字节级相同，输入是 `n k`，std.cpp 数的是把 n 拆成 k 份正整数的方案数。
# 下面的 count_partitions 复刻 std.cpp 的语义，使输出与评测数据逐字节一致；
# 题面语义下的骨牌解法 f(n) = f(n-1) + f(n-2) 见 index.md 的 ### 思路。

import sys


def count_partitions(total: int, parts: int) -> int:
    """求把 total 分成 parts 份正整数（不计顺序）的方案数。

    std.cpp 的 dfs 枚举的是"单调不降的 parts 元组"，与无序划分是同一计数。
    每份至少为 1，先各减 1，问题等价于把 total - parts 用不超过 parts 的数拆分：
    这是完全背包的计数版本，面额 1..parts 可重复使用，n 升序滚动即可。
    """
    rest = total - parts
    if rest < 0:
        return 0                               # 份数比总和还多，无解
    dp = [1] + [0] * rest                      # dp[0] = 1：拆 0 只有空方案
    for coin in range(1, parts + 1):
        for used in range(coin, rest + 1):
            dp[used] += dp[used - coin]        # 再添一枚面额 coin 的方案数
    return dp[rest]


def solve() -> None:
    total, parts = map(int, sys.stdin.buffer.read().split())
    print(count_partitions(total, parts))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
32
33
34
35
36
37
38
39
40
41/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:45
 * update_at: 2026-10-06 01:45
 */
#include <cstdio>

typedef long long ll;

// 数据说明：本题源仓库随题的测试数据与评测程序 std.cpp 实际考查的是「整数划分」，
// 而不是题面写的 2×N 骨牌覆盖（上游 1677 的 data/、data.py、std.cpp 与 1675 字节级相同）。
// 输入是 n k，要求把 n 拆成 k 份正整数（不计顺序）的方案数，本题解按此语义实现。

const int MAXN = 1000005;  // 随题数据 n<=200，这里留足余量，避免越界

ll dp[MAXN];               // dp[x]：已经考虑过的面额凑出 x 的方案数（完全背包计数）

int main() {
    ll n, k;
    scanf("%lld %lld", &n, &k);

    // 每份至少为 1，先各减 1，余下 rest 用不超过 k 的数拆分（可以重复、可以为 0）
    ll rest = n - k;
    if (rest < 0) {
        printf("0\n");
        return 0;
    }

    dp[0] = 1;             // 凑 0 只有空方案
    // 外层按面额升序、内层按目标值升序滚动，保证每个划分只沿唯一路径被构造一次
    for (ll coin = 1; coin <= k; coin++) {
        for (ll used = coin; used <= rest; used++) {
            dp[used] += dp[used - coin];   // 再添一枚面额 coin 的方案数
        }
    }

    printf("%lld\n", dp[rest]);
    return 0;
}

复杂度

时间复杂度： $O(k \cdot (n - k))$ 。外层 $k$ 种面额、内层至多 $n-k$ 个目标值，每个单元格一次加法。代入随题数据上界（ $k \leqslant 7$ 、 $n \leqslant 200$ ），总操作数不到 $1400$ 次。
空间复杂度： $O(n - k)$ 的一维 dp 数组，上界 198 个整数，远低于 128 MB 限制。

复杂度对比

解法	问题	时间复杂度	空间复杂度	与数据的关系
一（`domino.py`）	$2 \times N$ 骨牌覆盖	$O(N)$ （递推），快速幂可到 $O(\log N)$	$O(1)$	与随题数据不符，仅供理解题面
二（`main.py`）	$n$ 分成 $k$ 份无序划分	$O(k(n-k))$	$O(n-k)$	与随题数据一致，是提交解

数据说明

本题测试数据与题面不一致

下面记录的是源仓库测试数据的实际状态，不是算法结论。

核对真实数据时发现：ROJ 1677 的题面是「 $2 \times N$ 骨牌覆盖」，但随题测试数据与评测程序实际考查的是整数划分：

核对项	结果
`data/problem1.in`	`106 6` —— 两个整数 `n k`，不是骨牌题的单个 $N$
`data/problem1.out`	`189509`
`std.cpp`	`dfs` 枚举单调不降的 `k` 元组并检查剩余，统计的正是 $n$ 拆成 $k$ 份的方案数
`std.cpp` 与 `roj/1675/std.cpp`	字节级相同（md5 均为 `c492e1bc35b8a823812f2eb545292e02`）
`data.py`	与 `roj/1675/data.py` 相同：`randint(10,200)`、`randint(3,7)`
`data/.in`、`data/.out`、`data.json`	与 `roj/1675` 全部逐字节相同
上游仓库	`raw.githubusercontent.com/rainboyOJ/problems/master/roj/1677/` 也是这一份，不是本地下载故障

也就是说，1677 的随题数据疑似是相邻题 1675「数字划分」的数据被一起放进了同一个目录（1676「骨牌1」目录下也是同一份数据）。用整数划分的递推复算 10 组数据，与 .out 10/10 全部一致，例如 problem1 的 $p(106,6) = 189509$ 。

由此决定了本目录的两个实现口径：

main.py（提交解）实现整数划分，与评测数据逐字节一致，这也是 ### 代码 中正式主解的位置；
### 思路 的解法一按题面语义给出骨牌正解（domino.py），它在一份按题面正常生成 的数据上才是正确答案。

给读者的建议

这道题的正解要看你手上的数据是哪一份：按题面自己造 $2 \times N$ 数据时用解法一（ $f(N)=f(N-1)+f(N-2)$ ）；面对本目录的随题数据时用解法二（完全背包计数）。两份代码都只有十几行，值得对照阅读。

总结

题面模型： $2 \times N$ 棋盘用 $1 \times 2$ 骨牌铺满。按最左列的两种盖法分类，立即得到 $f(N) = f(N-1) + f(N-2)$ ， $f(0)=f(1)=1$ 。
数据模型： $n$ 分成 $k$ 份正整数的无序划分。每份先减 1 后等价于「用面额 $1..k$ 的硬币凑出 $n-k$ 」，即完全背包计数，转移 $dp[x] \mathrel{+}= dp[x-\text{coin}]$ 。
关键实现点：完全背包的内层必须升序，否则每种面额只能用一次， $n=7,k=3$ 只会剩下 $\{1,2,4\}$ ，答案变成 1。
数据瑕疵：随题数据与 std.cpp 均与 1675 字节级相同，考查的是整数划分而非骨牌，因此提交解按整数划分实现，题面语义的解另附并在此透明说明。
复杂度：解法一 $O(N)$ 时间、 $O(1)$ 空间；解法二 $O(k(n-k))$ 时间、 $O(n-k)$ 空间。