Codeforces 55D. Beautiful numbers

正文索引 [隐藏]

题目大意
数位DP
代码

传送门：http://codeforces.com/problemset/problem/55/D

题目大意

问一个区间内，有多少个数字满足它本身能被他每一个非零数位上的数字整除。
题解

数位DP

我们考虑如果判断整除的话，我们要知道前面数字的情况，但是前面的数字非常大不好处理。
再观察，发现1~9中的质因数数量很少，所以我们只需要记录七个质因数（2，2，2，3，3，5，7）的持有情况和前面的数字对他们LCM的余数情况即可处理全部。按位数位DP即可。
然后我TLE了。。。因为多测，所以我们发现很多情况是可以不用每个测试点都算一遍的，于是优化一下，就过了。
P.S. 然后我就发现，我这不是标算，似乎又很快很快的方法欸！

代码

#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int MaxGcd=2520;
int dNum[]={2,2,2,3,3,5,7};
int div[1<<7];
int pSt[10];
LL F[20][MaxGcd+5][1<<7][2];
int timeLine[20][MaxGcd+5][1<<7];
int nowTime;
int num[20];
int tot;
inline int putSt(int preSt,int now){
    if (now<=1) return preSt;
    for (int i=0;i<7;i++){
        if (now%dNum[i]==0){
            preSt|=(1<<i);
            now/=dNum[i];
        }
    }
    return preSt;
}
inline void init(){
    div[0]=1;
    for (int i=0;i<(1<<7);i++){
        for (int j=0;j<7;j++){
            if (i&(1<<j)){
                //Do nothing.
            }else{
                div[i|(1<<j)]=div[i]*dNum[j];
            }
        }
    }
    for (int i=0;i<=9;i++)
        pSt[i]=putSt(0,i);
}
LL DP(int pos,int preSum,int preSt,int flag){
    if (pos==0)
        if (preSum%div[preSt]==0) return 1; else return 0;
    if (flag==false)
        if (F[pos][preSum][preSt][flag]!=0) return F[pos][preSum][preSt][flag];
    else
        if (timeLine[pos][preSum][preSt]==nowTime) return F[pos][preSum][preSt][flag];
    if (flag) timeLine[pos][preSum][preSt]=nowTime;
    LL ret=0;
    int maxNum=flag?num[pos]:9;
    for (int now=0;now<=maxNum;now++){
        int nxtSt=preSt|pSt[now];
        int nxtSum=(preSum*10+now)%MaxGcd;
        ret=ret+DP(pos-1,nxtSum,nxtSt,flag&&(now==num[pos]));
    }
    return F[pos][preSum][preSt][flag]=ret;
}
inline LL calc(long long x){
    tot=0;
    while(x){
        num[++tot]=x%10;
        x=x/10;
    }
    return DP(tot,0,0,1);
}
LL l,r;
inline void solve(int T){
    scanf("%I64d%I64d",&l,&r);
    nowTime=T;
    printf("%I64d\n",calc(r)-calc(l-1));
}
int main(){
    memset(F,0,sizeof(F));
    init();
    int T=0;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve(i);
    return 0;
}

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

const int MaxGcd=2520;

int dNum[]={2,2,2,3,3,5,7};

int div[1<<7];

int pSt[10];

LL F[20][MaxGcd+5][1<<7][2];

int timeLine[20][MaxGcd+5][1<<7];

int nowTime;

int num[20];

int tot;

inline int putSt(int preSt,int now){

if (now<=1) return preSt;

for (int i=0;i<7;i++){

if (now%dNum[i]==0){

preSt|=(1<<i);

now/=dNum[i];

}

return preSt;

}

inline void init(){

div[0]=1;

for (int i=0;i<(1<<7);i++){

for (int j=0;j<7;j++){

if (i&(1<<j)){

//Do nothing.

}else{

div[i|(1<<j)]=div[i]*dNum[j];

}

for (int i=0;i<=9;i++)

pSt[i]=putSt(0,i);

}

LL DP(int pos,int preSum,int preSt,int flag){

if (pos==0)

if (preSum%div[preSt]==0) return 1; else return 0;

if (flag==false)

if (F[pos][preSum][preSt][flag]!=0) return F[pos][preSum][preSt][flag];

else

if (timeLine[pos][preSum][preSt]==nowTime) return F[pos][preSum][preSt][flag];

if (flag) timeLine[pos][preSum][preSt]=nowTime;

LL ret=0;

int maxNum=flag?num[pos]:9;

for (int now=0;now<=maxNum;now++){

int nxtSt=preSt|pSt[now];

int nxtSum=(preSum*10+now)%MaxGcd;

ret=ret+DP(pos-1,nxtSum,nxtSt,flag&&(now==num[pos]));

}

return F[pos][preSum][preSt][flag]=ret;

}

inline LL calc(long long x){

tot=0;

while(x){

num[++tot]=x%10;

x=x/10;

}

return DP(tot,0,0,1);

}

LL l,r;

inline void solve(int T){

scanf("%I64d%I64d",&l,&r);

nowTime=T;

printf("%I64d\n",calc(r)-calc(l-1));

}

int main(){

memset(F,0,sizeof(F));

init();

int T=0;

while(scanf("%d",&T)!=EOF)

for (int i=1;i<=T;i++)

solve(i);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑