# Algorithm Notes_Digital DP

### windy number

#### Title:

A positive integer with no leading zeros and two adjacent numbers that differ by at least 2 is called a windy number.

Ask in the interval [ a , b ] [a,b] How many windy numbers are there in [a,b]

#### Parse:

A one-dimensional record of the previous digit of the current state is required.

Note the leading 0 0 0, if the previous bit of the current state is a leading 0 0 When 0, the current bit can be changed from 0 0 0 starts enumeration. When there are leading zeros and the current bit is also 0 0 When 0, the current value can be assigned as − 2 -2 −2 is passed to the next d f s dfs dfs (see the code for details)

#### Code:

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
int dp[20][15];
vector<int> digit;
ll dfs(int pos, int pre, int lead, int limit){
if(pos == -1) return 1;
ll tmp = 0;
int op;
int up = limit?digit[pos]:9;
for(int i = 0; i <= up; i++){
if(abs(i-pre)<2) continue;
op = i;
tmp += dfs(pos-1, op, op==-2,limit&&i==up);
}
return tmp;
}
ll solve(ll num){
memset(dp, -1, sizeof(dp));
digit.clear();
ll res;
while(num){
digit.push_back(num%10);
num /= 10;
}
return dfs(digit.size()-1, -2, 1, 1);
}
int main(){
int a, b;
cin >> a >> b;
cout << solve(b) - solve(a-1);
return 0;
}


### digital counting

#### Title:

statistics [ l , r ] [l,r] How many times each digit appears in [l,r].

#### Parse:

The information to be recorded is: current position, leading 0 0 0, upper bound, digital d d the number of occurrences of d

#### Code:

#include<iostream>
#include<cstring>
using namespace std;
const int N=15;
long long le,ri,dp[N][N],num[N];
int d,cnt;
long long dfs(int pos,long long sum,int d,bool limit,bool lead){
if(pos==0) return sum;
int up=limit? num[pos]:9;
long long tmp=0;
for(int i=0;i<=up;i++){
}
dp[pos][sum]=tmp;
return tmp;
}
long long solve(long long x,int d){
cnt=0;
while(x){
num[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,d,1,1);
}
int main(){
cin>>le>>ri;
for(int i=0;i<=9;i++){
memset(dp,-1,sizeof(dp));
cout<<solve(ri,i)-solve(le-1,i);
if(i!=9) cout<<" ";
}
return 0;
}


### Sam number

#### Title:

A number where the difference between adjacent two digits does not exceed 2 is a Sam number. ask n n The number of n-bit Sam numbers.

#### Parse:

make f ( i , j ) f(i,j) f(i,j) is the last digit j j j's i i The number of i-digit Sam numbers f ( i , j ) = ∑ x = j − 2 j + 2 f ( i − 1 , x ) f(i,j) = \sum\limits_{x=j-2}\limits^{j+2}f(i-1,x) f(i,j)=x=j−2∑j+2​f(i−1,x)
At this point, the time complexity is O ( n ) O(n) O(n), will T
Matrix acceleration is required for recursion. Construct the transition matrix and initial matrix, then matrix fast exponentiation

#### Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 15;
const int mod = 1e9+7;
struct matrix{
ll a[maxn][maxn];
matrix(){
memset(a, 0, sizeof(a));
}
void matrixI(){
for(int i = 0; i < 10; i++)
a[i][i] = 1;
}
matrix operator * (const matrix b){
matrix c;
for(int k = 0; k < 10; k++)
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
c.a[i][j] = (c.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
return c;
}
};
matrix qpow(matrix a, ll b){
matrix res;
res.matrixI();
while(b){
if(b&1)
res = res*a;
b = b >> 1;
a = a*a;
}
return res;
}
matrix a, b;
ll n;
ll ans;
int main(){
cin >> n;
if(n == 1){
cout << 10 << endl;
return 0;
}
for(int i = 1; i < 10; i++)
a.a[0][i] = 1;
for(int i = 0; i < 10; i++){
for(int j = i-2; j <= i+2; j++){
if(j < 0 || j > 9)
continue;
b.a[j][i] = 1;
}
}
a = a*qpow(b, n-1);
for(int i = 0; i < 10; i++)
ans = (ans+a.a[0][i])%mod;
cout << ans << endl;
return 0;
}


### Beautiful numbers

#### Title:

for a number a a a , if a a a can be a a A non-zero number in each digit of a b b b Divisible by b ∣ a b|a b∣a, then a a a is the beautiful number.

ask [ l , r ] [l,r] The number of beautiful numbers in [l,r]

#### Parse:

If every bit is divisible a a a, then the least common multiple of these numbers is also divisible a a a, the least common multiple of 1-9 is 2520, and there is one dimension to record the least common multiple of the current state.

One dimension is also required to record the current state a a a, the concern is a a Whether a can be divided by the current least common multiple l c m lcm lcm is divisible, so just record a % 2520 a\%2520 The value of a%2520.

The status is now d p [ 20 ] [ 2520 ] [ 2520 ] dp[20][2520][2520] dp[20][2520][2520], still can't open. At this time, it is found that the one-dimensional space of the least common multiple is a lot of waste, because the least common multiple will not take all the values ​​​​1-2520, the least common multiple must be a factor of 2520, and the factor of 2520 is only 48, so the space is enough to open 50.

To sum up, d p [ 20 ] [ 2520 ] [ 50 ] dp[20][2520][50] dp[20][2520][50]

#### Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 2520;
ll dp[20][mod+10][50];
int factor[mod+10];
ll gcd(ll a, ll b){
if(b == 0)
return a;
else
return gcd(b, a%b);
}
ll lcm(ll a, ll b){
return a/gcd(a, b)*b;
}
vector<int> L, R;
ll l, r;
ll dfs(vector<int> v, int pos, int x, int lc, int limit){
if(pos == -1)
return x % lc == 0;
if(dp[pos][x][factor[lc]] != -1 && !limit)
return dp[pos][x][factor[lc]];
ll tmp = 0;
int up = limit ? v[pos] : 9;
for(int i = 0; i <= up; i++){
int nx = (x*10+i)%mod;
int nlc = i == 0 ? lc : lcm(lc, i);
tmp += dfs(v, pos-1, nx, nlc, limit && i==up);
}
if(!limit)
dp[pos][x][factor[lc]] = tmp;
return tmp;
}
void solve(){
cin >> l >> r;
l--;
L.clear(); R.clear();
while(l){
L.push_back(l%10);
l /= 10;
}
while(r){
R.push_back(r%10);
r /= 10;
}
cout << dfs(R, R.size()-1, 0, 1, 1) - dfs(L, L.size()-1, 0, 1, 1) << endl;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(dp, -1, sizeof(dp));
int tot = 0;
for(int i = 1; i <= mod; i++){
if(mod%i == 0)
factor[i] = ++tot;
}
int T;
cin >> T;
while(T--)
solve();
return 0;
}


Posted by Simsonite on Tue, 11 Oct 2022 12:32:37 +0300