#include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; int hsh = 0; unordered_map<ll, ll> ilocz[19]; unordered_map<ll, int> endno; unordered_map<ll, ll> startwith[19][10]; vector<pair<ll, ll>> startwith_iter[19][10]; ll fact[20]; ll nwt(ll n, ll k){ return fact[n]/fact[k]/fact[n-k]; } ll calc_komb(vector<ll>& v){ int n = v.size(); vector<int> v2(10); for(auto i: v){ v2[i]++; } ll res = 1; for(auto i: v2){ res *= nwt(n, i); n -= i; } return res; } void calc_il(vector<ll>& v){ ll res = 1; for(auto i: v){ res *= i; } ilocz[v.size()][res] += calc_komb(v); ll p = res; while(res >= 10){ ll res2 = 1; while(res){ res2 *= res%10; res /= 10; } res = res2; } endno[p] = res; } int t; ll queries[1001]; void generate(vector<ll>& s){ if(s.size() >= 18) return; calc_il(s); for(int i=9; i>0; i--){ if(s.size() && s.back() > i) break; s.push_back(i); generate(s); s.pop_back(); } } pair<ll, ll> get_highest(ll k){ int n = 1; while(k >= 10){ n++; k /= 10; } return {k, n}; } vector<ll> lt[19]; ll qpow(ll a, ll b){ ll res = 1; while(b){ if(b&1){ res *= a; } a *= a; b>>=1; } return res; } map<pair<ll, ll>, vector<ll>> memoization; int main() { cin.tie(0)->sync_with_stdio(0); fact[0] = 1; for(int i=1; i<20; i++){ fact[i] = fact[i-1]*i; } vector<ll> v; v.reserve(18); generate(v); lt[0].assign(10, 0); for(int i=1; i<19; i++){ lt[i] = lt[i-1]; for(int j=1; j<10; j++){ for(auto [d, k]: ilocz[i-1]){ lt[i][endno[d*j]] += k; } } } for(int i=1; i<19; i++){ for(int j=1; j<10; j++){ startwith[i][j] = startwith[i][j-1]; for(auto [a, b]: ilocz[i-1]){ startwith[i][j][a*j] += b; } /*startwith_iter[i][j].reserve(startwith[i][j].size()); for(auto k: startwith[i][j]){ startwith_iter[i][j].push_back(k); }*/ } } /*for(auto [a, b]: startwith[2][5]){ cerr<<a<<' '<<b<<nl; }*/ /*for(int i=1; i<19; i++){ cerr<<startwith[i][9].size()<<nl; }*/ cin>>t; for(int i=0; i<t; i++){ cin>>queries[i]; } for(int z=0; z<t; z++){ ll k = queries[z]; ll no_len = get_highest(k).second; vector<ll> res = lt[no_len-1]; ll prod = 1; ll prefix = 0; for(int w=no_len-1; w>=0; w--){ int highest = k / qpow(10, w); prefix = prefix*10 + highest; //cerr<<k<<' '<<highest<<' '<<w<<' '<<prefix<<nl; if(memoization.count({prefix, w})){ //cerr<<prefix<<' '<<w<<nl; for(int i=0; i<10; i++){ //cerr<<memoization[{prefix, w}][i]<<' '; res[i] += memoization[{prefix, w}][i]; } //cerr<<nl; } else if(highest){ vector<ll> tmp(10, 0); for(auto [d, q]: startwith[w+1][highest-1]){ tmp[endno[d*prod]] += q; } memoization[{prefix, w}] = tmp; for(int i=0; i<10; i++){ res[i] += tmp[i]; } } k -= highest*qpow(10, w); prod *= highest; } res[endno[prod]]++; ll nonzero = 0; for(int i=0; i<10; i++){ nonzero += res[i]; } res[0] += queries[z]-nonzero; for(int i=0; i<10; i++){ cout<<res[i]<<' '; } cout<<nl; } 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 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | #include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; int hsh = 0; unordered_map<ll, ll> ilocz[19]; unordered_map<ll, int> endno; unordered_map<ll, ll> startwith[19][10]; vector<pair<ll, ll>> startwith_iter[19][10]; ll fact[20]; ll nwt(ll n, ll k){ return fact[n]/fact[k]/fact[n-k]; } ll calc_komb(vector<ll>& v){ int n = v.size(); vector<int> v2(10); for(auto i: v){ v2[i]++; } ll res = 1; for(auto i: v2){ res *= nwt(n, i); n -= i; } return res; } void calc_il(vector<ll>& v){ ll res = 1; for(auto i: v){ res *= i; } ilocz[v.size()][res] += calc_komb(v); ll p = res; while(res >= 10){ ll res2 = 1; while(res){ res2 *= res%10; res /= 10; } res = res2; } endno[p] = res; } int t; ll queries[1001]; void generate(vector<ll>& s){ if(s.size() >= 18) return; calc_il(s); for(int i=9; i>0; i--){ if(s.size() && s.back() > i) break; s.push_back(i); generate(s); s.pop_back(); } } pair<ll, ll> get_highest(ll k){ int n = 1; while(k >= 10){ n++; k /= 10; } return {k, n}; } vector<ll> lt[19]; ll qpow(ll a, ll b){ ll res = 1; while(b){ if(b&1){ res *= a; } a *= a; b>>=1; } return res; } map<pair<ll, ll>, vector<ll>> memoization; int main() { cin.tie(0)->sync_with_stdio(0); fact[0] = 1; for(int i=1; i<20; i++){ fact[i] = fact[i-1]*i; } vector<ll> v; v.reserve(18); generate(v); lt[0].assign(10, 0); for(int i=1; i<19; i++){ lt[i] = lt[i-1]; for(int j=1; j<10; j++){ for(auto [d, k]: ilocz[i-1]){ lt[i][endno[d*j]] += k; } } } for(int i=1; i<19; i++){ for(int j=1; j<10; j++){ startwith[i][j] = startwith[i][j-1]; for(auto [a, b]: ilocz[i-1]){ startwith[i][j][a*j] += b; } /*startwith_iter[i][j].reserve(startwith[i][j].size()); for(auto k: startwith[i][j]){ startwith_iter[i][j].push_back(k); }*/ } } /*for(auto [a, b]: startwith[2][5]){ cerr<<a<<' '<<b<<nl; }*/ /*for(int i=1; i<19; i++){ cerr<<startwith[i][9].size()<<nl; }*/ cin>>t; for(int i=0; i<t; i++){ cin>>queries[i]; } for(int z=0; z<t; z++){ ll k = queries[z]; ll no_len = get_highest(k).second; vector<ll> res = lt[no_len-1]; ll prod = 1; ll prefix = 0; for(int w=no_len-1; w>=0; w--){ int highest = k / qpow(10, w); prefix = prefix*10 + highest; //cerr<<k<<' '<<highest<<' '<<w<<' '<<prefix<<nl; if(memoization.count({prefix, w})){ //cerr<<prefix<<' '<<w<<nl; for(int i=0; i<10; i++){ //cerr<<memoization[{prefix, w}][i]<<' '; res[i] += memoization[{prefix, w}][i]; } //cerr<<nl; } else if(highest){ vector<ll> tmp(10, 0); for(auto [d, q]: startwith[w+1][highest-1]){ tmp[endno[d*prod]] += q; } memoization[{prefix, w}] = tmp; for(int i=0; i<10; i++){ res[i] += tmp[i]; } } k -= highest*qpow(10, w); prod *= highest; } res[endno[prod]]++; ll nonzero = 0; for(int i=0; i<10; i++){ nonzero += res[i]; } res[0] += queries[z]-nonzero; for(int i=0; i<10; i++){ cout<<res[i]<<' '; } cout<<nl; } return 0; } |