URAL1057. Amount of Degrees(DP)

简单的数位DP 刚开始全以2进制来算的后来发现要找最接近x,y值的那个基于b进制的0,1组合
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<cmath>
  7 using namespace std;
  8 #define LL __int64
  9 #define INF 1e11
 10 LL dp[35][25],pp[12][22];
 11 int g1,g2,p[1<<21];
 12 void init()
 13 {
 14     int i,j;
 15     for(i = 3 ; i <= 10 ; i++)
 16     {
 17         pp[i][0] = 1;
 18         for(j = 1 ; j <= 20 ; j++)
 19         {
 20             pp[i][j] = pp[i][j-1]*i;
 21             if(pp[i][j]>INF)
 22             break;
 23         }
 24     }
 25     dp[0][0] = 1;
 26     dp[1][1] = 1;
 27     dp[1][0] = 1;
 28     for(i = 2; i <= 32 ; i++)
 29     {
 30         dp[i][0] = 1;
 31         for(j =1; j <= 20 ; j++)
 32         dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
 33     }
 34 }
 35 void change(int x,int y,int b,int c1[],int c2[])
 36 {
 37     int di[35],g=0,i;
 38     while(x)
 39     {
 40         di[++g] = x%b;
 41         x/=b;
 42     }
 43     for(i = g ; i >= 1;i--)
 44     c1[i] = di[i];
 45     g1 = g;
 46     g = 0;
 47     while(y)
 48     {
 49         di[++g] = y%b;
 50         y/=b;
 51     }
 52     for(i = g ; i >= 1;i--)
 53     c2[i] = di[i];
 54     g2 = g;
 55 }
 56 LL find(int c[],int k,int len)
 57 {
 58     int i,j,o=0;
 59     LL sum=0;
 60     for(i = len ; i >= 1 ; i--)
 61     {
 62         if(c[i]==0) continue;
 63         if(k>=o)
 64         sum+=dp[i-1][k-o];
 65         o++;
 66     }
 67     if(o==k)
 68     sum++;
 69     return sum;
 70 }
 71 int main()
 72 {
 73     int x,y,k,b,j,i;
 74     int c1[35],c2[35];
 75     init();
 76     scanf("%d%d%d%d",&x,&y,&k,&b);
 77     if(b!=2)
 78     {
 79         LL s=0,x1=-1,x2=-1;
 80         x--;
 81         for(i = 0 ; i <= (1<<20) ; i++)
 82         {
 83             s =0 ;
 84             for(j = 0 ; j <= 20 ; j++)
 85             if(i&(1<<j))
 86             {
 87                 s+=pp[b][j];
 88             }
 89             if(x1==-1&&s>x)
 90             x1 = i-1;
 91             if(s>y)
 92             {
 93                 x2 = i-1;
 94                 break;
 95             }
 96         }
 97         for(j = 20 ; j >=0 ; j--)
 98         if(x1&(1<<j))
 99         {
100             c1[j+1] = 1;
101             if(!g1)
102             g1 = j+1;
103         }
104         else
105         c1[j+1] = 0;
106         for(j = 20 ; j >=0 ; j--)
107         if(x2&(1<<j))
108         {
109             c2[j+1] = 1;
110             if(!g2)
111             g2 = j+1;
112         }
113         else
114         c2[j+1] = 0;
115     }
116     else
117     change(x-1,y,b,c1,c2);
118     LL s1 = find(c1,k,g1);
119     LL s2 = find(c2,k,g2);
120     printf("%I64d
",s2-s1);
121     return 0;
122 }
View Code