「一本通 6.6 练习 9」网格

题目描述

从 $(0,0)$ 走到 $(n,m)$ ，只能向右或向上，且途经点满足 $x \ge y$ 。求方案总数。 $1 \le m \le n \le 5000$ ，精确输出。输入：一行两个整数 $n,m$ 。
输出：一个整数，表示方案数。
样例：输入 6 6，输出 132。

思路

反射法：总路径 $\binom{n+m}{m}$ 减去首次越过 $y=x+1$ 的坏路径 $\binom{n+m}{m-1}$ ，答案为两者之差。用质因数分解实现大整数精确计算。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10"""ROJ 1660 网格：不越过对角线的路径计数（卡特兰数推广，精确大整数）。"""
import sys
from math import comb

def main() -> None:
    n, m = map(int, sys.stdin.read().split())
    # 反射法：全部路径 C(n+m, m) 减去接触直线 y = x+1 的坏路径 C(n+m, m-1)
    print(comb(n + m, m) - comb(n + m, m - 1))

main()

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131/**
 * 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:38
 * update_at: 2026-10-06 01:38
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Big {
    static const ll BASE = 10000;
    vector<ll> d; // 低位在前，每元素 0~BASE-1

    Big(ll x = 0) {
        if (x == 0) d.push_back(0);
        else {
            while (x) {
                d.push_back(x % BASE);
                x /= BASE;
            }
        }
    }

    // 大整数乘以一个小整数（x <= 10000，结果仍精确）
    void mul(ll x) {
        ll carry = 0;
        for (size_t i = 0; i < d.size(); ++i) {
            ll cur = d[i] * x + carry;
            d[i] = cur % BASE;
            carry = cur / BASE;
        }
        while (carry) {
            d.push_back(carry % BASE);
            carry /= BASE;
        }
        trim();
    }

    // 大整数减法：保证 *this >= b
    void sub(const Big& b) {
        ll borrow = 0;
        for (size_t i = 0; i < b.d.size(); ++i) {
            ll cur = d[i] - b.d[i] - borrow;
            if (cur < 0) {
                cur += BASE;
                borrow = 1;
            } else {
                borrow = 0;
            }
            d[i] = cur;
        }
        for (size_t i = b.d.size(); i < d.size() && borrow; ++i) {
            ll cur = d[i] - borrow;
            if (cur < 0) {
                cur += BASE;
                borrow = 1;
            } else {
                borrow = 0;
            }
            d[i] = cur;
        }
        trim();
    }

    void trim() {
        while (d.size() > 1 && d.back() == 0) d.pop_back();
    }

    void print() const {
        printf("%lld", d.back());
        for (int i = (int)d.size() - 2; i >= 0; --i) {
            printf("%04lld", d[i]);
        }
        printf("\n");
    }
};

const int MAXV = 10005;

int primes[MAXV];
int pcnt;
bool vis[MAXV];

// 线性筛，筛出 [2, n] 的所有质数
void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) primes[++pcnt] = i;
        for (int j = 1; j <= pcnt && i <= n / primes[j]; ++j) {
            vis[i * primes[j]] = 1;
            if (i % primes[j] == 0) break;
        }
    }
}

// n! 中质数 p 的指数
int count_p(int n, int p) {
    int cnt = 0;
    while (n) {
        n /= p;
        cnt += n;
    }
    return cnt;
}

// 计算 C(N, K)，通过质因数分解后累乘
Big comb(int N, int K) {
    Big res(1);
    for (int i = 1; i <= pcnt && primes[i] <= N; ++i) {
        int p = primes[i];
        int e = count_p(N, p) - count_p(K, p) - count_p(N - K, p);
        for (int j = 0; j < e; ++j) res.mul(p);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    sieve(n + m);
    Big ans = comb(n + m, m);
    Big bad = comb(n + m, m - 1);
    ans.sub(bad);
    ans.print();
    return 0;
}

「一本通 6.6 练习 9」网格

目录

题目描述

思路

参考代码