usaco-1.3.4 牛式

题目描述

乘法竖式中，把 * 换成给定数字集合（数字 ∈ 1…9）里的数字且首位不为 0，使式子成立者称为牛式：三位被乘数 × 两位乘数，两条部分积各三位，最终积四位。输入第一行是数字个数 $N$ （ $N\le 9$ ），第二行是 $N$ 个数字；输出一行，表示牛式总数。样例输入 5 / 2 3 4 6 8，输出 1。

思路

枚举由给定数字拼成的三位被乘数 $a$ 与两位乘数 $b$ （可重复取数）。只需校验它们算出的三条乘积： $a(b \bmod 10)$ 与 $a\lfloor b/10\rfloor$ 各为三位、 $ab$ 为四位，且乘积的每一位数字都属于给定集合。位数与数字集合两项缺一不可。

参考代码

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
41
42
43
44#!/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:55
# update_at: 2026-10-04 11:29

import sys
from itertools import product


def is_cow_number(value: int, length: int, allowed: set[int]) -> bool:
    """value 的十进制写法恰好 length 位，且每一位数字都来自 allowed 集合。"""
    text = str(value)
    return len(text) == length and allowed.issuperset(map(int, text))


def build_numbers(digits: list[int], length: int) -> list[int]:
    """用给定数字（允许重复）拼出全部 length 位数；数字集不含 0，故首位必非 0。"""
    return [int(''.join(map(str, combo))) for combo in product(digits, repeat=length)]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    count = next(data)  # 第 1 行：数字的个数
    digits = [next(data) for _ in range(count)]
    allowed = set(digits)

    three_digit = build_numbers(digits, 3)              # 被乘数 a 的全部候选
    two_digit = build_numbers(digits, 2)                # 乘数 b 的全部候选

    # 竖式里由 a、b 算出的 3 个结果都要位数正确、数字合法：部分积各 3 位，最终积 4 位
    answer = sum(
        is_cow_number(a * b, 4, allowed)
        and is_cow_number(a * (b % 10), 3, allowed)      # b 的个位乘 a
        and is_cow_number(a * (b // 10), 3, allowed)     # b 的十位乘 a
        for a in three_digit
        for b in two_digit
    )
    print(answer)


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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * 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 09:25
 * update_at: 2026-10-06 09:25
 */
#include <iostream>
using namespace std;

typedef long long ll;

int n;
int digit[15];   // 输入的数字集合，允许重复使用
bool in_set[15]; // in_set[d] 表示数字 d 是否在给定集合中，用来校验乘积的每一位
ll answer;

// 判断 value 的十进制写法是否恰好 length 位，且每一位数字都在给定集合中
bool valid(ll value, int length) {
    int cnt = 0;
    while (value > 0) {
        int d = value % 10;
        if (!in_set[d]) {
            return false;
        }
        value /= 10;
        cnt++;
    }
    return cnt == length;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> digit[i];
        in_set[digit[i]] = true;
    }

    // 枚举三位被乘数 a
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                int a = digit[i] * 100 + digit[j] * 10 + digit[k];
                // 枚举两位乘数 b
                for (int p = 1; p <= n; p++) {
                    for (int q = 1; q <= n; q++) {
                        int b = digit[p] * 10 + digit[q];
                        // 两条部分积各 3 位，最终积 4 位，且三个乘积每位数字都合法
                        if (valid(a * (b % 10), 3) && valid(a * (b / 10), 3) && valid(a * b, 4)) {
                            answer++;
                        }
                    }
                }
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

目录

题目描述

思路

参考代码