Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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();
- }
- }
Add Comment
Please, Sign In to add comment