鸣人的影分身

题目描述

鸣人的查克拉能量为 $M$ ，影分身个数最多为 $N$ ，每个分身可以分到 $0$ 点查克拉，问把 $M$ 点能量分完的不同分配方法数 $K$ （交换两个分身的点数算同一种方案）。第一行是测试数据组数 $t$ （ $0 \leqslant t \leqslant 20$ ），以下每行两个整数 $M, N$ （ $1 \leqslant M, N \leqslant 10$ ），每组输出一行 $K$ ；样例输入 1 / 7 3，输出 8。

思路

把一种方案写成非递增序列 $a_1 \geqslant a_2 \geqslant \dots \geqslant a_N \geqslant 0$ （不足 $N$ 个的位置补 $0$ ），它与分配方案一一对应，于是设 $f(M,N)$ 为和为 $M$ 的这类序列数。看末位 $a_N$ ：为 $0$ 时方案数是 $f(M,N-1)$ ，否则全体减 $1$ 后是 $f(M-N,N)$ ，故 $f(M,N)=f(M,N-1)+f(M-N,N)$ ；边界为 $M=0$ 或 $N=1$ 时 $f=1$ ， $M<N$ 时 $f(M,N)=f(M,M)$ 。记忆化后只有 $O(MN)$ 个状态，每组询问 $O(1)$ 查表。

参考代码

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-09-30 04:54
# update_at: 2026-09-30 04:54

import sys
from functools import cache


@cache
def ways(m: int, n: int) -> int:
    """把 m 点查克拉分配给 n 个有序影分身（允许为 0）的方案数。

    只看每个分身的点数构成的非递增序列：序列最大值为 0 时全 0 只有一种；
    只用 1 个分身时方案唯一。第一个分身取 0 点 → ways(m, n-1)；
    每个分身都至少 1 点 → 全体减 1，对应 ways(m-n, n)。
    """
    if m == 0 or n == 1:
        return 1
    if m < n:
        return ways(m, m)  # 多出的分身只能拿 0 点，等价于没有它们
    return ways(m, n - 1) + ways(m - n, n)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        m, n = next(data), next(data)
        out.append(str(ways(m, n)))

    print('\n'.join(out))


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
42
43
44/**
 * 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-05 08:33
 * update_at: 2026-10-05 08:34
 */
#include <cstdio>

typedef long long ll;

const int MAXM = 15;
const int MAXN = 15;

ll memo[MAXM][MAXN]; // memo[m][n] = 把 m 点查克拉分给 n 个影分身（允许为 0）的方案数
bool vis[MAXM][MAXN]; // vis[m][n] 标记 memo[m][n] 是否已经求出

// f(m, n)：只看每个分身的点数构成的非递增序列，n=1 或 m=0 时方案唯一。
ll f(ll m, ll n) {
    if (m == 0 || n == 1) {
        return 1;
    }
    if (m < n) {
        return f(m, m); // 多出的分身只能拿 0 点，等价于没有它们
    }
    if (vis[m][n]) {
        return memo[m][n];
    }
    vis[m][n] = true;
    // 末位 a_n 为 0 -> f(m, n-1)；每个分身都至少 1 点 -> 全体减 1 -> f(m-n, n)
    memo[m][n] = f(m, n - 1) + f(m - n, n);
    return memo[m][n];
}

int main() {
    ll t;
    scanf("%lld", &t);
    for (ll i = 1; i <= t; i++) {
        ll m, n;
        scanf("%lld %lld", &m, &n);
        printf("%lld\n", f(m, n));
    }
    return 0;
}

目录

题目描述

思路

参考代码