BZOJ1183 Croatian2008 Umnozak

Description

定义一个数的digit-product是它的各个位上的数字的乘积,定义一个数的self-product是它本身乘以它的digit-pr
oduct。编程求self-product在a和b之间的数的个数。

Input

两个整数a,b(1 ≤ a ≤ b < 10^18)。

Output

一个整数，self-product在a和b之间的数的个数。

Sample Input

145 192

Sample Output

数位DP，我么发现digit-product包含的质因子最多只有2，3，5，7，digit-product严格小于原数，所以digit-product不会超过1e9，所以我们可以对这个数进行枚举，只有很少的可能取值

然后我们确定了digit-product之后就可以确定原数的上下界，然后利用digit-product中，2，3，5，7的质因子个数来进行DP，注意一下边界问题什么的

。。。

反正我照标程调的

#include<bits/stdc++.h>

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||b<l_line)return 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\n",ans);

    return 0;

}

标程：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

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\n", rjesenje );

   return 0;

}