#include <bits/stdc++.h> using namespace std; typedef long long int ll; unordered_map<ll, int> Convert; unordered_map<ll, ll> Helper[20]; unordered_map<ll, bool> Temp; unordered_map<ll, array<ll, 10>> Values[20]; vector<ll> Memorize[20]; int Find(ll x) { ll y = x; while(y > 9) { ll val = y; y = 1; while(val > 0) { y *= (val % 10); val /= 10; } } return Convert[x] = y; } void Preprocess() { Helper[0][1] = 1; for(int i = 1; i <= 18; i++) { for(ll j = 0; j < 10; j++) { for(auto e : Helper[i-1]) Helper[i][e.first * j] += e.second; } } for(auto e : Helper[18]) Find(e.first); Memorize[0].resize(10, 0); for(int i = 1; i <= 18; i++) { Memorize[i].resize(10, 0); for(ll j = 1; j < 10; j++) { for(auto e : Helper[i-1]) Memorize[i][Convert[j * e.first]] += e.second; } for(int j = 0; j < 10; j++) Memorize[i][j] += Memorize[i-1][j]; } for(int i = 1; i <= 18; i++) { for(ll j = 1; j < 10; j++) { for(auto e : Helper[i-1]) Temp[e.first * j] = true; } for(auto e1 : Temp) { for(auto e2 : Helper[18 - i]) Values[18-i][e1.first][Convert[e1.first * e2.first]] += e2.second; } Temp.clear(); } } void Digitize(vector<ll>& Digits, ll n) { while(n > 0) { Digits.push_back(n % 10); n /= 10; } reverse(Digits.begin(), Digits.end()); } vector<ll> Solution(10, 0); vector<ll> Digits; void Solve(ll n) { Digitize(Digits, n); ll mult = 1; int len = Digits.size(); for(int j = 0; j < 10; j++) Solution[j] = Memorize[len-1][j]; for(int i = 0; i < Digits.size(); i++) { for(int j = 0; j < Digits[i]; j++) { if(j == 0 && i == 0) continue; for(int k = 0; k < 10; k++) Solution[k] += Values[len-i-1][mult*j][k]; } mult *= Digits[i]; } Solution[Convert[mult]]++; for(int i = 0; i < 10; i++) { cout << Solution[i] << " "; Solution[i] = 0; } cout << "\n"; Digits.clear(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); Preprocess(); int t; ll n; cin >> t; while(t --> 0) { cin >> n; Solve(n); } return 0; }
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 | #include <bits/stdc++.h> using namespace std; typedef long long int ll; unordered_map<ll, int> Convert; unordered_map<ll, ll> Helper[20]; unordered_map<ll, bool> Temp; unordered_map<ll, array<ll, 10>> Values[20]; vector<ll> Memorize[20]; int Find(ll x) { ll y = x; while(y > 9) { ll val = y; y = 1; while(val > 0) { y *= (val % 10); val /= 10; } } return Convert[x] = y; } void Preprocess() { Helper[0][1] = 1; for(int i = 1; i <= 18; i++) { for(ll j = 0; j < 10; j++) { for(auto e : Helper[i-1]) Helper[i][e.first * j] += e.second; } } for(auto e : Helper[18]) Find(e.first); Memorize[0].resize(10, 0); for(int i = 1; i <= 18; i++) { Memorize[i].resize(10, 0); for(ll j = 1; j < 10; j++) { for(auto e : Helper[i-1]) Memorize[i][Convert[j * e.first]] += e.second; } for(int j = 0; j < 10; j++) Memorize[i][j] += Memorize[i-1][j]; } for(int i = 1; i <= 18; i++) { for(ll j = 1; j < 10; j++) { for(auto e : Helper[i-1]) Temp[e.first * j] = true; } for(auto e1 : Temp) { for(auto e2 : Helper[18 - i]) Values[18-i][e1.first][Convert[e1.first * e2.first]] += e2.second; } Temp.clear(); } } void Digitize(vector<ll>& Digits, ll n) { while(n > 0) { Digits.push_back(n % 10); n /= 10; } reverse(Digits.begin(), Digits.end()); } vector<ll> Solution(10, 0); vector<ll> Digits; void Solve(ll n) { Digitize(Digits, n); ll mult = 1; int len = Digits.size(); for(int j = 0; j < 10; j++) Solution[j] = Memorize[len-1][j]; for(int i = 0; i < Digits.size(); i++) { for(int j = 0; j < Digits[i]; j++) { if(j == 0 && i == 0) continue; for(int k = 0; k < 10; k++) Solution[k] += Values[len-i-1][mult*j][k]; } mult *= Digits[i]; } Solution[Convert[mult]]++; for(int i = 0; i < 10; i++) { cout << Solution[i] << " "; Solution[i] = 0; } cout << "\n"; Digits.clear(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); Preprocess(); int t; ll n; cin >> t; while(t --> 0) { cin >> n; Solve(n); } return 0; } |