TASKSELECT ( Đề thi) Dp Aproach

#include <bits/stdc++.h>
#define task "TASKSELECT"
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long

const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
int a[] = {0, 1, 2, 3, 4, 5};
string n;
int m;
ll dp[12][6][150];
int k;

void Read()
{
    cin >> n >> k;
}

/// dp(i, j, k) là xét đến chữ số thứ i của n, số thứ j trong 4 số và còn đang nhớ k đơn vị
/// dp(i, j, k) = dp(i - 1, 4, v) + dp(i, 1, v') + dp(i, 2, v") + dp(i, 3, v"') + dp(i, 4, v"") với mọi bộ số v / 10 + v' + v" + v"' + v"" = k
/// Cho dễ thì đặt dp(i, 0, z) = dp(i - 1, 4, v)
/// Cơ sở dp(0, 0, 0) = 1
/// Đáp án là dp(m + 1, 0, 0) hay dp(m, 4, n[m] - '0')

ll Cal(string n, int k, vector<int> a)
{
    int m;
    reverse(n.begin(), n.end());
    m = n.size() - 1;
    memset(dp, 0, sizeof dp);
    dp[0][0][0] = 1;
    for (int i = 0; i <= m; ++i)
    {
        for (int j = 1; j <= k; ++j)
            for (int t = 0; t < 150; ++t)
                for (int h = 0; h < 10; ++h)
                    if (h * a[j] <= t)
                        dp[i][j][t] = (dp[i][j][t] + dp[i][j - 1][t - a[j] * h]) % mod;
        for (int j = 0; j < 150; ++j)
            if (j % 10 == n[i] - '0')
                dp[i + 1][0][j / 10] = (dp[i + 1][0][j / 10] + dp[i][k][j]) % mod;
    }
    return dp[m + 1][0][0];
}

void Solve()
{
    ll ans = 0;
    for (int i = 1; i < (1 << k); ++i)
    {
        vector<int> f({0});
        for (int j = 0; j < k; ++j)
            if ((i >> j) & 1)
                f.push_back(a[j + 1]);
        if ((__builtin_popcount(i) & 1) == (k & 1))
            (ans += Cal(n, __builtin_popcount(i), f)) %= mod;
        else
            (ans -= Cal(n, __builtin_popcount(i), f)) %= mod;
    }
    cout << (ans + mod) % mod;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        Read();
        Solve();
    }
}