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
| #include <bits/stdc++.h> #define FOR(i, x, y) for (remove_const<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i) #define FORD(i, x, y) for (remove_const<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i) using namespace std; typedef long long LL; const int maxn = 285112 + 5, maxm = 20; LL dp[maxn][maxm], s[maxn] = {1}; LL T, n;
void go(LL n, LL rank, LL pos, bool leading) { if (!pos) return; assert(n >= 0 && rank >= 0); LL t = 1 << (pos - 1); LL s = 0; FOR(i, 0, 10) { if (s + dp[n - i * t][pos - 1] <= rank) s += dp[n - i * t][pos - 1]; else { if (!leading || i) cout << i; go(n - i * t, rank - s, pos - 1, leading && !i); return; } } }
int main() { FOR(i, 0, maxm) dp[0][i] = 1; FOR(i, 1, maxn) { s[i] = s[i - 1] + dp[i - 1][maxm - 1]; FOR(j, 1, maxm) { dp[i][j] = dp[i][j - 1]; LL t = 1 << (j - 1); FOR(k, 1, 10) if (t * k <= i) dp[i][j] += dp[i - t * k][j - 1]; else break; } } cin >> T; while (T--) { cin >> n; LL k = upper_bound(s, s + maxn, n) - s - 1; go(k, n - s[k], maxm, 1); puts(""); } }
|