hdu 4722 Good Numbers 数位DP

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

数位DP！！！

代码如下：

 #include<iostream>

 #include<stdio.h>

 #include<algorithm>

 #include<iomanip>

 #include<cmath>

 #include<cstring>

 #include<vector>

 #define ll __int64

 #define pi acos(-1.0)

 #define MAX 50000

 using namespace std;

 ll dp[][][];

 int bit[];

 ll dfs(int pos,int mod,int sum,bool f)

 {

     if(pos==-) return mod==;

     if(!f&&dp[pos][mod][sum]!=-) return dp[pos][mod][sum];

     ll ans=;

     int e=f?bit[pos]:;

     for(int i=;i<=e;i++){

         ans+=dfs(pos-,(mod+i)%,sum+i,f&&i==e);

     }

     if(!f) dp[pos][mod][sum]=ans;

     return ans;

 }

 ll solve(ll n)

 {

     int m=;

     while(n){

         bit[m++]=n%;

         n/=;

     }

     return dfs(m-,,,);

 }

 int main(){

     int t,ca=;

     ll a,b;

     memset(dp,-,sizeof(dp));

     scanf("%d",&t);

     while(t--){

         scanf("%I64d%I64d",&a,&b);

         if(a>b) swap(a,b);

         printf("Case #%d: %I64d\n",++ca,solve(b)-solve(a-));

     }

     return ;

 }