CF 55D 아름 다운 숫자(디지털 DP)
1456 단어 디지털 dp
1-9 의 최소 공 배 수 는 2520 이 고 한 수 는 이 숫자 로 2520 의 나머지 를 대체 할 수 있 습 니 다.그러면 할 수 있 습 니 다.또한 디지털 dp 가 대표 하 는 것 에 대해 모호 하 게 느 꼈 지만 문 제 를 풀 고 나 서 디지털 dp 를 하 는 방법 을 알 게 된 것 같 습 니 다.먼저 dfs 폭력 알고리즘 을 작성 한 다음 에 두 개의 dfs 에 대해 매개 변수 가 같 으 면 그들 이 달 린 결과 도 같다 는 것 을 알 게 되 었 습 니 다.그러면 저 는 dp[매개 변수 1][매개 변수 2].......................................................................................이렇게 하면 쉽게 알 수 있다.
#include
using namespace std;
typedef long long LL;
int a[30],tol,id[3000],cnt;
LL dp[30][3000][50];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int Lcm(int a,int b){return a/gcd(a,b)*b;}
LL dfs(int cur,int mod,int lcm,int limit)
{
if(!cur)return mod%lcm==0;
if(!limit&&dp[cur][mod][id[lcm]])return dp[cur][mod][id[lcm]];
int up=limit?a[cur]:9;
LL ans=0;
for(int i=0;i<=up;i++)
ans+=dfs(cur-1,(mod*10+i)%2520,Lcm(lcm,i==0?1:i),limit&&a[cur]==i);
if(!limit)dp[cur][mod][id[lcm]]=ans;
return ans;
}
LL solve(LL x)
{
tol=0;
while(x)
{
a[++tol]=x%10;
x/=10;
}
return dfs(tol,0,1,1);
}
int main()
{
int T;
LL l,r;
for(int i=1;i<=2520;i++)
{
if(2520%i==0)id[i]=++cnt;
}
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d",&l,&r);
printf("%I64d
",solve(r)-solve(l-1));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Gym 100623J Just To Lucky(디지털 dp)제목: 1-n 중 몇 개의 숫자가 그 자체를 만족시키고 각 수위에 의해 정제될 수 있는지; 사고방식: n은 10의 12차원이다. 곧 디지털 dp라고 생각할 수 있다. 그때는 판자가 없어서 디지털 dp를 어떻게 두드렸...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
