记录75#includebits/stdc.h using namespace std; const int N1e97; long long n,k,cnt; void dfs(int now,long long x){//搜索实现全排列(重复) if(nown){ if(x%k0) cnt; return; } for(int i1;i6;i) dfs(now1,x*10i); } int main(){ cinnk; dfs(0,0); coutcnt%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 是一个特定的数。由于这个方案数可能会很大所以请你输出结果对 1097 取模的结果。思路 找到所有数字投掷n次 6 面骰子1~6每次结果拼成一个n位数允许前导零吗不因为骰子最小是 1所以第一位 ≥1问这个数是k的倍数的方案数mod 1e97✅ 总方案数 6ⁿn 次独立选择代码分析✅ 代码逐行解释#includebits/stdc.h using namespace std; const int N 1e9 7; long long n, k, cnt;N是模数通常叫MODcnt用于计数满足条件的方案数void dfs(int now, long long x) {now当前已经投了几次从 0 到 nx当前拼成的数字例如投了 3,2 → x32if (now n) { if (x % k 0) cnt; return; }如果投完了n次检查x % k 0如果是计数 1for (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 (1e97) 样例验证n2, k11DFS 会生成所有两位数11, 12, 13, ..., 16,21, 22, ..., 66共 36 个。其中能被 11 整除的有11, 22, 33, 44, 55, 66 → 共 6 个 ✅代码输出6正确。⚠️ 注意这段代码只适用于n10的情况也是看完数据用的这种解法❌ 问题 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 ≥ 19x就超过long long范围10¹⁸ 10¹⁹导致x变成负数或错误值 →x % k错误即使k很小如 k11x本身存不下❌ 问题 3没有取模优化题目要求答案 mod 1e97但cnt可能极大6ⁿ应边加边取模虽然最后cnt % N但如果cnt超过long long范围≈9e18也会溢出例如n306³⁰ ≈ 2e23 9e18 →cnt溢出 → 结果错误✅ 更好的优化动态规划DP 模运算关键观察我们不需要知道完整的数字x只需要知道x mod k因为(a * 10 d) mod k ((a mod k) * 10 d) mod k所以可以用 DPdp[i][r] 投了i次后当前数字 mod k 等于r的方案数状态转移for each digit d in 1..6: new_r (r * 10 d) % k dp[i1][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 ≤ 6n, 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,2113种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~66mⁿm 为选项数 很多人把第 4 类如骰子问题误称为“全排列”但严格来说它属于“生成所有可能的字符串/序列”不是排列。