题解 | #函数求值#

数位dp，记忆化搜索

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int mod=20123;
int f[120][120],a[120],cnt;
//pos是从最高位cnt搜索到当前位pos，num是从cnt位到pos-1位过程中1或者2的总数
//mlmit表示是否有限制
int dfs(int pos,int num,bool limit){
	//递归到终点
    if(!pos) return num;
    //之前搜索过
    if(!limit&&f[pos][num]!=-1) return f[pos][num];
    //开始搜索
    int len=limit?a[pos]:9;
    int ans=0;
    for(int i=0;i<=len;++i){
    	//递归向下搜索
        if(i==1||i==2) ans=(ans+dfs(pos-1,num+1,limit&&i==len))%mod;
        else ans=(ans+dfs(pos-1,num,limit&&i==len))%mod;
    }
    //记忆化存储
    if(!limit) f[pos][num]=ans;
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    string s;
    while(cin>>s){
        memset(f,-1,sizeof(f));
        cnt=s.length();
        for(int i=0;i<cnt;++i) a[cnt-i]=s[i]-'0';
        printf("%d\n",dfs(cnt,0,1));
    }
    return 0;
}