BZOJ 1183 Croatian 2008 Umnozak【デジタルDP】*

BZOJ1183 Croatian2008 Umnozak
Description
1つの数を定義するdigit-productは、その各ビット上の数値の積であり、1つの数を定義するself-productは、それ自体にそれを乗じたdigit-pr oductである.プログラミングはself-productのaとbの間の数の個数を求めます.
Input
2つの整数a,b(1≦a≦b<10^18).
Output
1つの整数、self-productのaとbの間の数の個数.
Sample Input
145 192
Sample Output
4
デジタルDP、私はdigit-productが含む質因子が最大で2,3,5,7しかないことを発見しました.digit-productは原数より厳格に小さいので、digit-productは1 e 9を超えません.だから、私たちはこの数を列挙することができます.わずかな可能性しかありません.
そしてdigit-productを決定してから原数の上下境界を決定し,digit-productでは2,3,5,7の質量因子個数を用いてDPを行い,境界問題に注意する
...
どうせ私はスケジュール通りに調整した.

#include
using namespace std;
typedef long long LL;
LL l,r,ans=0;
LL dp[18][30][19][13][11];
LL f[4]={2,3,5,7};
LL k[4]={0,0,0,0};
LL cnt[10][4]={
   {0,0,0,0},
   {0,0,0,0},
   {1,0,0,0},
   {0,1,0,0},
   {2,0,0,0},
   {0,0,1,0},
   {1,1,0,0},
   {0,0,0,1},
   {3,0,0,0},
   {0,2,0,0}
};
LL dfs(LL len,LL a,LL pot,LL l_line,LL r_line){
    LL b=a+pot-1;
    if(a>r_line||breturn 0;
    if(len==18)return (!k[0])&&(!k[1])&&(!k[2])&&(!k[3]);
    bool mem=(a>=l_line&&b<=r_line);
    if(mem&&dp[len][k[0]][k[1]][k[2]][k[3]]>=0)
        return dp[len][k[0]][k[1]][k[2]][k[3]];
    pot/=10;
    LL res=0;
    for(LL i=(a!=0);i<=9;++i){
        LL t=1;
        for(LL j=0;j<4;j++)if(cnt[i][j]>k[j])t=0;
        if(!t)continue;
        for(LL j=0;j<4;j++)k[j]-=cnt[i][j];
        res+=dfs(len+1,a+i*pot,pot,l_line,r_line);
        for(LL j=0;j<4;j++)k[j]+=cnt[i][j];
    }
    if(mem)dp[len][k[0]][k[1]][k[2]][k[3]]=res;
    return res;
}
LL getL(LL a,LL b){return (a+b-1)/b;}
LL getR(LL a,LL b){return a/b;}
void getans(LL up,LL prod,LL tip){
    if(prod>(LL)1e9||prod*prod>up)return;
    if(tip==4){
        ans+=dfs(0,0,(LL)1e18,getL(l,prod),getR(r,prod));
        return;
    }
    getans(up,prod,tip+1);
    ++k[tip];
    getans(up,prod*f[tip],tip);
    --k[tip];
}
int main(){
    cin>>l>>r;
    memset(dp,-1,sizeof(dp));
    getans(r,1,0);
    printf("%lld
",ans);
    return 0;
}

スレッド:

#include 
#include 
#include 
#include 

using namespace std;

typedef long long llint;

llint memo[18][30][19][13][11];

int f[4] = { 2, 3, 5, 7 };
int k[4] = { 0, 0, 0, 0 };
int code[10][4] = {
   { 0, 0, 0, 0 },
   { 0, 0, 0, 0 },
   { 1, 0, 0, 0 },
   { 0, 1, 0, 0 },
   { 2, 0, 0, 0 },
   { 0, 0, 1, 0 },
   { 1, 1, 0, 0 },
   { 0, 0, 0, 1 },
   { 3, 0, 0, 0 },
   { 0, 2, 0, 0 }
};

llint rec( int digits, llint a, llint pot, llint lo, llint hi ) {   
   llint b = a + pot-1;
   if( a > hi || b < lo ) return 0;
   if( digits == 18 ) return !k[0] && !k[1] && !k[2] && !k[3];   

   int memoize = 0;
   if( a >= lo && b <= hi ) memoize = 1;

   if( memoize && memo[digits][k[0]][k[1]][k[2]][k[3]] >= 0 )
      return memo[digits][k[0]][k[1]][k[2]][k[3]];

   pot /= 10;

   llint ret = 0;

   for( int digit = (a!=0); digit <= 9; ++digit ) {

      int ok = 1;
      for( int i = 0; i < 4; ++i ) ok &= code[digit][i] <= k[i];
      if( !ok ) continue;

      for( int i = 0; i < 4; ++i ) k[i] -= code[digit][i];
      ret += rec( digits+1, a + digit*pot, pot, lo, hi );
      for( int i = 0; i < 4; ++i ) k[i] += code[digit][i];
   }

   if( memoize ) memo[digits][k[0]][k[1]][k[2]][k[3]] = ret;

   return ret;
}

llint lo, hi;
llint rjesenje;

llint ceil( llint a, llint b ) { return (a+b-1)/b; }
llint floor( llint a, llint b ) { return a/b; }

void gen( llint limit, llint product, int factor ) {
   if( product > 1000000000 || product*product > limit ) return;
   if( factor == 4 ) {
      rjesenje += rec( 0, 0, 1000000000000000000LL, ceil(lo,product), floor(hi,product) );
      return;
   }

   gen( limit, product, factor + 1 );
   ++k[factor];
   gen( limit, product*f[factor], factor );
   --k[factor];
}

int main( void ) {
   scanf( "%lld%lld", &lo, &hi );

   memset( memo, -1, sizeof memo );

   gen( hi, 1, 0 );

   printf( "%lld
", rjesenje );

   return 0;
}