「动态规划」第3章数位DP

B数计数

题意

求\(1\to n\)中有几个数满足\(13 \mid i 且包含子串\)13。

分析

我们考虑\(计数dp\)。设\(dp[pos][mod][k]\)表示\(pos\)位余数为\(mod\)出现\(13\)的状态为\(k\)。

\(k=0\)表示当前位不为\(1\)现在想找\(1\)。

\(k=1\)表示没有出现\(13\)但是当前位置为\(1\)。

\(k=2\)表示有\(13\)出现。

实现

如果当前没有限制并且当前\(f[pos][mod][k]\)被查找过，那么直接返回\(f[pos][mod][k]\)。

\(dfs需要四个参数dfs(当前位数,余数,当前状态,限制)\)。

如果当前递归到第\(0\)位，直接返回\(op==2\&\& mod==0\)。

当前如果没有限制那么从\(9\)开始枚举，否则从\(limit\)开始枚举。

\(ans+=dfs(pos-1,((mod*10)+i)\%13,check(k,i),limit\&\&i==s)\)。

如果当前没有限制那么直接\(f[pos][res][op]=ans\)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int n;
int c[N];
int f[N][N][N];
const int mod=13;
int check(int v13,int val){
    if(v13==0){
        if(val==1) return 1;
        return 0;
    }
    else if(v13==1){
        if(val==1) return 1;
        if(val==3) return 2;
        return 0;
    }
    else return 2;
}
int dfs(int pos,int res,int op,int limit){
    if(!limit&&f[pos][res][op]>=0) return f[pos][res][op];
    if(pos==0) return op==2&&res==0;
    int s=0,ans=0,rest;
    if(!limit) s=9;
    else s=c[pos];
    for(int i=0;i<=s;i++){
        ans+=dfs(pos-1,(res*10+i)%mod,check(op,i),limit&&i==s);
    }
    if(!limit) f[pos][res][op]=ans;
    return ans;
}
int solve(int n){
    int cnt=1,x=n;
    while(x>0){
        c[cnt++]=x%10;
        x/=10;
    }
    return dfs(cnt-1,0,0,1);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(f,-1,sizeof f);
        printf("%d\n",solve(n));
    }
}