CF D. Beautiful numbers （数位dp） - c++编程基础

TOP

CF D. Beautiful numbers （数位dp）

2015-07-20 17:48:02 来源: 作者: 【大中小】浏览:13次

Beautiful Numbers : 这个数能整除它的所有位上非零整数。问[l,r]之间的Beautiful Numbers的个数。

若一个数能整除它的所有的非零数位，那么相当于它能整除个位数的最小公倍数。因此记忆化搜索中的参数除了len(当前位)和up（是否达到上界），有一个prelcm表示前面的数的最小公倍数，判断这个数是否是Beautiful Numbers，还要有一个参数表示前面数，但是这个数太大，需要缩小它的范围。

难点：

缩小前面组成的数的范围。

可以发现所有个位数的最小公倍数是2520，假设当前的Beautiful Numbers是x，

那么 x % lcm{dig[i]} = 0,

又 2520%lcm{dig[i]} = 0，

那么x%2520%lcm{ dig[i] } = 0，x范围由9*10^18变为2520。

处理超内存问题。

经过分析后可以设出dp[20][2050][2050]，dp[i][j][k]表示处理到i位，前面的数的最小公倍数为j，前面的数%2520为k。但这样

明显会TLE。。因为1~9组成的最小公倍数只有48个，可以离散化，这样数组就降到了dp[20][50][2520]。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#define LL __int64 #define LL long long #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; const int max_lcm = 2520; LL gcd(LL a, LL b) { if(b == 0) return a; return gcd(b,a%b); } LL lcm(LL a, LL b) { return a/gcd(a,b)*b; } int dig[25]; LL dp[25][50][2525]; int hash[2525]; LL dfs(int len, int prelcm, int prenum, int up) { if(len == 0) { return prenum%prelcm == 0; } if(!up && dp[len][hash[prelcm]][prenum] != -1) return dp[len][hash[prelcm]][prenum]; int n = up ? dig[len] : 9; LL res = 0; for(int i = 0; i <= n; i++) { int nownum = (prenum*10+i)%max_lcm; int nowlcm = prelcm; if(i) nowlcm = lcm(prelcm,i); res += dfs(len-1,nowlcm,nownum,up&&i==n); } if(!up) dp[len][hash[prelcm]][prenum] = res; return res; } LL cal(LL num) { int len = 0; while(num) { dig[++len] = num%10; num /= 10; } return dfs(len,1,0,1); } int main() { int test; LL a,b; int cnt = 0; for(int i = 1; i <= 2520; i++) //离散化 { if(max_lcm % i == 0) hash[i] = ++cnt; } scanf(%d,&test); memset(dp,-1,sizeof(dp)); for(int item = 1; item <= test; item++) { scanf(%I64d %I64d,&a,&b); printf(%I64d ,cal(b) - cal(a-1)); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Leetcode 动态规划 Trapping Rain..	下一篇：uva 11732 - strcmp() Anyone?(字..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: