#include <bits/stdc++.h> using namespace std; const int NAX = 1e6 + 5; vector<int> memo(NAX, -1); int simulate(long long x) { if (x < 10) { return x; } if (x < NAX && memo[x] != -1) { return memo[x]; } long long mul = 1; while (x) { mul *= x % 10; x /= 10; } if (x < NAX) { return memo[x] = simulate(mul); } return simulate(mul); } bool ok[25][30][40][60]; // [7][5][3][2] int expo[10][4]; long long INF = 1.000001e18L; vector<long long> dp[20][10][25][30][40]; // dp[len][ans][7][5][3][2] void init() { for (int dig = 1; dig < 10; dig++) { vector<int> p{7,5,3,2}; for (int i = 0; i < 4; i++) { for (int x = dig; x % p[i] == 0; x /= p[i]) { expo[dig][i]++; } } } expo[0][1] = expo[0][3] = 1; // 0 = 2 * 5 long long A = 1; for (int d7 = 0; A < INF; d7++, A *= 7) { long long B = A; for (int d5 = 0; B < INF; d5++, B *= 5) { long long C = B; for (int d3 = 0; C < INF; d3++, C *= 3) { long long D = C; for (int d2 = 0; D < INF; d2++, D *= 2) { ok[d7][d5][d3][d2] = true; int x = simulate(D); dp[0][x][d7][d5][d3].resize(61); dp[0][x][d7][d5][d3][d2]++; } } } } // cout << "Y = " << dp[0][3][0][0][1][0] << "\n"; for (int len = 1; len <= 18; len++) { for (int x = 0; x < 10; x++) { for (int d7 = 0; d7 < 25; d7++) { for (int d5 = 0; d5 < 30; d5++) { for (int d3 = 0; d3 < 40; d3++) { for (int d2 = 0; d2 < (int) dp[len-1][x][d7][d5][d3].size(); d2++) { long long me = dp[len-1][x][d7][d5][d3][d2]; if (me == 0) { continue; } for (int dig = 0; dig < 10; dig++) { if (d7 >= expo[dig][0] && d5 >= expo[dig][1] && d3 >= expo[dig][2] && d2 >= expo[dig][3]) { vector<long long>& v = dp[len][x][d7-expo[dig][0]][d5-expo[dig][1]][d3-expo[dig][2]]; int z = d2 - expo[dig][3]; v.resize(max((int) v.size(), z + 1)); v[z] += me; } } } } } } } } } int main() { init(); int T; cin >> T; while (T--) { string s; cin >> s; int len = (int) s.length(); vector<long long> ans(10); vector<int> pref(4); // cout << "X = " << dp[1][3][0][0][0][0] << "\n"; for (int i = 0; i < len; i++) { for (int dig = (i == 0 ? 1 : 0); dig < s[i] - '0'; dig++) { for (int x = 0; x < 10; x++) { // dp[len][ans][7][5][3][2] if (pref[3] + expo[dig][3] < (int) dp[len-1-i][x][pref[0]+expo[dig][0]][pref[1]+expo[dig][1]][pref[2]+expo[dig][2]].size()) { ans[x] += dp[len-1-i][x][pref[0]+expo[dig][0]][pref[1]+expo[dig][1]][pref[2]+expo[dig][2]][pref[3]+expo[dig][3]]; } } } if (i != 0) { for (int dig = 1; dig < 10; dig++) { for (int x = 0; x < 10; x++) { // cerr << len-1-i << " " << x << " "; // for (int j = 0; j < 4; j++) cerr << expo[dig][j] << " "; // cerr << "\n"; if (expo[dig][3] < (int) dp[len-1-i][x][expo[dig][0]][expo[dig][1]][expo[dig][2]].size()) { ans[x] += dp[len-1-i][x][expo[dig][0]][expo[dig][1]][expo[dig][2]][expo[dig][3]]; } // cerr << "ok\n"; } } } for (int j = 0; j < 4; j++) { pref[j] += expo[s[i]-'0'][j]; } } ans[simulate(stoll(s))]++; for (long long x : ans) { cout << x << " "; } cout << "\n"; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include <bits/stdc++.h> using namespace std; const int NAX = 1e6 + 5; vector<int> memo(NAX, -1); int simulate(long long x) { if (x < 10) { return x; } if (x < NAX && memo[x] != -1) { return memo[x]; } long long mul = 1; while (x) { mul *= x % 10; x /= 10; } if (x < NAX) { return memo[x] = simulate(mul); } return simulate(mul); } bool ok[25][30][40][60]; // [7][5][3][2] int expo[10][4]; long long INF = 1.000001e18L; vector<long long> dp[20][10][25][30][40]; // dp[len][ans][7][5][3][2] void init() { for (int dig = 1; dig < 10; dig++) { vector<int> p{7,5,3,2}; for (int i = 0; i < 4; i++) { for (int x = dig; x % p[i] == 0; x /= p[i]) { expo[dig][i]++; } } } expo[0][1] = expo[0][3] = 1; // 0 = 2 * 5 long long A = 1; for (int d7 = 0; A < INF; d7++, A *= 7) { long long B = A; for (int d5 = 0; B < INF; d5++, B *= 5) { long long C = B; for (int d3 = 0; C < INF; d3++, C *= 3) { long long D = C; for (int d2 = 0; D < INF; d2++, D *= 2) { ok[d7][d5][d3][d2] = true; int x = simulate(D); dp[0][x][d7][d5][d3].resize(61); dp[0][x][d7][d5][d3][d2]++; } } } } // cout << "Y = " << dp[0][3][0][0][1][0] << "\n"; for (int len = 1; len <= 18; len++) { for (int x = 0; x < 10; x++) { for (int d7 = 0; d7 < 25; d7++) { for (int d5 = 0; d5 < 30; d5++) { for (int d3 = 0; d3 < 40; d3++) { for (int d2 = 0; d2 < (int) dp[len-1][x][d7][d5][d3].size(); d2++) { long long me = dp[len-1][x][d7][d5][d3][d2]; if (me == 0) { continue; } for (int dig = 0; dig < 10; dig++) { if (d7 >= expo[dig][0] && d5 >= expo[dig][1] && d3 >= expo[dig][2] && d2 >= expo[dig][3]) { vector<long long>& v = dp[len][x][d7-expo[dig][0]][d5-expo[dig][1]][d3-expo[dig][2]]; int z = d2 - expo[dig][3]; v.resize(max((int) v.size(), z + 1)); v[z] += me; } } } } } } } } } int main() { init(); int T; cin >> T; while (T--) { string s; cin >> s; int len = (int) s.length(); vector<long long> ans(10); vector<int> pref(4); // cout << "X = " << dp[1][3][0][0][0][0] << "\n"; for (int i = 0; i < len; i++) { for (int dig = (i == 0 ? 1 : 0); dig < s[i] - '0'; dig++) { for (int x = 0; x < 10; x++) { // dp[len][ans][7][5][3][2] if (pref[3] + expo[dig][3] < (int) dp[len-1-i][x][pref[0]+expo[dig][0]][pref[1]+expo[dig][1]][pref[2]+expo[dig][2]].size()) { ans[x] += dp[len-1-i][x][pref[0]+expo[dig][0]][pref[1]+expo[dig][1]][pref[2]+expo[dig][2]][pref[3]+expo[dig][3]]; } } } if (i != 0) { for (int dig = 1; dig < 10; dig++) { for (int x = 0; x < 10; x++) { // cerr << len-1-i << " " << x << " "; // for (int j = 0; j < 4; j++) cerr << expo[dig][j] << " "; // cerr << "\n"; if (expo[dig][3] < (int) dp[len-1-i][x][expo[dig][0]][expo[dig][1]][expo[dig][2]].size()) { ans[x] += dp[len-1-i][x][expo[dig][0]][expo[dig][1]][expo[dig][2]][expo[dig][3]]; } // cerr << "ok\n"; } } } for (int j = 0; j < 4; j++) { pref[j] += expo[s[i]-'0'][j]; } } ans[simulate(stoll(s))]++; for (long long x : ans) { cout << x << " "; } cout << "\n"; } } |