디지털 dp CodeForces - 55D 아름다운 숫자

Beautiful numbers CodeForces - 55D 
제목: 자신의 모든 자릿수로 나눌 수 있는 숫자를 아름다움으로 정의하고 구간을 정해 구간 내의 아름다운 숫자 개수를 구한다.
분석: 우선, 제한 조건을 이전의 모든 비트의 최대 공배수로 바꿀 수 있다.pos,sum,lcm,up을 dfs의 조건과 dp로 표시하고, 그 다음에 dp[pos]sum[lca]up]은pos 이후의 위치를 모두 훑어본 후에 이 상태는 이sum의 최대치를 취한다.여기서 한 가지 문제를 피해야 한다. 바로 15와 12이다. 15의 dp[pos=1]sum=0[up=1]의 기억에서 12의 dp[pos=1][sum=0]up=1]을 직접 얻으면 안 된다. 그리고 디지털 dp는 이런 기억화로 시간의 복잡도를 줄여야 하기 때문에 이곳의 up은 두 가지 작용을 한다.즉 어떤 위치가 숫자 몇 개를 누비고 15의 dp[1]를 포화(15의 dp[1]과 12의 dp[1]을 피하고 15의 dp[0]를 선택하여 12의 dp[0]를 기억한다)로 정의한다면 기억화할 때 사용하는 것은 dp[0]=10, 즉 up=0의 상위로 완벽하게 해결된다.그리고 이렇게 하면memset을 한 번 사용할 수 있고 다른 것은 모두 기억화할 수 있어 시간의 복잡도를 크게 줄일 수 있다.
그리고 MLE를 발견했다. 그 이유는 수조가 너무 넓어서 1~9의 공배수가 2520이고 [sum]의 최대치는 2520으로 볼 수 있고 큰 것은 샘플링(관련 수론이 있음)으로 할 수 있기 때문에 이것은 2520으로 할 수 있다.그리고 [lca] 위치가 너무 많아서 1~9의 공배수가 몇 개밖에 안 돼요. 그래서 이산화를 해서 해시 그룹을 만들어야 해요. dp라는 그룹을 조작할 때 [lca] 위치의 값을 해시 그룹으로 cnt로 바꾸면 돼요. 이 숫자는 약 50개예요.
Lcm(a,b)=a/gcd(a,b)*b도 볼 수 있습니다.

#include
#include
#include
#include
#include
using namespace std;

typedef long long ll;
const int maxn=32;
const int Mod=2520;
ll n,m;
int dig[maxn];
ll dp[maxn][2550][50][2];
int Hash[2550];

int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int Lcm(int a,int b){
    return a/gcd(a,b)*b;
}

ll dfs(int pos,int sum,int lcm,bool up) {
    // printf("state = %d %d %d %d 
", pos,sum,lcm,up);
    if(pos<0) return sum%lcm==0;
    if(!up&&dp[pos][sum][Hash[lcm]][up]!=-1) {
        printf("dp %d %d %d %d = %d
", pos,sum,lcm,up,dp[pos][sum][Hash[lcm]][up]);
        return dp[pos][sum][Hash[lcm]][up];
    }
    ll res=0;
    for(int i=0; i<=9; i++){
        if(up==1 && i>dig[pos]) break;
        int tlcm=lcm;
        if(i) tlcm=Lcm(tlcm,i);
        res += dfs(pos-1,(sum*10+i)%Mod,tlcm,up&&i==dig[pos]);
        // printf("res=%lld
",res );
    }
    if(!up) dp[pos][sum][Hash[lcm]][up]=res;
    return res;
}

ll sol(ll x){
    if(x<0) return 0;
    // memset(dp,-1,sizeof(dp));
    int cnt=0;
    while(x){
        dig[cnt++]=x%10;
        x/=10;
    }
    return dfs(cnt-1,0,1,1);
}

int main(){
    int T;
    cin>>T;
    int cnt=0;
    for(int i=1; i<=Mod; i++){
        if(Mod%i==0){
            Hash[i]=cnt++;
        }
    }
    // printf("Hash=%d
", Hash[126]);
    memset(dp,-1,sizeof(dp));
    while(T--){
        cin>>n>>m;
        cout<1)<<endl;
    }
}

 
전재 대상:https://www.cnblogs.com/-Zzz-/p/11415938.html