디지털 DP 퀴즈 요약
HDU 4507
제목: 조건에 부합되지 않는 숫자의 제곱과
사고방식:DP[pos][num][val]은 제pos위까지 하고 각 숫자와%7=num, 전체 숫자%7=val의 합법적인 숫자 제곱은 얼마인지를 나타낸다.
#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
#define ll long long
const int N=3e5+5;
const int mod = 1e9+7;
struct node{
ll cnt,sum,sqr;
node(ll cnt=-1,ll sum=0,ll sqr=0):cnt(cnt),sum(sum),sqr(sqr){}
}dp[30][7][7];
ll fac[30];
int a[30];
int T;
ll l,r;
ll rd()
{
ll x=0,f=1;char ch=getchar();
while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int sum(int a, int b) {
int s = (a + b);
if (s >= mod) s -= mod;
return s;
}
int sub(int a, int b) {
int s = a - b;
if (s < 0) s += mod;
return s;
}
int mult(int a, int b) {
return (1LL * a * b) % mod;
}
void doit()
{
fac[0]=1;
rep(i,1,20) fac[i]=mult(fac[i-1],10);
rep(i,0,20)
rep(j,0,6)
rep(k,0,6)
{
dp[i][j][k].cnt=-1;
dp[i][j][k].sum=dp[i][j][k].sqr=0;
}
}
ll dfs(int pos,int num,int val,ll &cnt,ll &summ,bool limit)
{
if(pos==-1)
{
if(num==0 || val==0) return 0;
cnt=1;
return 0;
}
if(!limit && dp[pos][num][val].cnt!=-1)
{
cnt=dp[pos][num][val].cnt;
summ=dp[pos][num][val].sum;
return dp[pos][num][val].sqr;
}
int up=limit?a[pos]:9;
ll sq=0;
rep(i,0,up)
if(i!=7)
{
ll cn=0,su=0;
ll x=dfs(pos-1,(num+i)%7,(val*10+i)%7,cn,su,limit &&i==a[pos]);
int mi=mult(i,fac[pos]),xy=mult(2,mult( fac[pos],mult( i,su )));
//printf("%d %d %d %d %d
",mi,xy,pos,i,fac[1]);
sq=sum( sq,sum( x,sum( mult( cn,mult(mi,mi) ),xy ) ) );
cnt=sum(cnt,cn);
summ=sum(summ,sum( su,mult(mi,cn) ) );
//printf("sq=%lld cnt=%lld summ=%lld
",sq,cnt,summ);
}
if(!limit) dp[pos][num][val]={cnt,summ,sq};
return sq;
}
int solve(ll x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
//printf(" :%d
",pos);
ll t1=0,t2=0;
return dfs(pos-1,0,0,t1,t2,true)%mod;
}
int main()
{
doit();
T=rd();
while(T--)
{
l=rd();r=rd();
printf("%lld
",sub(solve(r),solve(l-1)));
}
}
HDU 6659
부분 제목: f(d,k)는 1-k 사이의 모든 숫자에 d가 나타난 개수가 얼마인지 나타낸다
아이디어: 직접 디지털 DP
#include
#include
#include
#include
using namespace std;
typedef long long ll;
struct node{
long long a;long long b;
};
int x=6;
ll a[20];
ll dp[20][2];
ll num[20][2];
node dfs(int pos,int pre,bool limit)
{
//printf("%d %d pre=%d
",pos,limit,pre);
if(pos==-1) return {0,1};
if(!limit && num[pos][pre]!=-1)
{
return {dp[pos][pre],num[pos][pre]};
}
int up=limit ? a[pos] : 9;
ll tmp=0,tmp1=0;
for(int i=0;i<=up;i++)
{
node ans=dfs(pos-1,i==x,limit && i==a[pos]);
tmp+=ans.a;
if(i==x) tmp+=ans.b;
tmp1+=ans.b;
}
if(!limit)
{
dp[pos][pre]=tmp;
num[pos][pre]=tmp1;
}
return {tmp,tmp1};
}
ll solve(ll x)
{
int pos=0;
//printf("%lld
",x);
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,0,true).a;
}
int main()
{
ll le,ri;
while(~scanf("%lld",&ri))
{
memset(num,-1,sizeof(num));
printf("%lld
",solve(ri));
}
return 0;
}
/*
1000000000000
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.