算法竞赛备赛进阶之数位DP训练

数位DP的思想就是对每一位进行DP，计算时记忆化每一位可以有的状态，其作用是减少运算时间，避免重复计算。

数位DP是一种计数用的DP，一般就是要统计一个区间[A,B]内满足一些条件数的个数。

以1e9甚至1e18、1e100的问题为例，因为在统计情况下有很多重复的计算，数位DP实现了相同状态只计算一次，从而大幅减少运算时间。

数位DP：

技巧1：[X, Y] => f(Y) - f(X-1)

技巧2：用树进行排列

1.度的数量

1081

求给定区间[X, Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。

例如。设X=15，Y=20，K=2，B=2，择优且仅有下列三个数满足题意：

17 = 24 + 20

18 = 24 + 21

20 = 24 + 22

输入格式

第一行包含两个整数X和Y，接下来两行包含整数K和B

#include<iostream>
#include<algorithm>
#include<vector>
?
using namespace std;
?
const int N = 35;
?
int K, B;
int f[N][N];
?
void init()
{
 ? ?for(int i = 0;i < N; i++)
 ? ? ? ?for(int j = 0;j <= N; j++)
 ? ? ? ? ? ?if(!j) f[i][j] = 1;
 ?          else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
?
int dp(int n)
{
 ? ?if(!n) return 0;
 ? ?
 ? ?vector<int> nums;
 ? ?while(n)
 ?  {
 ? ? ? ?nums.push_back(n % B);
 ? ? ? ?n /= B;
 ?  }
 ? ?
 ? ?int res = 0;
 ? ?int last = 0;
 ? ?
 ? ?for(int i = nums.size() - 1;i >= 0; i--)
 ?  {
 ? ? ? ?int x = nums[i];
 ? ? ? ?if(x)//求左边的分支
 ? ? ?  {
 ? ? ? ? ? ?res += f[i][K - last];
 ? ? ? ? ? ?if(x > 1)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?if(K - last - 1 >= 0) res += f[i][K - last - 1];
 ? ? ? ? ? ? ? ?break;
 ? ? ? ? ?  }
 ? ? ? ? ? ?else 
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?last++;
 ? ? ? ? ? ? ? ?if(last > K) break;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?if(!i && last == K) res++; // 最右侧分支上的方案
 ?  }
 ? ?
 ? ?return res;
}
?
int main()
{
 ? ?init();
 ? ?
 ? ?int l, r;
 ? ?cin >> l >> r >> K >> B;
 ? ?
 ? ?cout << dp(r) - dp(r - 1) << endl;
 ? ?return 0;
}

2.数字游戏

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈现非下降关系，如123，446

现在大家决定玩一个游戏，指定一个整数闭区间[a, b]，问这个区间内有多少个不降数。

动态规划

1. 状态表示

   1. 集合：所有最高位是j，且一共有i位的不降数的集合

   2. 属性：数量

2. 状态计算

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
?
using namespace std;
?
const int N = 40;
?
int f[N][N]; // f[i][j]表示一共有i位，且最高位填j的数的个数
?
void init()
{
 ? ?for(int i = 0;i <= 9; i++) f[1][i] = 1;
 ? ?
 ? ?for(int i = 2;i < N; i++)
 ? ? ? ?for(int j = 0;j <= 9; j++)
 ? ? ? ? ? ?for(int k = j;k <= 9; k++)
 ? ? ? ? ? ? ? ?f[i][j] += f[i - 1][k];
}
?
int dp(int n)
{
 ? ?if(!n) return 1;
 ? ?
 ? ?vector<int> nums;
 ? ?while(n)
 ?  {
 ? ?    nums.push_back(n % 10);
 ? ? ? ?n /= 10;
 ?  }
 ? ?
 ? ?int res = 0;
 ? ?int last = 0;
 ? ?for(int i = nums.size() - 1;i >= 0; i--)
 ?  {
 ? ? ? ?int x = nums[i];
 ? ? ? ?for(int j = last;j < x; j++)
 ? ? ? ? ? ?res += f[i + 1][j];
 ? ? ? ?
 ? ? ? ?if(last > x)
 ? ? ? ? ? ?break;
 ? ? ? ?last = x;
 ? ? ? ?
 ? ? ? ?if(!i) res++;
 ?  }
 ? ?
 ? ?return res;
}
?
int main()
{
 ? ?void init();
 ? ?
 ? ?int l, r;
 ? ?while(scanf("%d%d", &l, &r))
 ?  {
 ? ? ? ?cout << dp[r] - dp[l - 1] << endl;
 ?  }
 ? ?
 ? ?return 0;
}

3.Windy数

1083.Windy定义了一种Windy数：不包含前导零且相邻两个数字之差至少为2的正整数被称为Windy数。

Windy想知道，在A和B之间，包括A和B，总共有多少个Windy数？

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
?
using namespace std;
?
const int N = 11;
?
int f[N][10];
?
void init()
{
 ? ?for(int i = 0;i <= 9; i++) f[1][i] = 1;
 ? ?
 ? ?for(int i = 2;i < N; i++)
 ? ? ? ?for(int j = 0;j <= 9; j++)
 ? ? ? ? ? ?for(int k = 0;k <= 9; k++)
 ? ? ? ? ? ? ? ?if(abs(j - k) >= 2)
 ? ? ? ? ? ? ? ? ? ?f[i][j] += f[i - 1][k];
}
?
int dp(int n)
{
 ? ?if(!n) return 0;
 ? ?
 ? ?vector<int> nums;
 ? ?while(n) nums.push_back(n % 10), n /= 10;
 ? ?
 ? ?int res = 0;
 ? ?int last = -2;
 ? ?for(int i = nums.size() - 1;i >= 0; i--)
 ?  {
 ? ? ? ?int x = nums[i];
 ? ? ? ?for(int j = 0;j < x; j++)
 ? ? ? ? ? ?if(abs(j - last) >= 2)
 ? ? ? ? ? ? ? ?res += f[i + 1][j];
 ? ? ? ?
 ? ? ? ?if(abs(x - last) >= 2) last = x;
 ? ? ? ?else break;
 ? ? ? ?
 ? ? ? ?if(!i) res++;
 ?  }
 ? ?
 ? ?// 特殊枚举有前导零
 ? ?for(int i = 1;i < nums.size(); i++)
 ? ? ? ?for(int j = 1;j <= 9;+)
 ? ? ? ? ? ?res += f[i][j];
 ? ?
 ? ?return res;
}
?
int main()
{
 ? ?init();
 ? ?
 ? ?int l, r;
 ? ?cin >> l >> r;
 ? ?
 ? ?cout << dp(r) - dp(l - 1) << endl;
 ? ?
 ? ?return 0;
}

4.数字游戏II

1084.由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和mod N 为0

现在大家又要玩游戏了，指定一个整数闭区间[a, b]，问这个区间内有多少个取模数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
?
using namespace std;
?
const int N = 11, M = 110;
?
int P;
int f[N][10][M];
?
int mod(int x, int y)
{
 ? ?return (x % y + y) % y;
}
?
void init()
{
 ? ?memset(f, 0, sizeof(f));
 ? ?
 ? ?for(int i = 0;i <= 9; i++) f[1][i][i % P]++;
 ? ?
 ? ?for(int i = 2;i < N; i++)
 ? ? ? ?for(int j = 0;j <= 9; j++)
 ? ? ? ? ? ?for(int k = 0;k < N; k++)
 ? ? ? ? ? ? ? ?for(int x = 0;x <= 9; x++)
 ? ? ? ? ? ? ? ? ? ?f[i][j][k] += f[i - 1][x][mod(k - j, P)];
}
?
int dp(int n)
{
 ? ?if(!n) return 1;
 ? ?
 ? ?vector<int> nums;
 ? ?while(n) nums.push_back(n % 10), n /= 10;
 ? ?
 ? ?int res = 0;
 ? ?int last = 0;
 ? ?for(int i = nums.size() - 1;i >= 0; i--)
 ?  {
 ? ? ? ?int x = nums[i];
 ? ? ? ?for(int j = 0;j < x; j++)
 ? ? ? ? ? ?res += f[i + 1][j][mod(-last, P)];
 ? ? ? ?
 ? ? ? ?last += x;
 ? ? ? ?
 ? ? ? ?if(!i && last % P == 0) res++;
 ?  }
 ? ?
 ? ?return res;
}
?
int main()
{
 ? ?int l, r;
 ? ?while(cin >> l >> r >> P)
 ?  {
 ? ? ? ?init();
 ? ? ? ?
 ? ? ? ?cout << dp[r] - dp[l - 1] << endl;
 ?  }
 ? ?
 ? ?return 0;
}

5.不要62

1085.杭州人称那些傻乎乎黏兮兮的人为62。

杭州交通管理局经常会扩充一些的士车牌照。附近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有4或62的号码。如：62315，73418，88914都属于不吉利号码。但是，61152虽然含有6和2，但不是逐号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照号区号[n, m]，推断出交管局今后又要实际上给多少辆的士车上牌照了。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
?
using namespace std;
?
const int N = 9;
?
int f[N][10];
?
void init()
{
 ? ?for(int i = 0;i <= 9; i++)
 ?      if(i != 4)
 ? ? ? ? ? ?f[1][i] = 1;
 ? ?
 ? ?for(int i = 2;i < N; i++)
 ? ? ? ?for(int j = 0;j <= 9; j++)
 ? ? ?  {
 ? ? ? ? ? ?if(j == 4) continue;
 ? ? ? ? ? ?for(int k = 0;k <= 9; k++)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?if(k == 4 || j == 6 && k == 2)
 ? ? ? ? ? ? ? ? ? ?continue;
 ? ? ? ? ? ? ? ?f[i][j] += f[i - 1][k];
 ? ? ? ? ?  }
 ? ? ?  }
}
?
int dp(int n)
{
 ? ?if(!n) return 1;
 ? ?
 ? ?vector<int> nums;
 ? ?while(n) nums.push_back(n % 10), n /= 10;
 ? ?
 ? ?int res = 0;
 ? ?int last = 0;
 ? ?for(int i = nums.size() - 1;i >= 0; i--)
 ?  {
 ? ? ? ?int x = nums[i];
 ? ? ? ?for(int j = 0;j < x; j++)
 ? ? ?  {
 ? ? ? ? ? ?if(j == 4 || last == 6 && j == 2) continue;
 ? ? ? ? ? ?res += f[i + 1][j];
 ? ? ?  }
 ? ? ? ?
 ? ? ? ?if(x == 4 || last == 6 && x == 2) break;
 ? ? ? ?last = x;
 ? ? ? ?
 ? ? ? ?if(!i) res++;
 ?  }
 ? ?
 ? ?return res;
}
?
int main()
{
 ? ?init();
 ? ?
 ? ?int l, r;
 ? ?while(cin >> l >> r, l || r)
 ?  {
 ? ? ? ?cout << dp[r] - dp[l - 1] << endl;
 ?  }
 ? ?
 ? ?return 0;
}

6.恨7不成妻

1086.DS级码农吉哥依然单身！ 所以，他生平最恨情人节，不管是214还是77，他都讨厌！

吉哥观察了214和77这两个数，发现： 　　2+1+4=7 　　7+7=72 　　77=711 最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！

什么样的数和7有关呢？

如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；

现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
?
using namespace std;
?
typedef long long LL;
?
const int N = 20, P = 1e9 + 7;
?
struct F
{
 ? ?int s0, s1, s2;
}f[N][10][7][7];
?
int power7[N], power9[N];
?
int mod(LL x, int y)
{
 ? ?return (x % y + y) % y;
}
?
void init()
{
 ? ?for(int i = 0;i <= 9; i++)
 ?  {
 ? ? ? ?if(i == 7) continue;
 ? ? ? ?auto &v = f[1][i][i % 7][i % 7];
 ? ? ? ?v.s0++;
 ? ? ? ?v.s1 += i;
 ? ? ? ?v.s2 += i * i;
 ?  }
 ? ?
 ? ?LL power = 10;
 ? ?for(int i = 2;i < N; i++, power *= 10)
 ? ? ? ?for(int j = 0;j < N; j++)
 ? ? ?  {
 ? ? ? ? ? ?if(j == 7) continue;
 ? ? ? ? ? ?for(int a = 0;a < 7; a++)
 ? ? ? ? ? ? ? ?for(int b = 0;b < 7; b++)
 ? ? ? ? ? ? ?      for(int k = 0;k <= 9; k++)
 ? ? ? ? ? ? ? ? ?  {
 ? ? ? ? ? ? ? ? ? ? ? ?if(k == 7) continue;
 ? ? ? ? ? ? ? ? ? ? ? ?auto &v1 = f[i][j][a][b], &v2 = f[i - 1][k][mod(a - j * (power % 7), 7)][mod(b - j, 7)];
 ? ? ? ? ? ? ? ? ? ? ? ?v1.s0 = (v1.s0 + v2.s0) % P;
 ? ? ? ? ? ? ? ? ? ? ? ?v1.s1 = (v1.s1 + j * (power % P) * v2.s0 + v2.s1) % P; 
 ? ? ? ? ? ? ? ? ? ? ? ?v1.s2 = (v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0) % P + 2 * j * (power % P) % P * v2.s1 % P + v2.s2) % P;
 ? ? ? ? ? ? ? ? ?  }
 ? ? ?  }
 ? ?
 ? ?power7[0] = power9[0] = 1;
 ? ?for(int i = 1;i < N; i++)
 ?  {
 ? ? ? ?power7[i] = power7[i - 1] * 10 % 7;
 ? ? ? ?power9[i] = power9[i - 1] * 10 % P;
 ?  }
}
?
F get(int i, int j, int a, int b)
{
 ? ?int s0 = 0, s1 = 0, s2 = 0;
 ? ?for(int x = 0;x < 7; x++)
 ? ? ? ?for(int y = 0;y < 7; y++)
 ? ? ?  {
 ? ? ? ? ? ?if(x == a || y == b) continue;
 ? ? ? ? ? ?auto v = f[i][j][x][y];
 ? ? ? ? ? ?s0 = (s0 + v.s0) % P;
 ? ? ? ? ? ?s1 = (s1 + v.s1) % P;
 ? ? ? ? ? ?s2 = (s2 + v.s2) % P;
 ? ? ?  }
 ? ?return {s0, s1, s2};
}
?
int dp(LL n)
{
 ? ?if(!n) return 0;
 ? ?
 ? ?LL backup_n = n % P;
 ? ?vector<int> nums;
 ? ?while(n) nums.push_back(n % 10), n /= 10;
 ? ?
 ? ?int res = 0;
 ? ?LL last_a = 0, last_b = 0;
 ? ?for(int i = nums.size() - 1;i >= 0; i--)
 ?  {
 ? ? ? ?int x = nums[i];
 ? ? ? ?for(int j = 0;j < x; j++)
 ? ? ?  {
 ? ? ? ? ? ?if(j == 7) continue;
 ? ? ? ? ? ?int a = mod(-last_a % 7 * power7[i + 1], 7);
 ? ? ? ? ? ?int b = mod(-last_b, 7);
 ? ? ? ? ? ?
 ? ? ? ? ? ?auto v = get(i + 1, j, a, b);
 ? ? ? ? ? ?res = (res + (last_a % P) * (last_a * P) % P * power9[i + 1] % P * power9[i + 1] % P * v.s0 % P + 2 (last_a % P) % P * power9[i + 1] % P * v.s1 % P + v.s2) % P;
 ? ? ?  }
 ? ? ? ?
 ? ? ? ?if( x == 7) break;
 ? ? ? ?last_a = last_a * 10 + x;
 ? ? ? ?last_b += x;
 ? ? ? ?
 ? ? ? ?if(!i && last_a % 7 && last_b % 7) res += (res + backup_n * backup_n) % P;
 ?  }
 ? ?
 ? ?return res;
}
?
int main()
{
 ? ?init();
 ? ?
 ? ?int T;
 ? ?cin >> T;
 ? ?while(T--)
 ?  {
 ? ? ? ?int l, r;
 ? ? ? ?cin >> l >> r;
 ? ? ? ?cout << mod(dp(r) - dp(l - 1), P) << endl;
 ?  }
 ? ?
 ? ?return 0;
}