本文主要是介绍【数位dp】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 那个lower_bound 必须都是单调的
2. 数组越界
3. memset(dp,-1,sizeof(dp));写在外面
4. 4 * 2/ 2 *2 可以直接约掉
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <string>
#include <queue>
#include <bitset>
using namespace std;#define MOD 2520
typedef long long ll;
ll T;
ll lcmcnt;
ll dp[20][2600][60];
ll has[2600];
ll bits[20];
ll gcd(ll a, ll b)
{return b == 0 ? a : gcd(b,a%b);
}
ll f(ll a,ll b)
{return a / gcd(a,b) * b;
}
ll dfs(ll len,ll premod,ll prelcm,bool flag)
{if(len <= 0) return premod%prelcm == 0;if(!flag && dp[len][premod][has[prelcm]]!=-1) return dp[len][premod][has[prelcm]];ll e = flag ? bits[len] : 9;ll ans = 0;for(ll i=0;i<=e;i++){ll newmod = (premod * 10 + i) % MOD;ll newlcm = prelcm;if(i)newlcm = f(prelcm,i);ans += dfs(len-1,newmod,newlcm,flag && i == e);}return flag ? ans : dp[len][premod][has[prelcm]] = ans;
}
ll solve(ll x)
{ll tt = x;ll cnt = 0;while(tt > 0){bits[++cnt] = tt % 10;tt /= 10;}return dfs(cnt,0,1,true);
}
int main()
{lcmcnt = 0;for(ll i=1;i<=MOD;i++){if(2520 % i == 0) has[i] = ++lcmcnt;}scanf("%I64d",&T);memset(dp,-1,sizeof(dp));for(ll i=0;i<T;i++){ll l,r;scanf("%I64d%I64d",&l,&r);printf("%I64d\n",solve(r)-solve(l-1));}return 0;
}/*
4578 cf55d
*/这篇关于【数位dp】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
