【数位DP】CF55D Beautiful numbers

矫情吗；* 2023-06-01 06:10 18阅读 0赞

$dp\[x\]\[p\]\[pp\]$表示第x位，当前已有数字mod 2520（1~9数字的lcm）为p，当前各位数字的lcm为pp

观察到数组太大，考虑压缩，第三维lcm最多只有9个数字，打表发现最多只有48个状态，压掉第三维即可

打表用一个状压然后set维护（广搜也可以）即可

*有一个坑点：题目里似乎没有说关于0的事情（即数字里出现0）但是有人在CF上打这个比赛的时候问了出题人，碰到0不要管即可！！！*

打表代码：

1 set<int>s;
     2 inline void Make(int x){
     3     int ans=1;
     4     for(int i=0;i<9;i++){
     5         if(((1<<i)&x)) ans=lcm(ans,i+1);
     6     }s.insert(ans);
     7 }
     8 inline void States_Maker(){
     9     int ans=1;
    10     for(int i=0;i<(1<<9);i++)Make(i);
    11     while(!s.empty()){
    12         cout<<*s.begin()<<",";
    13         s.erase(s.begin());
    14     }    
    15 }

解题代码：

1 #include<bits/stdc++.h>
     2 #define int long long
     3 #define writeln(x)  write(x),puts("")
     4 #define writep(x)   write(x),putchar(' ')
     5 using namespace std;
     6 inline int read(){
     7     int ans=0,f=1;char chr=getchar();
     8     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
     9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    10     return ans*f;
    11 }void write(int x){
    12     if(x<0) putchar('-'),x=-x;
    13     if(x>9) write(x/10);
    14     putchar(x%10+'0');
    15 }const int M = 20,State = 50;
    16 int f[M][2521][State],T,n,a[M],l,r,Pos[2521],S[State]={
        0,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520};
    17 inline int gcd(int x,int y){
        return __gcd(x,y);}
    18 inline int lcm(int x,int y){
        if(x==0)return y;if(y==0)return x;return x*y/gcd(x,y);}
    19 int dfs(int x,int p,int pp,bool lim){
    20     if(!x)return (p%pp==0)?(1):(0);
    21     if(!lim&&p!=-1&&pp!=-1&&f[x][p][Pos[pp]]!=-1)return f[x][p][Pos[pp]];
    22     int ans=0,up=lim?a[x]:9;
    23     for(int i=0;i<=up;i++)ans+=dfs(x-1,(p*10+i)%2520,lcm(pp,i),lim&&a[x]==i);
    24     if(!lim)f[x][p][Pos[pp]]=ans;
    25     return ans;
    26 }
    27 inline int Solve(int x){
    28     int len=0;
    29     while(x)a[++len]=x%10,x/=10;
    30     return dfs(len,0,1,1);
    31 }
    32 signed main(){
    33     memset(f,-1,sizeof(f));
    34     for(int i=1;i<=48;i++)Pos[S[i]]=i;
    35     T=read();
    36     while(T--)l=read(),r=read(),writeln(Solve(r)-Solve(l-1));
    37     return 0;
    38 }

转载于:https://www.cnblogs.com/zhenglw/p/11594843.html