第一道数位dp

之前看了讲解视频，然后知道了数位dp的基本代码结构

主要是求一个dp推导，然后再特判最终情况。

这里的dp推导，不是直接循环将dp推导出来
(我看的视频里是用循环推导的dp)
这里面用循环的话，编码难度会很高
因此这里选择的是dfs记忆化递归！

然后，在特判最终情形就好了。

数为dp最为困难的就是dp的推导！！！

#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int max_n = 120;
const int N = 14;
typedef long long ll;
ll f[N][max_n][max_n][max_n];

ll dfs(int pos, int tar, int red, int mod) {
    if (f[pos][tar][red][mod] != -1)return f[pos][tar][red][mod];
    if (pos == 1)return f[pos][tar][red][mod] = !(red | mod);
    f[pos][tar][red][mod] = 0;
    ll cur = 1;
    for (int i = 1;i < pos - 1;++i)cur *= 10;
    for (int i = 0;i <= red && i <= 9;++i) {
        f[pos][tar][red][mod] += dfs(pos - 1, tar, red - i, (mod + cur * i % tar) % tar);
    }return f[pos][tar][red][mod];
}

ll dp(ll n) {
    if (!n)return 0;
    vector<int> nums;
    while (n) {
        nums.push_back(n % 10);
        n /= 10;
    }

    ll res = 0;
    ll last = 0;
    int sum = 0;
    ll cur = 1;
    for (int i = 1;i <= nums.size();++i)cur *= 10;

    for (int i = nums.size() - 1;i >= 0;--i) {
        cur /= 10;
        int x = nums[i];
        if (x) {
            for (int y = 0;y < x;++y) {
                for (int tar = max(1,sum + y);tar <= 108;++tar) {
                    res += dfs(i + 1, tar, tar - y - sum, (y * cur + last) % tar);
                }
            }
        }
        last += x * cur;
        sum += x;
        if (i == 0) {
            res += (last % sum == 0);
        }
    }
    return res;
}


int main() {
    ios::sync_with_stdio(0);
    for (int i = 0;i < N;++i)for (int j = 0;j < max_n;++j)for (int k = 0;k < max_n;++k)for (int o = 0;o < max_n;++o)f[i][j][k][o] = -1;
    int t;cin >> t;
    for (int i = 1;i <= t;++i) {
        ll n;cin >> n;
        cout << "Case " << i << ": " << dp(n) << endl;
    }
}