P8825 [传智杯 #3 初赛] 运气

记录75

#include<bits/stdc++.h> using namespace std; const int N=1e9+7; long long n,k,cnt; void dfs(int now,long long x){//搜索实现全排列(重复) if(now==n){ if(x%k==0) cnt++; return; } for(int i=1;i<=6;i++) dfs(now+1,x*10+i); } int main(){ cin>>n>>k; dfs(0,0); cout<<cnt%N; return 0; }

题目传送门https://www.luogu.com.cn/problem/P8825

突破口

你有一枚 6 个面的骰子，分别写了 1,2,3,4,5,6 ，每一面朝上的概率是均等的。

现在哈兰想知道，如果他投掷 n 次，并且将结果按顺序写在纸上成为一个数。（比如说如果哈兰扔了 3 次，分别是 3,2,5 ，那么他最后得到的数就是 325）他现在想知道这个数是 k 的倍数的可能情况有多少种，其中 k 是一个特定的数。

由于这个方案数可能会很大，所以请你输出结果对 109+7 取模的结果。

思路

📌 找到所有数字

• 投掷n次 6 面骰子（1~6）
• 每次结果拼成一个n位数（允许前导零吗？不，因为骰子最小是 1，所以第一位 ≥1）
• 问：这个数是k的倍数的方案数（mod 1e9+7）

✅ 总方案数 = 6ⁿ（n 次独立选择）

代码分析

✅ 代码逐行解释

#include<bits/stdc++.h> using namespace std; const int N = 1e9 + 7; long long n, k, cnt;

• N是模数（通常叫MOD）
• cnt用于计数满足条件的方案数

void dfs(int now, long long x) {

• now：当前已经投了几次（从 0 到 n）
• x：当前拼成的数字（例如投了 3,2 → x=32）

if (now == n) { if (x % k == 0) cnt++; return; }

• 如果投完了n次：
  • 检查x % k == 0
  • 如果是，计数 +1

for (int i = 1; i <= 6; i++) dfs(now + 1, x * 10 + i);

• 枚举下一次骰子结果i ∈ {1,2,3,4,5,6}
• 新数字 =x * 10 + i（十进制拼接）

int main() { cin >> n >> k; dfs(0, 0); cout << cnt % N; return 0; }

• 从“投了 0 次，数字为 0”开始搜索
• 最后输出cnt mod (1e9+7)

🧪 样例验证（n=2, k=11）

DFS 会生成所有两位数：

• 11, 12, 13, ..., 16,
• 21, 22, ..., 66

共 36 个。

其中能被 11 整除的有：11, 22, 33, 44, 55, 66 → 共 6 个 ✅

代码输出6，正确。

⚠️ 注意：这段代码只适用于n<=10的情况（也是看完数据用的这种解法）

❌ 问题 1：时间复杂度过高

• 时间复杂度 =O(6ⁿ)
• 当n = 10→ 6¹⁰ ≈6000 万，勉强可过（C++）
• 当n = 15→ 6¹⁵ ≈4.7 亿，超时
• 当n = 20→ 6²⁰ ≈3.6 万亿，完全不可行

而题目中n可 过（虽然样例小，但正解必须支持大 n）

❌ 问题 2：数字x会溢出

• x是long long，最大约 10¹⁸
• 当n ≥ 19，x就超过long long范围（10¹⁸ < 10¹⁹）
• 导致x变成负数或错误值 →x % k错误

即使k很小（如 k=11），x本身存不下！

❌ 问题 3：没有取模优化

• 题目要求答案 mod 1e9+7，但cnt可能极大（6ⁿ），应边加边取模
• 虽然最后cnt % N，但如果cnt超过long long范围（≈9e18），也会溢出

例如：n=30，6³⁰ ≈ 2e23 > 9e18 →cnt溢出 → 结果错误

✅ 更好的优化：动态规划（DP） + 模运算

关键观察：

我们不需要知道完整的数字x，只需要知道x mod k！

因为：

• (a * 10 + d) mod k = ((a mod k) * 10 + d) mod k

所以可以用 DP：

• dp[i][r]= 投了i次后，当前数字 mod k 等于r的方案数

状态转移：

for each digit d in 1..6: new_r = (r * 10 + d) % k dp[i+1][new_r] += dp[i][r]

初始：dp[0][0] = 1

答案：dp[n][0]

时间复杂度：O(n × k)，空间可优化到 O(k)

对于n ≤ 1000,k ≤ 1000，完全可行

📌 为什么用这种办法？

因为为了讲解搜索实现全排列(重复)，关于动态规划，在DP问题的时候会重新整理

✅ 总结

💡竞赛提示：
凡是涉及“拼数字 + 整除性”的计数问题，优先考虑“模意义下的 DP”，而不是构造完整数字！

🔚 结论

代码逻辑正确但效率极低且存在溢出风险，仅适用于本题这样的极小数据。
在正式比赛中，必须使用基于模运算的动态规划才能通过所有测试点

补充

一、什么是“全排列”？

✅ 标准定义（狭义）

全排列（Permutation）：指将n个互不相同的元素按所有可能的顺序进行排列，总共有n!种。

例如：[1, 2, 3]的全排列有：

123, 132, 213, 231, 312, 321 → 共 3! = 6 种

⚠️ 广义用法（注意！）

在编程中，有时人们会把“所有可能的序列”（包括重复元素、固定长度的笛卡尔积）也笼统称为“全排列”，但这其实是误解。

比如：

• 投骰子n次，每次 1~6 → 共6ⁿ种结果
  → 这叫“可重复的排列”或“笛卡尔积”，不是数学意义上的全排列！

📌关键区别：

• 全排列：元素不重复，长度 = 元素个数，顺序不同即不同
• 可重复枚举（如 DFS 骰子）：允许重复，长度固定，本质是多重循环

---

二、全排列的分类

类型	特点	示例	数量
无重复全排列	所有元素互异	[1,2,3]→ 6 种	n!
有重复全排列	元素可重复	[1,1,2]→ 112,121,211（3种）	n! / (c₁! c₂! ...)
k-排列（Partial Permutation）	从 n 个中选 k 个排列	从[1,2,3]选 2 个 → 12,13,21,23,31,32	P(n,k) = n!/(n−k)!
可重复排列（Cartesian Product）	每位独立选择，允许重复	骰子投 2 次 → 11~66	mⁿ（m 为选项数）

💡 很多人把第 4 类（如骰子问题）误称为“全排列”，但严格来说它属于“生成所有可能的字符串/序列”，不是排列。