题目就是kuangbin的数位DP。
先讲C题，不要62，差不多就是一个模板题。要注意的是按位来的话，光一个pos是不够的，还需要一维来记录当前位置是什么数字，这样才能防止同一个pos不同数字的dp值混在一起。直接丢代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef long long ll;10 11 // pos , 记录当前位是什么12 // 第二维是为了防止同一个pos的不同which的dp混淆在一起，因为是记忆化搜索的13 int bit[12],dp[12][12];14 15 int dfs(int pos,int which,bool have_six,bool flag)16 {17 if(pos == -1) return 1;18 int& ans = dp[pos][which];19 if(flag && ans!=-1) return ans;20 int d = flag?9:bit[pos];21 22 int ret = 0;23 for(int i=0;i<=d;i++)24 {25 if(i==4) continue;26 if(have_six && i==2) continue;27 ret += dfs(pos-1,i,i==6,flag||i
那么如果是求区间内还有62的呢？可以是在上面的基础上，用总个数减去；也可以再开一维have，表示是否拥有了62。这样变化一下就是D题了，丢代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef long long ll;10 11 12 int bit[22];13 ll dp[22][2][2];14 15 /*ll dfs(int pos,bool state,bool flag)16 {17 if(pos == -1) return 1;18 ll& ans = dp[pos][state];19 if(flag && ans!=-1) return ans;20 int d = flag?9:bit[pos];21 22 ll ret = 0;23 for(int i=0;i<=d;i++)24 {25 if(state && i==9) continue;26 ret += dfs(pos-1,i==4,flag||i
另外还需要注意的是上面的问题并不需要记录当前一位是哪个数字，只要记录是不是需要的数字即可。比方说62，我只要用一个state保存这一位是不是6即可。
以上就是数位dp的基本套路，但是还会遇到一种情况，比方说让你统计区间内数的二进制表示的0的个数，这样子在dfs时需要再加一个参数first来表示有没有前导0。举个例子，比如说10010，在dfs以后，如果变成了0XXXX的情况，显然第一个0是不能算在0的个数之内的。因此，如果数位dp的过程中，有无前导0会对结果造成影响的，就要再加一个参数first来辅助完成dp过程。具体见E题代码：
1 #include2 #include 3 #include 4 using namespace std; 5 6 int bit[40]; 7 int dp[40][40][40]; 8 //int len; 9 10 /*11 单纯的用len来记录总位数是不行的，因为比方说5是101，12 比它小的数可能len不等于313 也就是说在递推的过程中len是会发生变化的14 15 因此，换一个方法，用一个bool变量first记录之前位是否存在16 */17 18 int dfs(int pos,int num_zero,int num_one,bool flag,bool first)19 {20 if(pos == -1) return num_zero >= num_one;21 int& ans = dp[pos][num_zero][num_one];22 if(flag && ans!=-1) return ans;23 24 int d = flag?1:bit[pos];25 int ret = 0;26 for(int i=0;i<=d;i++)27 {28 ret += dfs(pos-1,(first||i?num_zero+(i==0):0),(first||i?num_one+(i==1):0),flag||i
然后几题是比较有意思的。
A题，问区间内的美丽数的个数，美丽数指的是：这个数能被各个位置上的数字整除。这题的方法是直接找他们的最小公倍数，然后当做状态的状态的一维即可。要注意的是如果最小公倍数开最大的话，会超内存，那么只要将这一系列的最小公倍数离散化即可。其实这题似乎还可以优化，我没有深究了。具体见代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef long long ll;10 11 int gcd(int a,int b) { return a%b?gcd(b,a%b):b;}12 int lcm(int a,int b) { return a*b/gcd(a,b);}13 // pos,离散化后的公约数的位置,各个位置上数字的和14 int a[2520+10];15 int bit[22];16 ll dp[22][50][2520+100];17 18 ll dfs(int pos,int _lcm,int sum,bool flag)19 {20 if(pos == -1) return (ll)(sum%_lcm==0);21 ll& ans = dp[pos][a[_lcm]][sum];22 if(flag && ans!=-1) return ans;23 int d = flag?9:bit[pos];24 25 ll ret = 0;26 for(int i=0;i<=d;i++)27 {28 ret += dfs(pos-1,i?lcm(_lcm,i):_lcm,(sum*10+i)%2520,flag||i
B题，问区间内满足以下条件的数，这个数字内的LIS等于K。那么只要模拟LIS用二进制储存一个状态码当做一维的内容即可。具体见代码：
1 #include2 #include 3 #include 4 #include 5 #include
讲到状态码形式的数位dp，可以再看看最后一题。大意是找出区间内平衡数：任何奇数只要出现了，就必须出现偶数次；任何偶数，只要出现了就必须出现奇数次。不出现的数字不做讨论，同时是任意一个奇数都要出现偶数次，比方说1333，1和3它们都出现了奇数次，而不是所有奇数出现的次数和是偶数次，因此这个数字不满足平衡数的要求。具体实现的话也是转化成3进制的状态码即可，具体见代码：
1 #include2 #include 3 #include 4 #include 5 #include
最后想讲的是J题，求的是区间内的与7无关的数字的平方和。因为涉及到平方，所以涉及到展开的问题。具体见代码注释：
1 #include2 #include 3 #include 4 #include 5 #include
最后想补充的一点是，很多的solve求的都是0~指定位置满足条件的和，但是没有关系，只要相减以后就都抵消了，但是单单使用solve的话就可能会出现问题。