小衣同学的博客

枚举这个随便选的临界位i（也就是不卡上界的临界位），也就是[1,i-1]都是卡上界的，本质是想知道已经选了ai个i，还有x个数可以随便选的时候，j是众数的方案数。复杂度大致是O(n*d*d*n*n*d)的，实际也跑不满，跑了600多ms。枚举第i位选了什么，枚举此时对应的众数j，以及枚举j最后选了多少个。枚举第i位选了什么，枚举此时对应的众数j，以及枚举j最后选了多少个。此外，还有一种情况，是前面全选的前导0，从某一位开始才有数的，那么情况类似，枚举有数的第一位i，也就是[1,i-1]都是全0。

赛后发现这个区间即使不等长也是可以merge的，所以就是线段树区间合并类似的操作。赛中想的是，枚举l和r不同的位是哪一位，然后左右分治往上merge答案。这个和代码1的区别就在于是递推的，可以直接对二进制位这些区间做合并。数位dp+分治的一发乱搞，枚举数对(l,r)是在哪一位有的diff。每个2的幂次的长度的区间，对应一个区间的答案，可以直接merge。jiangly、kilo、starsilk代码。记忆化搜索写的数位dp，然后是一个区间合并。

The 2022 CCPC Guangzhou Onsite M. XOR Sum(数位dp 数位背包)

Thue-Morse序列性质 & 带进位的数位dp

AtCoder Regular Contest 133 D.Range XOR(数位dp+分类讨论)

题目给一个正整数n(1<=n<=1e50)，你只能用包含1的数以及加减两种运算去计算这个数，问最少需要多少个1。例如，24=11+11+1+1，最少需要6个1；而102=111-11+1+1，最少需要7个1。思路来源libreOJ群题解注意到111111*6=1111111-111111*4-1且1*6=11-1*5，这表明每一个长度的串1都最多用不会超过6次也就是低位的1不会产生进位，即不会对高位产生影响，前对后有影响，后对前无影响，这启发我们从高到低dp，

题目多组样例，每次给定一个n(1<=n<=1e9)，求[1,n]中，数位表示中包含"13"子串，且数字能被13整除的数的数量题解其实就是 不要62 那道题的思想，感觉一年多终于把其理解透彻了万一哪天忘了呢，总结一下吧，dp[i][j][k]表示当前第i位 状态为j 当前%13余数为k的方案数状态有012三种，分别对应不含13且末尾不是1，不含13且末尾是1，已含13三种状态，再根据最后填什么，判断和13前缀匹配多少，%13=0，加一维余数，用于记忆化代码

题目T(T<=30)组样例，每次给出[x,y](0<=x<=y<=1e18)，求[x,y]中的“平衡的数”的数量“平衡的数”：若存在一个轴，使得左边的数位到这个轴的力*力臂之和=右边的力*力臂之和，则称该数是平衡的，其中力定义为数位的值，力臂定义为到轴的距离，如4139是平衡的，因为其存在轴3，使得4*2+1*1=9*1思路来源https://www.cnblogs.com/bin-gege/p/5696129.html题解考虑枚举轴，轴一旦确定，每一

题目T(T<=1e4)组样例，每次给定[L,R](0<L<=R<2^63 -1)和K(1<=K<=10)，设f(x)为x的十进制表示下数位的最长严格单增子序列(LIS)的长度，如1356的LIS为4求[L,R]区间内满足f(x)=K的x的个数思路来源https://blog.csdn.net/bin_gege/article/details/51836809题解考虑LIS的二分写法，是维护一个数组，每次替换upper_bound的那个数，这

题目给定两个正整数(a,b)的和s(2<=s<=1e12)和异或的值x(0<=x<=1e12)求能组成这样的(a,b)的对数,(b,a)和(a,b)被视为是不同的对数，无解输出0思路来源https://blog.csdn.net/Z_sea/article/details/80709999（为什么进位）https://blog.csdn.net/DTL6...

题目给你N(N<=1e3)个区间，第i个区间[Li,Ri](1<=Li<=Ri<=1e18)依次在第i个区间里等概率地选择一个数，如果选择的数是1开头的，则称为这次是好的选择求好的选择在N次选择中至少占K%(0<=K<=100)的概率题解在数位dp这里还是有很多不足，回头需要再刷如果能求出，对于第i个选择是好的选择的概率one，则...

题目如果一个数能被它的数位和整除，则称这个数是美丽的数给你一个整数n(1<=n<=1e12)，统计[1,n]中有多少个数是美丽的数思路来源https://blog.csdn.net/sunyutian1998/article/details/81433749题解dp的第一维肯定是位数，第二维也肯定是当前的数位和而第三维则是在枚举的数位和的情况下，对应的余数，...

题目给定[l,r]，1<=l<r<=2e9，求[l,r]内的数在二进制表示下，0的数量大于等于1的数量 的数 的个数思路来源https://blog.csdn.net/libin56842/article/details/10037607题解注意还有i个位可以填的时候，已知j个0和k个1对后继没有影响，那就记录下来……这题和前两天做的CF的D题的数...

题目一个美丽的数被定义为可以被它的每一位的数整除的数，给定区间[l,r](1<=l<=r<=9e18)，求该区间内美丽数的个数思路来源https://www.cnblogs.com/kuangbin/archive/2013/05/01/3052670.html题解还是kuangbin爷的代码风格踏实清楚明白……注意到被每个数位都能整除，就相当于被这些...

题目给你一个数n，问[1,n]包括49的数有多少个，n<(1<<63)思路来源https://blog.csdn.net/u012860063/article/details/46820639https://www.2cto.com/kf/201409/338701.html题解这题分前面出现49和后面出现49讨论……都在代码的注释里了……dp[i...