user

1
2
3
4
5
6
7
8
关于有少量重复数字的数的研究

有多少个18位数n（不考虑前导零）满足在n中没有一个数字出现超过三次？

我的思路:枚举每个数字的出现次数,直到填满18位.

然后计算组合数:因为不能有前导0,所以要特别判断:如果0不出现没事,如果出现要减掉0开头的数字.
请给我c++代码实现,预处理组合数,使用int128.

gpt

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
你的思路是**完全正确的**：
本质是对「每个数字出现次数 ≤ 3，且总位数 = 18」的**多重集排列计数**，再用**容斥（扣掉前导 0）**即可。

下面我先把数学逻辑简要梳理清楚，然后给你一份**可直接编译运行的 C++（使用 `__int128`，预处理组合数/阶乘）**。

---

## 数学建模（与你思路一致）

设
[
c_0, c_1, \dots, c_9 \in {0,1,2,3}, \quad \sum_{d=0}^9 c_d = 18
]

### 1️⃣ 不考虑前导 0 的排列数

对固定的计数方案 ((c_0,\dots,c_9))，排列数是多项式系数：

[
\text{all} = \frac{18!}{\prod_{d=0}^9 c_d!}
]

### 2️⃣ 扣除前导 0（若 (c_0 \ge 1)）

固定第一位为 0，剩余 17 位排列：

[
\text{bad} = \frac{17!}{(c_0-1)! \prod_{d=1}^9 c_d!}
]

### 3️⃣ 合法数量

[
\text{valid} =
\begin{cases}
\text{all}, & c_0 = 0 \
\text{all} - \text{bad}, & c_0 \ge 1
\end{cases}
]

---

## 实现要点

* 枚举 10 个数字，每个取值 `0..3`
* DFS / 递归枚举，剪枝 `sum > 18`
* 预处理 `0..18` 的阶乘（`__int128`）
* 累加答案

---

## C++ 实现（使用 `__int128`）
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
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128_t;

i128 fact[20];
i128 ans = 0;
int c[10];

// 打印 __int128（调试用，可选）
void print_i128(i128 x) {
    if (x == 0) {
        cout << 0;
        return;
    }
    if (x < 0) {
        cout << '-';
        x = -x;
    }
    string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

void dfs(int d, int sum) {
    if (sum > 18) return;
    if (d == 10) {
        if (sum != 18) return;

        // all = 18! / prod(c[d]!)
        i128 all = fact[18];
        for (int i = 0; i < 10; i++)
            all /= fact[c[i]];

        // subtract leading-zero cases if needed
        if (c[0] > 0) {
            i128 bad = fact[17];
            bad /= fact[c[0] - 1];
            for (int i = 1; i < 10; i++)
                bad /= fact[c[i]];
            all -= bad;
        }

        ans += all;
        return;
    }

    for (int k = 0; k <= 3; k++) {
        c[d] = k;
        dfs(d + 1, sum + k);
    }
}

int main() {
    // factorial
    fact[0] = 1;
    for (int i = 1; i <= 18; i++)
        fact[i] = fact[i - 1] * i;

    dfs(0, 0);

    print_i128(ans);
    cout << "\n";
    return 0;
}
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
---

## 复杂度分析

* 枚举状态数：
  [
  4^{10} = 1,048,576
  ]
* 实际有效状态远少于此（受 `sum=18` 约束）
* 每个状态仅常数运算，**秒级内必跑完**

---

## 拓展（你可能会感兴趣）

* 改成「最多出现 k 次」 → 把 `3` 改成参数
* 改成「恰好有 m 个数字出现 3 次」
* 推广到 n 位数 / b 进制
* 用生成函数
  [
  (1+x+x^2+x^3)^{10}
  ]

如果你愿意，我可以帮你：

* 用 **组合数 DP** 再写一版
* 给出 **数学闭式表达**
* 或验证结果数量级是否合理

你这个问题本身就已经是**竞赛 / 数论研究级别**了 👍