数位DP选讲 dzy493941464

祝pascal选手早日转C++。 C++： || pascal：or C++：&& pascal：and C++：== pascal：= C++：% pascal：mod

Codeforces 55D. Beautiful Numbers 定义一个数是美丽的，当且仅当它能整除自身的每个非零数位。 例如250是美丽的，2333就是不美丽的。 询问[L,R]中有多少个数是美丽的。 1≤L≤R≤9×1018

Solution 考虑到1~9的LCM只是2520，所以一个数的所有非零数位的LCM一定是2520的因数。 我们设当前状态为f[dep][lcm][mo]。 表示当前转移到了第dep位，当前所有非零数位的LCM为lcm，当前这个数%2520 = mo。 枚举当前位k。 那些状态可以转移到当前状态呢？ f[dep-1][LCM(lcm,k)][(mo*10+k)%2520] 因为2520的因数只有48个，所以把lcm这维优化成48这样空间就够了。

Codeforces 258B. Little Elephant and Elections 定义幸运数字是4,7，一个数字的幸运度为它数位上幸运数字的个数。 给你n个数：1,2,3,...,n。你要从中选7个数，使得第1个数的幸运度大于后6个数的幸运度之和。 求方案数。N<=10^9

Solution 先用数位dp预处理出幸运度为0~9的数的个数。 然后dfs后六个数的幸运度即可。 f[dep][num] 枚举当前数位k f[dep-1][num+(k==4 || k==7)] 然后dfs后六个数的幸运度即可。

HDU3709 Balanced Number 定义一个数是平衡的，当且仅当把它看成一个杠杆，存在一个支点使它平衡。 例如4139。当3作为支点时，左边的力矩是4×2+1×1=9，右边的力矩是9×1=9。所以这个杠杆是平衡的，4139是平衡数。 询问[L,R]中有多少个平衡数。 0≤L≤R≤1018

Solution 枚举支点为ctr。 设当前状态为f[dep][ctr][sum]。 表示当前支点在ctr，力矩和是sum。（ctr左边的力矩算正，右边的算负，这样如果最后sum=0则平衡）。 力矩和最大值大概最大为(9+8+..+2+1)*9大概500左右。 枚举这位的数为k。 从哪些状态转移呢？ f[dep-1][ctr][sum+k*(dep-ctr)]。

SPOJ BALNUM 又是平衡数~ 定义一个数是平衡的，当且仅当，在这个数中的出现的每个奇数都出现了偶数次，出现的每个偶数都出现了奇数次。 比如233是平衡的，2333就不平衡了，23333又平衡了。 询问[L,R]中有多少个平衡数。 1≤L≤R≤1018

Solution 我们考虑0~9，每个数只有三种状态：没用，合法，不合法。 我们用3进制表示状态。0没用，1合法，2不合法。 状态为f[dep][status] 枚举当前数位k。 从哪转移？ f[dep-1][trans(status,k)]

BZOJ1799 [AHOI2012] 同类分布 询问[L,R]中各位数字之和能整除原数的个数。 1≤L≤R≤1018

Solution 直接的想法就是枚举数位和sum（最大是18*9=162），然后直接数位dp。 定义状态为f[dep][sum][cur][mo] 枚举当前位是k 从哪转移？ f[dep-1][sum][cur+k][(mo*10+k)%sum] 可惜这样会MLE，于是我们可以把sum这维优化掉放在外面即可。

HDU4507 吉哥系列故事——恨7不成妻 如果一个整数符合下面3个条件之一，那么我们说这个整数和7有关： 整数中某一位是7 整数的每一位加起来的和是7的整数倍 这个整数是7的整数倍 询问[L,R]中与7无关的数字的平方和，模109+7. 1≤L≤R≤1018

Solution 我们可以先算出与7有关的数的平方和，再用总和去减。 f[dep][a][b][c]表示到第dep位，a表示是否有7出现，b表示数位和%7，c表示当前数%7。 每一个状态我们得维护三个值： cnt 和7有关的数的个数 sum 和7有关的数的和 sqr 和7有关的数的平方和

Solution 设当前是第len位为k，dfs回溯上来的数为x，令d=k×10len-1，那么这个数就是d+x。 它的平方对答案的贡献是(d+x)2=d2+2dx+x2当前状态为f，从g转移过来。 f.cnt += g.cnt f.sum += g.sum + d×g.cnt f.sqr += d×d×g.cnt + 2×d×g.sum + g.sqr 小心爆long long

Codechef FAVNUM 吉丽有N个喜欢的数字ai。 定义一个数字是吉利的，当且仅当这个数中包含至少一个吉丽喜欢的数字。 比如吉丽喜欢250和233，那2333就是吉利的，1250也是吉丽的。 吉丽想知道在[L,R]中第K小的吉利数是多少。 1≤L≤R≤1018，1≤ai≤1018，1≤K≤R-L+1，N≤62

Solution 考虑建出N个数字串的AC自动机。 f[dep][flag][status] 枚举当前数为k status表示当前走到了AC自动机里的哪个节点。 枚举当前数为k f[dep-1][flag||trans(status,k).flag][trans(status,k)] 二分答案，计算小于它的吉利数有几个

谢谢大家D我