魔法數字[數位DP][狀态壓縮]

題目描述 

在數論領域中， 人們研究的基礎莫過于數字的整除關系。 一般情況下， 我 

們說整除總在兩個數字間進行，例如 a | b（a 能整除 b） 表示 b 除以 a 的餘數為 

0。 

我們稱一個數字 X 是魔法的，當且僅當 X 是整數，且它能被 K 及 K 以上 

種一位數整除， 要求這若幹種一位數均在 X 的十進制表示中出現。 

給出整數 K、 L、 R，請你計算出在區間[L, R]中，有多少個魔法數字。

輸入格式 

一行三個整數 K、 L、 R。

輸出格式 

輸出一行一個整數， 表示該區間内魔法數字的個數。

樣例資料 

magic.in 

2 1 20 

magic.out 

2

分析

數位dp...然後...寫不來

讓我們來想一想要那些狀态

第一維  第幾位

怎麼知道前面出現了那些數字呢（因為要算整除的個數）

第二維  狀壓，出現則為1

好，怎麼知道能不能整除呢

我們發現

本題的p就是2520

隻要知道除以2520的餘數，除以其它的都知道

優化等會兒說吧

第三維  除以2520的餘數

好像所有數位都還有一維----是否放滿

10123

最高位區0（沒有放滿）  就還可以取9999

放滿了  低位最高就是0..1..2..3

于是dp四步走

1.定狀态 

f[pos][state][mod][limit]   ,  即f[18][512][252][2]  (252是優化，等會兒講)

2.考慮邊界 

pos=n+1時，如果出現了那個數且整除mod，cnt++，cnt>=k就傳回1

3.轉移  數位dp 記憶化搜尋 最好寫

枚舉下一位，如果limit=1，枚舉答案的最高位數，否則為9

f[i][j][k][l]+=f[i+1][j|(1<<x-1)][k*10+x][l&(x==a[i])];

4.答案

f[1][0][0][true] -> 到第一位，前面什麼都沒有，而且都放滿了

一些細節

1.考慮到limit，必須從高位開始，是以要這樣存

exampal   R=10234 len=5,a[1]=1,a[2]=0,a[3]=2,a[4]=3,a[5]=4;

2.狀壓一定從0開始，不知道省多少空間

3.優化：5可以看尾數，8可以看上一位的4

什麼意思呢，上一位到第一位組成的數字除4餘3，除8可能是3或7

這一位時乘了10，除8隻可能餘6

于是2520可以變252，但要判斷後再模

//狀壓+數位dp 
//f為第i位 除252餘j 出現數的狀态為j 是否沾滿
//最終答案 f[1][0][0][1];
//exampal R=10234 len=5,a[1]=1,a[2]=0,a[3]=2,a[4]=3,a[5]=4;
//轉移 遞歸記憶化搜尋  f[i][j][k][l]+=f[i+1][j*10+x][k|(1<<x-1)][l&(x==a[i])];
//1<<0=1,即第0位是1
//邊界f[len+1][mod][state][l],if(state&(1<<(x-1)&&mod%x==0) 為1,否則為0//出現且整除 
#include<bits/stdc++.h>
using namespace std;
long long f[20][252][512][2],ans;
int k,len,a[20],pd; 
int read(){
    int cnt=0;char ch=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
    return cnt;
}
long long init()
{
    char ch[20];scanf("%s",ch+1);
    len=strlen(ch+1);
    memset(a,0,sizeof(a));
    memset(f,-1,sizeof(f));
    for(int i=len;i>=1;i--)
        a[i]=ch[i]-'0';
    if(pd==0){pd=1;if(a[len]) a[len]--;else a[len-1]--,a[len]=9;}//l-1
}
long long dfs(int pos,int mod,int state,bool lim){
    if(pos==len+1){
        int cnt=0;
        if(state&1) cnt++;
        if(state&(1<<1)&&mod%2==0) cnt++;
        if(state&(1<<2)&&mod%3==0) cnt++;
        if(state&(1<<3)&&mod%4==0) cnt++;
        if(state&(1<<4)&&mod%5==0) cnt++;
        if(state&(1<<5)&&mod%6==0) cnt++;
        if(state&(1<<6)&&mod%7==0) cnt++;
        if(state&(1<<7)&&mod%8==0) cnt++;
        if(state&(1<<8)&&mod%9==0) cnt++;
        if(cnt>=k) return 1;
        return 0;
    }
    mod%=252;
    if(f[pos][mod][state][lim]!=-1) return f[pos][mod][state][lim];
    long long cur=0;
    int x=lim?a[pos]:9;
    for(int i=0;i<=x;i++)
        cur+=dfs(pos+1,mod*10+i,i?(state|(1<<(i-1))):state,lim&(i==x));
    f[pos][mod][state][lim]=cur; 
    return cur;
} 
int main()
{
    k=read();
    init(),ans-=dfs(1,0,0,true);
    init(),ans+=dfs(1,0,0,true);
    printf("%d",ans);
    return 0;
}      

int dfs(int now,bool is6,bool ismax)
{
  if(now==0) return 1;
  if(!ismax&& dp[now][is6]>=0) return dp[now][is6];
  int ways=0,limit=(ismax?bit[now]:9);//為true則為bit[now] 否則為9 
  for(int i=0;i<=limit;i++){
    if(i==4||is6&&i==2) continue;
    ways+=dfs(now-1,i==6,ismax&&i==limit);
  }
        f[now][is6][ismax]=ways;
  return ways;
}