记录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问题的时候会重新整理
✅ 总结
| 方面 | 原代码 | 优化做法 |
|---|---|---|
| 方法 | 暴力 DFS | 动态规划 |
| 时间 | O(6ⁿ) | O(nk) |
| 空间 | O(n)（递归栈） | O(k) |
| 数字存储 | 存完整x（会溢出） | 只存x mod k |
| 适用范围 | n ≤ 6 | n, k ≤ 1000+ |
💡竞赛提示：
凡是涉及“拼数字 + 整除性”的计数问题，优先考虑“模意义下的 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,32P(n,k) = n!/(n−k)!可重复排列（Cartesian Product） 每位独立选择，允许重复 骰子投 2 次 → 11~66 mⁿ（m 为选项数）💡 很多人把第 4 类（如骰子问题）误称为“全排列”，但严格来说它属于“生成所有可能的字符串/序列”，不是排列。
