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
167
168
169
170
171
172
173
174
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
#define ulli unsigned long long int
using namespace std;

int Z;
ulli n, C[20][20];
vector<ulli> N;
vector<vector<ulli> > result;
vector<pair<int, ulli> > L[20];
map<ulli, ulli> R[20];

ulli encode(ulli x) {
    while (x > 9) {
        ulli res = 1;
        while (x > 0) {
            res = res * (ulli)(x % 10);
            x = x / 10;
        }
        x = res;
    }
    return x;
}

void generate_C() {
    FOR(n,0,19) {
        C[n][0] = 1;
        FOR(k,1,n+1) C[n][k] = C[n][k-1] * (n - k + 1) / k;
    }
}

int total_places;
void traverse(int available_places, int digit, ulli current_product, ulli current_multiplicator) {
    if (current_product % 10 == 0) return;

    // End of calculation
    if (available_places == 0) {
        if (R[total_places].find(current_product) == R[total_places].end()) R[total_places][current_product] = 0;
        R[total_places][current_product] += current_multiplicator;
        return;
    }

    // Last available digit, there are still some places which must be fully filled
    if (digit == 9) {
        FOR(i,0,available_places) current_product = current_product * digit;
        traverse(0, 10, current_product, current_multiplicator);
        return;
    }

    // General case
    ulli digit_multiplicator = 1;
    FOR(choosen_places,0,available_places+1) {
        traverse(
            available_places - choosen_places,
            digit + 1,
            current_product * digit_multiplicator,
            current_multiplicator * C[available_places][choosen_places]
        );
        digit_multiplicator = digit_multiplicator * digit;
    }
}

inline void register_result(vector<pair<int,ulli> > &L, map<ulli,ulli> &R) {
    for(map<ulli, ulli>::iterator it=R.begin(); it!=R.end(); ++it) {
        FOR(i,0,L.size()) {
            result[L[i].first][encode(L[i].second * it->first)] += it->second;
        }
    }
}

int main(){

    // Read data
    scanf("%d", &Z);
    N.resize(Z);
    FOR(z,0,Z) scanf("%lld", &N[z]);

    // Preparation
    generate_C();
    result.resize(Z);
    FOR(i,0,20) {
        L[i].clear();
        R[i].clear();
    }

    // Register L-sequences for all cases
    int max_size = 0;
    FOR(z,0,Z) {

        // Clear result
        result[z].resize(10);
        FOR(i,0,10) result[z][i] = 0;

        // Create representation of number "n"
        ulli tmp = N[z];
        vector<int> repr;
        while (tmp>0) {
            repr.push_back(tmp % 10);
            tmp /= 10;
        }
        reverse(repr.begin(), repr.end());
        if (max_size < repr.size()) max_size = repr.size();

        // -------------------

        // Register all numbers that has less digits than n
        FOR(i,1,repr.size()) L[i].push_back(make_pair(z, 1));

        // Register sector numbers
        ulli current_product = 1;
        FOR(pos,0,repr.size()) {
            FOR(digit,1,repr[pos]) {
                ulli new_product = current_product * (ulli)(digit);
                if (new_product % 10 == 0) continue;
                L[repr.size()-pos-1].push_back(make_pair(z, new_product));
            }

            // We are going deeper - save current digit inside product
            current_product = current_product * (ulli)(repr[pos]);
            if (current_product % 10 == 0) break;
        }
    }

    // Generate all canonical R-sequences and handle matching with L-sequences
    FOR(length, 1, max_size) {
        total_places = length;
        traverse(length, 1, 1, 1);
    }

    // Combine results
    FOR(places,0,20) {
        map<ulli,vector<int> > LM;
        FOR(i,0,L[places].size()) {
            int case_number = L[places][i].first;
            ulli product = L[places][i].second;
            if (LM.find(product) == LM.end()) LM[product] = vector<int>();
            LM[product].push_back(case_number);
        }

        for(map<ulli, ulli>::iterator itR=R[places].begin(); itR!=R[places].end(); ++itR) {
            ulli R_product = itR->first;
            ulli count = itR->second;
            for(map<ulli,vector<int> >::iterator itL=LM.begin(); itL!=LM.end(); ++itL) {
                ulli L_product = itL->first;
                vector<int> &cases = itL->second;
                int x = encode(L_product * R_product);
                FOR(i,0,cases.size()) result[cases[i]][x] += count;
            }
        }
    }

    // Special case
    FOR(i,0,L[0].size()) result[L[0][i].first][encode(L[0][i].second)] += 1;

    // Fix a little bit results and print them
    FOR(z,0,Z) {
        ulli n = N[z];

        // Special case
        result[z][encode(n)] += 1;

        // Fix "0"
        result[z][0] = n;
        FOR(i,1,10) result[z][0] = result[z][0] - result[z][i];

        // Print results
        FOR(i,0,10) printf("%lld ", result[z][i]);
        printf("\n");
    }
}