题解 | #函数求值#

#include <bits/stdc++.h>
#include <string>
using namespace std;

int main() {
   string s;
   while(cin >> s){

        int m = s.length(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        function<int(int,int,bool)> f = [&](int i,int cnt2,bool ok)-> int {
             if (i == m) return cnt2%20123;
             if (!ok && dp[i][cnt2] >= 0) return dp[i][cnt2];
            int res = 0;
            for (int d = 0, up = ok ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
                {
                    res += f(i + 1, cnt2 + (d == 2 ||d == 1), ok && d == up);
                    res%=20123;
                }
            if (!ok) dp[i][cnt2] = res;
            return res;

        };
        cout<<f(0,0,true)<<endl;
    }
   
}
// 64 位输出请用 printf("%lld")

}// 64 位输出请用 printf("%lld")