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;
	if(!limit&&!lead&&dp[pos][pre]!=-1) return dp[pos][pre];
	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;
		if(!i&&lead) op = -2;
		tmp += dfs(pos-1, op, op==-2,limit&&i==up);
	}
	if(!limit&&!lead) dp[pos][pre] = tmp;
	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;
	if(!limit&&!lead&&dp[pos][sum]!=-1) return dp[pos][sum];
	int up=limit? num[pos]:9;
	long long tmp=0;
	for(int i=0;i<=up;i++){
		tmp+=dfs(pos-1,sum+((i==d)&&(!lead||i)),d,limit&&i==num[pos],i==0&&lead);
	}
	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;
}