People in Cubeland use cubic coins. Not only the unit of currency is called a cube but…
- User
People in Cubeland use cubic coins. Not only the unit of currency is called a cube but also the coins are shaped like cubes and their values are cubes. Coins with values of all cubic numbers up to 9261 (= 213), i.e., coins with the denominations of 1, 8, 27, ..., up to 9261 cubes, are available in Cubeland. Your task is to count the number of ways to pay a given amount using cubic coins of Cubeland. For example, there are 3 ways to pay 21 cubes: twenty one 1 cube coins, or one 8 cube coin and thirteen 1 cube coins, or two 8 cube coin and five 1 cube coins. Input
First line of input contains the total number of test cases T. Next T lines contains amount to be paid. You may assume that all the amounts are positive and less than 10000.
Output
For each of the given amounts to be paid output one line containing a single integer representing the number of ways to pay the given amount using the coins available in Cubeland.
SAMPLE INPUT 2 2 10
SAMPLE OUTPUT 1 2
Assistant
We are asked: count number of ways to pay a given amount using cubic coins: denominations are cubes 1^3=1, 2^3=8, 3^3=27, ..., up to 21^3=9261 (since 21^3 = 9261). So coins: 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096, 4913, 5832, 6859, 8000, 9261.
We need to count the number of ways to sum to amount n using these denominations, unlimited supply (since coins). So it's integer compositions with unlimited copies, order doesn't matter? Wait: "ways to pay" typically considers combinations of coins; order of coins does not matter. Usually coin change problem counts the number of ways to make change where order of coins doesn't matter. The example: for amount 21, they list three ways: twenty one 1s; one 8 and thirteen 1s; two 8s and five 1s. They didn't consider sequences like 8+1+... vs 1+8+..., so it's combinations (unordered). So we need to count number of combinations of these coins (each coin used any number of times) that sum to n. This is classic coin change (ways to make change) where order not matter, so it's like number of integer solutions to sum_{i=1}^{21} a_i * (i^3) = n, with a_i >=0 integer. So we need to compute the number of combinations for each test case.
Given constraints: T not specified but amounts <10000. Up to 10000. Number of coin types: 21 (since 21^3=9261 <10000, 22^3=10648 >10000 so max coin is 9261). So we need to compute number of ways for each n up to 10000.
We could use DP: dp[i][j] = number of ways using first i coins to sum j, classic unbounded knapsack. Since number of coins is small (21) and n max 10000, DP is trivial.
But note: the number of ways can be large? Possibly large? Since n up to 10000, using coins 1,8,... The number of ways could be huge, maybe exceeding 64-bit? We need to output integer. Typically in such problems, they expect using big integers? But the sample output small: 1 and 2. Let's consider: number of ways to partition n using cubes? Since 1 is present, the number of ways is like number of unrestricted partitions? Actually denominations are not all integers; they are cubes; but still many ways because 1 is there, so any amount can be formed, and the number of ways corresponds to number of solutions with many coin types. For n=10000, the number of ways could be huge; maybe exponential. I think typical problems like this from e-olymp or similar often require big integers. But maybe they guarantee the number fits in 64-bit? Let's estimate: The number of ways to represent n using unlimited coins with denominations that include 1 is essentially the number of combinations, which grows roughly like O(n^{k-1})? Actually number of integer partitions with restricted parts? But here parts are specific set of 21 numbers. For n=10000, each coin is at most 9261, but 1 is present, so the number of solutions is the number of ways to choose numbers of other coins, bounded by n/8 etc. The number of solutions is the coefficient in generating function ∏{i=1}^{21} 1/(1-x^{i^3}). This coefficient could be huge. Let's estimate: The number of compositions with parts from a set that includes 1 is like number of ways to put coins: if you consider each coin as a type, the number of solutions is like the number of partitions into parts from the set. For n=10000, with many parts available, the number might be huge. For example, number of partitions of 10000 (with all positive integers) is astronomically large (~ exp(pi sqrt(2n/3))/(4n sqrt(3)) approx 10^106). But here we have only 21 allowed part sizes, not all integers, so number will be smaller but still can be large. Let's approximate: Since 1 is allowed, we can always fill with 1s, but we also have other parts. The number of solutions equals the number of ways to write n = a11 + a88 + a2727 + ... + a92619261. This is like the number of integer partitions with parts from a fixed finite set S. The generating function is product{s in S} 1/(1-x^s). The coefficient growth is polynomial? Wait, consider S = {1, 2} then number of ways to pay n is floor(n/2)+1 which is O(n). That's polynomial. S = {1, 2, 3}? Then number of ways is about n^2/12? Actually number of partitions into 1,2,3 is O(n^2). In general, for a finite set of positive integers that includes 1, the number of partitions into those parts is a quasi-polynomial of degree d-1 where d is the number of denominations? Let's think: The generating function is rational: product_{i=1}^k 1/(1-x^{d_i}) where d_i are positive integers with gcd=1 (since 1 included). This rational function has poles at roots of unity, leading to coefficient growth asymptotically of the form Θ(n^{k-1})? Actually consider unrestricted partitions into any positive integers (infinite set) gives super-polynomial growth (exp(sqrt(n))). But with finite set, it's polynomial. Because the generating function is a rational function with all poles on the unit circle, and the dominant contribution comes from the pole at x=1 of multiplicity k (since denominator factors (1-x^{d_i}) each contributes a simple pole at x=1 because 1-x^{d_i} ~ d_i(1-x) near 1). So product 1/(1-x^{d_i}) ~ 1/((∏ d_i)(1-x)^k) near x=1. The coefficient asymptotics: a_n ~ n^{k-1} / ((k-1)! ∏ d_i). For example k=2 denominations {1, d}: then a_n ~ n/(d) => linear. k=3: quadratic. So with 21 denominations, a_n ~ n^{20} / (20! * ∏ d_i). n=10000 => 10000^{20} = 10^{80}, divided by 20! ~2.4e18, product of d_i is huge: product of cubes 1^32^3*...*21^3 = (∏ i^3) = (21!)^3. 21! ~ 5.1e19, cube ~ 1.33e59. So a_n ~ 10^{80} / (2.4e18 * 1.33e59) = 10^{80} / 3.2e77 = about 3e2? Wait 10^{80}/3.2e77 = 312.5. Actually n^{20} = (10^4)^{20} = 10^{80}. ∏ d_i = ∏ i^3 from i=1..21 = (∏ i)^3 = (21!)^3. 21! ~ 5.109094e19, cube ~ 1.334e59. Multiply by (20)! ≈ 2.43e18 gives about 3.24e77. 10^{80}/3.24e77 ≈ 308. So asymptotic number of ways maybe around 308? That's surprisingly small. But that's asymptotic for large n; maybe n=10000 is not large enough relative to denominations? Actually the asymptotic formula holds as n → ∞, but the growth is polynomial of degree k-1=20, so 10000^20 = 10^{80}, but denominator product is huge because d_i are large. So the constant factor is tiny. So the actual number of ways may be moderate? Let's test small n: For n=100, number of ways? We can try to compute for n=100 with coins up to 64 maybe (since 125>100). But still, number of ways might not be huge. For n=10000, since the highest coin is 9261, the next is 8000, etc. There are many combinations? Let's approximate by considering generating function: The coefficient might be in the thousands or maybe millions? Let's try to do rough mental: The number of ways to represent n as a sum of cubes is like partitions into cubes. The number of partitions of n into parts ≤ n, but only 21 specific part sizes. For n=10000, the maximum number of non-1 coins is limited: you could have up to floor(10000/8) = 1250 of 8's if no other coins, but that's huge; but the asymptotic polynomial suggests that it's not exponential because the number of solutions is essentially the number of integer points in a 20-dimensional polytope defined by sum d_i a_i = n. That number is roughly the volume, which grows as n^{20} / (20! ∏ d_i). For d_i being cubes, product is huge, so maybe number of solutions is not huge. Let's compute that more precisely: d_i = i^3, i=1..21. ∏_{i=1}^{21} i^3 = (21!)^3. 21! ≈ 5.109094e19; cube ≈ 1.334e59 (since log10(21!) ~ 19.708; times 3 = 59.124; so about 1.33e59). 20! ≈ 2.432902e18. So denominator constant = (20)! * ∏ d_i ≈ 2.43e18 * 1.33e59 = 3.23e77. n=10000 -> n^{20} = 10^{80}. So coefficient ~ 3.09e2. That is about 300. So perhaps the number of ways is around a few hundred, maybe up to a few thousand for n=10000. But wait: The asymptotic is for n large relative to the denominations. For n=10000, the highest coin is 9261, which is comparable to n; but that doesn't break the asymptotics because the generating function has all denominators. The asymptotic is valid for n → ∞ but the constant factor assumes contributions from all denominations, but if n is not huge relative to the largest coin, the lower bound might be less. However, the product includes large d_i, but the polytope defined by sum a_i d_i = n, with a_i >= 0, the number of integer solutions is roughly volume of the simplex {x_i >=0, sum x_i d_i <= n} times something. Actually the number of solutions is equal to the number of integer points in the simplex defined by sum d_i a_i = n. That simplex has dimension 20. Its volume is n^{20} / (20! ∏ d_i). So if n=10000, volume = 1e80 / (20! ∏ d_i) = ~300. Since volume is about 300, the number of integer points should be roughly volume, maybe a few times more. So it's plausible that the number of ways is in the order of hundreds to thousands. That fits within 64-bit integer (since 2^63 ~9e18). So we can use 64-bit (unsigned long long) safely.
But let's verify with some small numbers: For n=100, denominations up to 64 (since 125>100). So coins: 1,8,27,64. The number of solutions to a+8b+27c+64d=100. That may be something moderate. Could compute? Likely not huge. For n=1000, maybe still moderate.
Thus we can safely use 64-bit if number of ways stays below say 10^12. But we need to be sure: Consider extreme: n=9999. Could number of ways exceed 2^63? Let's compute upper bound: The number of solutions is at most the number of combinations for the largest coin? Actually each variable a_i can be at most n/d_i. But the number of solutions is bounded by the number of ways to assign a_21 from 0 to floor(n/9261), and then recursively. A trivial bound: For each coin except the smallest, the number of possibilities is roughly n/d_i. A very rough bound: product over i=2..21 of (n/d_i + 1). For n=10000, product = ∏ (floor(10000/i^3)+1). Let's compute quickly: i=2:8 -> floor(10000/8)=1250 -> +1 =1251; i=3:27 -> floor(10000/27)=370 ->+1=371; i=4:64 -> floor=156 ->+1=157; i=5:125 -> 80->81; i=6:216 ->46->47; i=7:343 ->29->30; i=8:512 ->19->20; i=9:729 ->13->14; i=10:1000 ->10->11; i=11:1331 ->7->8; i=12:1728 ->5->6; i=13:2197 ->4->5; i=14:2744 ->3->4; i=15:3375 ->2->3; i=16:4096 ->2->3; i=17:4913 ->2->3; i=18:5832 ->1->2; i=19:6859 ->1->2; i=20:8000 ->1->2; i=21:9261 ->1->2. Multiply these numbers: 1251 * 371 * 157 * 81 * 47 * 30 * 20 * 14 * 11 * 8 * 6 * 5 * 4 * 3 * 3 * 3 * 2 * 2 * 2 * 2? Actually i=21 also 2. That's many factors. Let's approximate product: 1251*371 ≈ 464,000; *157 ≈ 72,888,000; *81 ≈ 5.904e9; *47 ≈ 2.775e11; *30 ≈ 8.325e12; *20 ≈ 1.665e14; *14 ≈ 2.331e15; *11 ≈ 2.564e16; *8 ≈ 2.051e17; *6 ≈ 1.2306e18; *5 ≈ 6.153e18; *4 ≈ 2.461e19; *3 ≈ 7.383e19; *3 ≈ 2.215e20; *3 ≈ 6.645e20; *2 ≈ 1.329e21; *2 ≈ 2.658e21; *2 ≈ 5.316e21; *2 ≈ 1.063e22. So product ~1e22, which exceeds 2^63 (~9.22e18). So the naive product bound exceeds 64-bit. But actual number of solutions is much smaller because the equation constraints the sum; the variables are not independent. The product bound is an overestimate that counts all combinations of counts without regard to sum constraint. The actual number is the number of solutions to the linear equation, which is roughly the volume of the simplex ~300, as argued. So 1e22 is a huge overcount. So actual number likely within 64-bit.
But we need to be absolutely certain. Let's attempt to compute the generating function coefficient for n=10000 using approximate methods: The volume of the simplex {x_i >=0, sum d_i x_i = n} is n^{k-1} / ((k-1)! ∏ d_i). For k=21, n=10000, that gives about 1e80/(20!*∏ d_i). We estimated ~300. The actual integer count is close to that. So it's definitely < 10^6 maybe? But let's see if there is any possibility that the number could be larger than 10^9? The volume is ~300. Integer points count could be maybe a few thousand? Might be up to 10^4? Because the polytope might have many integer points relative to volume; but volume is about 300; the number of integer points in a polytope of volume V in dimension d can be approximated by V + O(boundary). The boundary might add some, but still likely < 1000. So it's safe.
We could also compute for n=9261 (the largest coin). Number of ways: all 1s, or one 9261, or combos with 9261 and others? Actually 9261 can be represented also using smaller coins. But still limited.
Thus using 64-bit integer is fine.
But wait: The problem might be from some contest where they expect big integer? The sample input doesn't hint. But we should check: The problem statement says "Your task is to count the number of ways to pay a given amount using cubic coins." Typically such problems have large outputs; they might require big integer or modular output? But not stated. Usually in competitive programming, they'd ask for number of ways modulo something if it's large. But here they didn't mention modulo. So it's likely small enough.
But we need to be thorough: Could there be up to 21 denominations, and n up to 10000. Let's attempt to compute exact maximum possible number of ways by approximate generating function coefficient. We can try to compute for n=10000 using actual code? Since we cannot run, but we can reason.
The generating function: F(x) = ∏{i=1}^{21} 1/(1 - x^{i^3}). The coefficient a_n = number of partitions of n into parts from S. The asymptotic: a_n ~ (n^{20})/(20! * ∏{i=1}^{21} i^3) * something about periodic? Actually more precisely, the coefficient in the expansion of 1/∏(1-x^{d_i}) with gcd=1 is a quasi-polynomial of degree k-1. That is, for large n, a_n is given by a polynomial in n of degree 20 plus periodic fluctuations. The leading coefficient is 1/((k-1)! ∏ d_i). So indeed it's polynomial, not exponential. So a_n = c n^{20} + lower terms. c = 1/(20! * ∏ d_i). ∏ d_i = ∏ i^3 = (21!)^3. So c ≈ 1/(20! * (21!)^3) = 1/(20! * (21!)^3). Let's compute approximate magnitude: 21! ~ 5.1e19; (21!)^3 ~ 1.33e59; times 20! ~2.43e18 => ~3.23e77. So c ~ 3.09e-78. Multiply by n^{20} = (1e4)^20 = 1e80 => 3.09e2. So about 309. So indeed a_n around 309 for n=10000. For n=9999 it's similar. So definitely not huge.
Therefore we can implement DP with 64-bit integer (unsigned long long). We need to count ways for up to T test cases, each amount <10000. Efficient: Precompute dp[0..10000] using the coin denominations. Classic DP: dp[0] = 1; for each coin c in denominations (sorted increasing), for amount from c to max_n: dp[amount] += dp[amount - c]. This counts combinations where order of coins doesn't matter because we process coins one by one. That's the standard coin change DP.
Edge: denominations: we must include 1^3=1. So dp[0]=1.
We'll compute dp array of size max_n+1 (maybe 10000). Use 64-bit.
Complexities: O(num_coins * max_n) = 21*10000 = 210k operations, trivial.
We need to handle multiple test cases. So we can precompute once then answer each query.
But careful: The DP method as described (for each coin, for amt from coin to max) yields number of combinations (order doesn't matter). That's correct.
Now let's check sample: For n=2: Only using 1s: 1 way. So output 1. For n=10: Ways: ten 1s; one 8 + two 1s? Actually 8+2*1 =10, yes; also maybe other? 1+? can't use 27. So 2 ways. Output 2. So matches.
Thus solution: precompute dp with coin values 1,8,27,...,9261 (i^3 for i=1..21). Then for each test case read n and output dp[n].
Now the problem might have nuance: "cubic coins" up to 21^3=9261. But note 21^3 = 9261 exactly? 21^3 = 9261, correct. So there are 21 denominations. Some denominations might exceed 10000? The largest is 9261, so within 10000. So fine.
Implementation details: Use long long or unsigned long long. Since amounts up to 10000, dp values maybe up to some thousands, so safe.
Let's confirm with a quick test: n=100 maybe? Let's try to compute manually some small n to get intuition: Actually we can compute small n with DP to see if number grows.
But to be extra safe, we can use Python's big integers if we want, but not needed.
Now I'll produce solution in C++ (or Python). Typically problems expect C/C++ but we can answer in either. Since this is a response, I'll produce a generic explanation and code.
But maybe the problem expects use of generating function or DP.
Thus I'll provide solution:
- Precompute array coins: for i from 1 to 21: coins.push_back(iii).
- Initialize dp[0] = 1; rest 0.
- For each coin in coins: for (int j = coin; j <= MAX_N; ++j) dp[j] += dp[j - coin];
- Then for each test case read n, print dp[n].
Check sample.
Potential pitfalls: The dp array may overflow if we use int; but it's safe.
Now let's test with some values manually maybe: n=0? not needed as amounts positive. But dp[0]=1 for base.
Thus answer.
But wait: Are there any other interpretations? Could "ways to pay" consider order? Usually coin change problems count unordered combinations. The example confirms unordered.
Thus final answer.
Now produce final code in C++:
#include #include #include using namespace std;
const int MAX_N = 10000; long long dp[MAX_N+1] = {0};
int main() { vector coins; for (int i=1; i<=21; i++) { coins.push_back(iii); } dp[0] = 1; for (int c : coins) { for (int j=c; j<=MAX_N; j++) { dp[j] += dp[j-c]; } } int T; cin >> T; while (T--) { int n; cin >> n; cout << dp[n] << endl; } return 0; }
That's it.
But is there any risk with integer overflow if using 32-bit int? Since dp values might be around few thousands? Actually maybe dp[10000] could be more than 2^31? Let's compute approximate upper bound: The asymptotic ~300, but the actual count might be larger because of lower-order terms? Let's compute the quasi-polynomial at n=10000. We can try to compute using inclusion-exclusion or generating function to get exact number? Might be a few thousand. Could be as high as a few hundred thousand? Let's test with a similar set: Suppose denominations {1,8,27}. Then number of ways for n is about floor(n/8)+1? Actually with denominations 1,8,27, the number of solutions to a+8b+27c=n. For n=1000, b can range 0..125, and for each b, c is fixed? Actually c can be determined from remainder after using 27. It's not linear; but we can compute by DP. For small set, number of ways grows roughly quadratically? For denominations {1,2} it's linear. For {1,8} it's linear: floor(n/8)+1. For {1,8,27}: number of ways is O(n^2) because two degrees of freedom. Actually with three coins, the number of ways is about n^2/(2827) = n^2/432. For n=1000, that's about 2.3e6/432 ~ 2314. So it's in thousands. For {1,8,27,64} the number would be O(n^3) but divided by product of three larger numbers: 82764=13824, times 3! = 6 -> denominator 82944, so n^3/82944. For n=1000, that's 1e9/8.3e4 ≈ 12048. So that's ~12k. So adding more denominations increases degree but also multiplies denominator. So for 21 denominations, the leading term is n^{20}/(20! * ∏ d_i) which is small. But lower-degree terms could be larger? Actually the quasi-polynomial includes terms of lower degree that could have larger coefficients because denominators are smaller? But they involve sums over subsets? In the full generating function, the coefficient is sum over certain residues. But the leading term is the largest as n→∞, but for moderate n, lower-degree terms could dominate because the leading term coefficient is tiny. However, the degree is high, so n^{20} is huge but multiplied by tiny coefficient. Lower-degree terms like constant term could be larger? Actually the polynomial of degree 20: c20 n^20 + c19 n^19 + ... + c0. c20 is about 3e-78, c19 might be? c19 could be on the order of 1/(19! * ∏ d_i) maybe? Actually from the theory of partial fractions, each term corresponds to a pole at x=1 and also at other roots of unity. The coefficients of lower powers of n from the expansion of 1/(1-x^{d_i}) near x=1? Actually the generating function near x=1: ∏ 1/(1 - x^{d_i}) = 1/(∏ d_i (1-x)^k) * (1 + O(1-x)). So the expansion yields leading term as described. The lower-degree terms are also determined by higher-order expansions, but they will also involve denominators ∏ d_i, so likely also very small. However, there might be contributions from other poles at other roots of unity, which are periodic and bounded. So overall, a_n is the sum of a polynomial of degree 20 with small coefficients plus bounded fluctuations. So for n=10000, the polynomial's leading term ~300, and lower-degree terms might add some but likely total is not extremely large. Possibly a_n could be in the thousands or tens of thousands. Let's test with some intermediate number of coins. For k=4 denominations {1,8,27,64}, we estimated a_n ~ n^3/(682764) = n^3 / (613824) = n^3/82944. For n=10000, that would be 1e12/82944 ≈ 12,054,000. That's 12 million! But is that valid? Wait n=10000, but our coin set {1,8,27,64} only includes up to 64, and we have unlimited copies. The number of ways to pay 10000 with these four coins? Could be huge. Let's recalc: The asymptotic formula for k=4: a_n ~ n^{3}/(3! ∏ d_i) = n^3/(6 * 182764). But note that product includes d_1=1, d_2=8, d_3=27, d_4=64. That's 182764 = 13824. So n^3/(613824) = n^3/82944. For n=10000, n^3 = 1e12, /82944 ≈ 12,056,000. That's about 12 million. So with just 4 coins, number of ways is in millions. This is plausible? Let's test with a smaller n: n=100, a_100 ~ 1e6/82944 ≈ 12. So about 12 ways. That seems plausible? Actually we can manually consider: 100 = 64a +27b+8c + d. a can be 0 or 1. For a=0: then 100 = 27b+8c+d. b max 3. For a=1: remainder 36 => 27b+8c+d=36; b can be 0 or 1. Count them, maybe around 12 ways. So 12 is plausible. For n=1000: n^3=1e9, /82944≈12056, so about 12k ways. That could be plausible. So with 4 coins, a_1000 ~ 12k, which is fine. With 21 coins, we might have many degrees of freedom, but the denominator product is enormous (including 1827...9261). The product of d_i for i=1..21 is massive, as computed ~1.33e59. The leading term coefficient is 1/(20! * 1.33e59) ≈ 1/3.2e77 = 3e-78, so n^20 term gives 3e-78 * 1e80 = 300. So with 21 coins, the number of ways is actually much smaller because each added large coin drastically reduces the volume of the simplex. The contributions from subsets of coins (like using only the first few) also contribute to total ways? But the total count includes all combinations using any of the 21 coins. But if we only use the first few coins, that yields many solutions. Because the DP counts all solutions, including those that use only small denominations. For instance, solutions that use only 1,8,27,64 are a subset of all solutions, and their count is about n^3/82944. For n=10000, that's ~12 million. So the total count must be at least 12 million, because that subset is included. So the earlier asymptotic using all 21 coins (leading term) is not the only contribution; the leading term is from the highest-degree part, but the full generating function includes contributions from all poles, including the pole at x=1 which gives a polynomial of degree 20, but that polynomial's leading term is as computed. However, the polynomial itself is not the only part; the coefficient a_n is exactly equal to that polynomial (for n large enough) plus contributions from other roots of unity which are bounded. Actually wait: For rational generating functions of the form 1/∏{i=1}^k (1 - x^{d_i}), the coefficient a_n is given by a quasi-polynomial of degree k-1. That means there exist polynomials p_0(n),...,p{L-1}(n) such that a_n = p_r(n) when n ≡ r mod L, where L is some period (e.g., lcm of d_i). Each polynomial has degree k-1. So the coefficient a_n is exactly a polynomial in n of degree 20 (with periodic coefficients). There is no other contributions that are not polynomial; the generating function is a rational function with poles only at roots of unity, and the coefficient is exactly a quasi-polynomial of degree k-1 for all n beyond some point. This quasi-polynomial includes the full count, including contributions from using any subset? But if the polynomial degree is 20, then for large n, a_n grows like n^{20} times constant. But we just argued that with only 4 denominations, the count grows like n^3. That's consistent: For the full set of 21 denominations, the degree is 20, not 3. However, the constant for the leading term is extremely small. But for n=10000, the term from the subset of denominations {1,8,27,64} is part of the full count. But the full count's asymptotic is n^{20} * c, which for n=10000 gives ~300, but the subset count is ~12 million. That's contradictory: The full count must be at least the subset count. So either the full count is larger, but the asymptotic n^{20} term should dominate eventually. However, n^{20} term with tiny coefficient might be smaller than n^3 term from subset? But the full generating function is ∏{i=1}^{21} 1/(1-x^{d_i}). This is not equal to sum of generating functions of subsets; it includes all coins. But the coefficient a_n for the full set is not simply the sum of counts for each subset; it's the count with all denominations allowed. This count is definitely larger than the count with only denominations {1,8,27,64}, because you have more options. So the full count should be ≥ 12 million for n=10000. But our earlier asymptotic gave ~300, which is clearly wrong because it's far less than 12 million. So what went wrong? Let's revisit the asymptotic formula: For a generating function ∏{i=1}^{k} 1/(1 - x^{d_i}) where gcd of d_i is 1, the coefficient asymptotics is a_n ~ n^{k-1} / ((k-1)! ∏ d_i) * C? Actually the standard formula: The number of solutions to ∑ d_i a_i = n is approximately n^{k-1} / ((k-1)! ∏ d_i). This is the volume of the simplex {a_i >=0, ∑ d_i a_i = n}. That volume indeed gives the number of integer solutions as n grows. But this is for the number of nonnegative integer solutions to the linear Diophantine equation ∑ d_i a_i = n. That is exactly what we are counting: the number of ways using all denominations. So why would the volume be so small? Let's compute the simplex volume for k=4, d = [1,8,27,64]. Volume = n^{3} / (3! * 182764) = n^3 / (6 * 13824) = n^3 / 82944, which for n=10000 gives about 12 million. That matches the approximate number of solutions. Good.
Now for k=21, volume = n^{20} / (20! * ∏ d_i). For n=10000, we got ~300. That suggests the number of solutions is about 300, which is far less than the number of solutions for the subset of 4 coins (12 million). That cannot be, because adding more coins should increase the number of solutions, not decrease. So there is a mistake: The volume formula gives the number of solutions for the full set of variables? But note: When we add more coins, the dimension increases (k-1 increases), but the product ∏ d_i also increases. The volume for a given n might actually decrease if the new d_i are large? But intuition: More variables give more freedom, so number of solutions should increase. However, the volume formula shows that volume = n^{k-1} / ((k-1)! ∏ d_i). When we add a new variable with a large d_i, the denominator multiplies by that large d_i, while the numerator exponent increases by 1. For moderate n, the denominator factor might outweigh the numerator increase. For example, going from k=4 to k=5, add d_5=125. The volume for k=5 is n^4/(24 * ∏ d_i) where ∏ d_i now includes 125. Compare to k=4 volume: n^3/(6 * ∏{i=1}^4 d_i). The ratio (vol5/vol4) = [n^4/(24 * ∏{i=1}^5 d_i)] / [n^3/(6 * ∏{i=1}^4 d_i)] = (n/4) * (1/d_5) = n/(4125) = n/500. For n=10000, that ratio = 20. So vol5 is 20 times larger than vol4! Actually n/(4d_5) for n=10000 => 10000/(500) =20. So volume increases. So adding a fifth coin increases the volume (number of solutions) by factor 20. So volume grows as we add more coins, as long as n is large relative to the new d_i. For k=21, we need to compute product ∏ d_i and compare. Our earlier computed product for 21 coins gave ∏ d_i = (21!)^3 ≈ 1.33e59. For k=4, product = 182764 = 13824 ≈ 1.38e4. For k=5, product = 13824125=1,728,000 ≈ 1.73e6. So denominator growth is huge as k increases. But numerator n^{k-1} also grows. For n=10000, n^{20} is enormous (1e80). However, denominator (20! * ∏ d_i) also huge (3e77). So volume = 1e80/3e77 = 333. For k=4, volume = 1e12/82944 ≈ 12 million. So indeed the volume for k=21 is much smaller than for k=4? That seems contradictory: For n=10000, the simplex volume for 21 variables is 333, while for 4 variables it's 12 million. That would imply that adding more variables drastically reduces the number of solutions? But we earlier argued that adding more variables increases the number of solutions because you have more options. But wait, the simplex volume for a given n is not directly comparable across different dimensions, because the counting measure is different. The number of integer solutions in dimension k-1 (i.e., with k variables) is roughly the volume of a (k-1)-dimensional simplex. The volume in dimension d is measured in units of d-dimensional volume. But when we compare counts, we compare actual integer counts, not volumes. The volume formula approximates the number of integer points in that simplex. For k=4, the simplex is 3-dimensional, volume ~12e6, number of integer points ~12e6. For k=21, simplex is 20-dimensional, volume ~333, number of integer points ~333? That would mean there are only about 333 integer solutions to ∑{i=1}^{21} a_i d_i = n. But is that plausible? Could there be only 333 ways to represent 10000 using 21 denominations? Let's test with a smaller case: suppose we have denominations {1, 100}. Then number of ways to pay n is floor(n/100)+1, which is about n/100. For n=10000, that's 101. That's linear. Add a third denomination, say 50. Then number of ways increases. For denominations {1,50,100}, the number of ways to pay 10000 is about? It's the number of nonnegative integer solutions to a + 50b + 100c = 10000. That can be solved by iterating over c and b, etc. The count is roughly n^2/(250100) = 1e8/10000 = 10000? Actually n^2/(2*5000) = 1e8/10000 = 10000. So ~10,000. That's larger than 101. So adding a coin increased the count.
Now consider denominations {1, 1000, 10000}. For n=10000, number of ways: using 10000: one way; using 1000s: up to ten, but then 1s. So count is maybe 11? Actually 100010 + 0 =10000; 10009+1000? Wait there is only 1 and 1000 and 10000. So number of solutions to a + 1000b + 10000c = 10000. c can be 0 or 1. If c=1 then remainder 0 => a=0,b=0 =>1 way. If c=0 then a+1000b=10000 => b from 0 to 10, a=10000-1000b => 11 ways. Total 12. That's small. So adding a large coin (10000) reduced the count? Actually compared to just {1,1000}, count would be floor(10000/1000)+1 = 11. So adding 10000 added exactly 1 more way, so total 12. So count remains similar. But adding a medium coin like 50 to {1,1000}? But 50 is not a divisor of 1000? Might increase count. So the count depends on the set.
Now our set of cubes includes many large coins: 9261, 8000, 6859, etc. Many of these are close to n. So for n=10000, many denominations are comparable to n. So many variables are effectively restricted to 0 or 1. That reduces the number of solutions. In fact, for denominations larger than n, they are not used. Since max is 9261, many denominations between 5000 and 9261 can only be used at most once. Those between 2744 and 5000 maybe can be used up to 3 times, etc. So the number of degrees of freedom is not 20 because many variables are heavily constrained. The asymptotic volume formula assumes all variables can range up to n/d_i, which for large d_i is small, but still the volume formula integrates over the whole simplex. However, the simplex in 20 dimensions has volume computed as n^{20}/(20! ∏ d_i). This volume is indeed the number of integer points if all d_i are relatively small compared to n, such that the simplex is well-filled. But if many d_i are comparable to n, the simplex is very narrow in those dimensions, and the integer count may be much smaller than the volume? Actually the volume formula is exact for the continuous volume; the integer count is approximately volume when the region is large in all dimensions relative to the grid spacing. But here, for dimensions corresponding to large d_i, the range is small (like at most 1 or 2). In those dimensions, the continuous approximation fails. The simplex's extent in direction i is at most n/d_i. If n/d_i is small (e.g., less than 1), the simplex is effectively lower-dimensional in that direction? Actually if n/d_i < 1, that variable can only be 0. But all d_i are <= 9261, and n=10000, so n/d_i >= 10000/9261 ≈ 1.08, so all variables can at least be 0 or maybe 1? For i=21, d=9261, n/9261 ≈1.08, so a21 can be 0 or 1. For i=20, d=8000, n/8000=1.25, so a20 can be 0 or 1 (since 28000=16000 > n). So many higher coins have max count 1. For i=19, d=6859, 26859=13718>10000, so max 1. i=18: 5832, 25832=11664>10000 => max 1. i=17: 4913, 24913=9826 ≤10000? Actually 24913=9826, which is less than 10000. So a17 can be 0,1,2? Let's check: 34913=14739 >10000, so max 2. i=16: 4096, 24096=8192, 34096=12288>10000, so max 2. i=15: 3375, 23375=6750, 33375=10125>10000, so max 2. i=14: 2744, 32744=8232, 42744=10976>10000, so max 3. i=13: 2197, 42197=8788, 52197=10985>10000, max 4. i=12: 1728, 51728=8640, 61728=10368>10000, max 5. i=11: 1331, 71331=9317, 81331=10648>10000, max 7. i=10: 1000, up to 10. i=9: 729, up to 13. i=8: 512, up to 19. i=7: 343, up to 29. i=6: 216, up to 46. i=5: 125, up to 80. i=4: 64, up to 156. i=3: 27, up to 370. i=2: 8, up to 1250. i=1: 1, up to 10000. So indeed many variables have small max counts. The volume approximation assumes continuous ranges, but actual integer points are limited. The volume of a 20-dimensional region where some dimensions have range only 0 or 1 is effectively zero? Actually the continuous volume measure would still assign a volume if the ranges are >0. For dimension with range [0,1], the length is 1, which is not negligible. But the product of ranges for all dimensions gives some volume. For example, if each dimension i has range up to n/d_i, the product of those ranges (the hyperrectangle that encloses the simplex) is ∏ (n/d_i) = n^k / ∏ d_i. This is massive: n^21 / ∏ d_i. For n=10000, n^21=1e84, / ∏ d_i (~1.33e59) = 7.5e24. But the simplex volume is smaller by factor 1/k!? Actually the volume of the simplex is n^k/(k! ∏ d_i) if the simplex is the set {a_i >=0, ∑ d_i a_i = n}. The volume in k-dimensions (since there are k variables, but one constraint reduces to k-1 dimensions). Actually careful: The variables are a1,...,ak, with constraint ∑ d_i a_i = n. The volume of the (k-1)-dimensional simplex (the set of nonnegative solutions) is n^{k-1} / ((k-1)! ∏ d_i). This volume is measured in (k-1)-dimensional Lebesgue measure (the volume of the projection onto k-1 coordinates). For k=21, this volume is about 333. That's a 20-dimensional volume. So it's a measure of the size of the solution set in a 20-dimensional space. Even if individual variable ranges are small (like some are only 0 or 1), the volume can still be small. But does a volume of 333 in 20 dimensions correspond to many integer points? In high dimensions, the number of integer points in a region of volume V is approximately V if the region is sufficiently "thick" in all directions. However, if the region is thin in some dimensions (range less than 1), then the region essentially lies on a lower-dimensional subspace. But if the range is exactly 1 (i.e., variable can be 0 or 1), then the continuous region includes a segment of length 1, so it has volume contribution 1 in that dimension. But in integer counting, a dimension with range 1 might have 2 integer points (0 and 1). The continuous volume approximation might undercount because it approximates number of integer points by volume, but in high dimensions, the number of integer points can be much larger than volume if the region is a hypercube of side length 1? Actually consider a hypercube of side length 1 in d dimensions. Its volume is 1. The number of integer points inside it could be up to 2^d (if the cube covers many integer points). But a unit hypercube aligned with the axes, if its corners are at integer coordinates, it contains exactly 2^d integer points (the vertices). But the simplex is not a cube; it's a convex polytope. The number of integer points in a polytope can be much larger than its volume in high dimensions. For example, consider the standard simplex {x_i >=0, sum x_i <= 1} in d dimensions. Its volume is 1/d!. The number of integer points in it? Only the origin and the unit vectors? That's d+1 points, which is much larger than 1/d! for large d (since 1/d! is tiny). So integer points can exceed volume drastically when the polytope is very pointy. So our earlier approximation of number of integer points by volume might be far too low. In fact, the number of integer solutions to ∑ d_i a_i = n can be much larger than the volume, especially when many d_i are large and variables have small ranges. The volume approximation is only valid when the ranges are large compared to 1 in all dimensions, i.e., when n/d_i >> 1 for all i. That's not the case here: for many i, n/d_i is near 1 or small. So the actual number of solutions could be much larger than the volume.
Thus we need to evaluate the actual number for n=10000. Let's try to estimate more accurately. The problem is: count number of nonnegative integer solutions to ∑_{i=1}^{21} a_i * i^3 = n. This is a linear Diophantine equation with 21 variables. For n=10000, we can try to compute approximate number via generating function or DP. But we can trust that DP will give the correct number. We need to ensure the DP values fit in 64-bit. Let's attempt to bound it. We can compute an upper bound using the product of (max count+1) for each variable. That product we computed earlier was ~1e22. That's an upper bound, but it's huge. However, the actual number is likely far less than that product, but could still be as high as? Let's try to estimate more carefully.
We can think of the number of solutions as the number of partitions of n into parts from S. There is known results: the number of partitions into distinct parts? Not distinct. But we can try to approximate by considering the generating function and evaluating coefficient. Since n=10000 and the denominations include many large ones, maybe the number of solutions is not that huge. Let's try to compute a rough DP for a subset to see growth. But we can't run code. Let's try reasoning with inclusion of many small coins: The presence of 1 means any solution is essentially a composition of n using the other coins, with the rest filled by 1s. The number of ways is the number of ways to choose some multiset of other coins that sum to ≤ n, and then the remainder is made up by 1s. So it's equivalent to number of ways to write n as sum of other coins (each used multiple times) plus an arbitrary number of 1s (which just fill remainder). But since 1 is also a coin, it's the same as unrestricted. Another perspective: The generating function is ∏_{i=1}^{21} 1/(1-x^{i^3}). This is the same as generating function for partitions into parts that are cubes. So we need the number of partitions of n into parts that are perfect cubes ≤ 9261. Now, partitions of n into cubes, for n=10000, what is typical size? Partitions into cubes are relatively rare because cubes are sparse and grow quickly. However, many small cubes exist (1,8,27,64,125,216,343,512,729). Those are up to 729, which are 9 denominations. The larger ones are 1000,1331,1728,2197,2744,3375,4096,4913,5832,6859,8000,9261. So there are 12 more large cubes. But because many of the large cubes are near n, they can be used only few times. So the partition function might be moderate.
We can try to approximate the number by dynamic programming for n up to 10000 using only the first 9 coins (up to 729). For n=10000, using only up to 729, the number of ways would be huge? Let's estimate: For denominations {1,8,27,64,125,216,343,512,729}, we have k=9. The volume approximation for these 9 coins (ignoring larger ones) would be n^8/(8! ∏ d_i). ∏ d_i for these 9: 182764125216343512729. Let's compute product: we can compute logs: log10(1)=0, 8=0.90309, 27=1.43136, 64=1.80618, 125=2.09691, 216=2.33445, 343=2.53529, 512=2.70927, 729=2.86273. Sum ≈ 0.90309+1.43136=2.33445; +1.80618=4.14063; +2.09691=6.23754; +2.33445=8.57199; +2.53529=11.10728; +2.70927=13.81655; +2.86273=16.67928. So product ≈ 10^{16.67928} ≈ 4.78e16. 8! =40320. n^8 = (10^4)^8 = 10^{32}. So volume = 10^{32} / (40320 * 4.78e16) = 10^{32} / (1.93e21) = 5.18e10. So about 5e10. That's 50 billion. That's already larger than 2^31, but fits in 64-bit? 5e10 < 9e18, so fits in 64-bit. But this is only the volume approximation for the 9-coin simplex, which might approximate the number of solutions using only these 9 coins. But we also have the larger coins, which will increase the count further. However, the larger coins might not increase the count drastically because they are large and have limited usage. But their inclusion might increase the count because they provide additional ways that combine with the small coins. So total count might be somewhat larger than the 9-coin count. Could it exceed 2^63? Possibly but unlikely given product bounds.
We can try to estimate total count by considering generating function and maybe compute an upper bound more tightly. The total number of solutions is the coefficient of x^n in ∏_{i=1}^{21} 1/(1-x^{i^3}). An upper bound could be obtained by taking the product over i of (1/(1 - x^{i^3})) evaluated at x=1? Not directly. Another bound: The number of solutions is at most the number of solutions to a11 + a28 + ... + a21*9261 = n, where each a_i ≤ n/(i^3). As a trivial upper bound, we have the product of (floor(n/i^3)+1). We computed that product and got about 1e22. This is an upper bound because each combination of a_i values yields a unique sum? Actually the sum is determined by the a_i, so each tuple yields a sum; but not all tuples sum to n; the product counts all tuples regardless of sum, so it's an overcount. To get an upper bound on number of solutions, we need to bound the number of tuples that sum to n. The product bound is the total number of tuples with a_i within range, which is much larger than the number that sum to n. So it's not a tight bound. We need a better estimate.
Let's try to compute approximate count using generating function: For large n, the count should be asymptotically equal to p(n) where p(n) is the quasi-polynomial. But the quasi-polynomial itself, for n=10000, we could compute the leading term plus lower order terms. However, we don't have the full polynomial, but we could approximate by volume times something due to Ehrhart quasi-polynomial. The number of integer points in the dilated simplex n * (standard simplex) is a polynomial in n of degree 20, with leading coefficient volume, and other coefficients related to boundary. So the exact count for n=10000 would be that polynomial evaluated at 10000. This polynomial has rational coefficients that sum to something. The volume is tiny, but the polynomial might have large lower-degree terms? Let's examine the Ehrhart polynomial for the simplex Δ = { (a1,...,a21) >=0 : ∑ d_i a_i = 1 }. The number of integer points in nΔ (i.e., solutions to ∑ d_i a_i = n) is L_Δ(n) = ∑_{j=0}^{20} c_j n^j, where c_20 = volume(Δ) = 1/(20! ∏ d_i). The other coefficients c_j are related to sums over faces etc. They can be expressed in terms of Bernoulli numbers or something. Typically, the Ehrhart polynomial coefficients can be large relative to the leading term if the simplex is not very "full"? Actually consider a simple example: Simplex defined by a1 + a2 + ... + a_k = n (all d_i=1). Its volume in (k-1)-dimensions is n^{k-1}/(k-1)!. The number of integer solutions is C(n+k-1, k-1) which is a polynomial of degree k-1 with leading coefficient 1/(k-1)!. For k=21, that's n^20/20! + lower terms. The lower terms are also polynomial; the coefficient of n^20 is 1/20! ≈ 4.11e-19? Actually 20! ≈ 2.43e18, so 1/20! ≈ 4.11e-19. For n=10000, n^20/20! = 1e80/2.43e18 ≈ 4.11e61, which is astronomically huge. So for d_i=1, the number of solutions is huge. But for our d_i large, the volume is scaled by 1/∏ d_i, making the leading coefficient extremely small.
Now consider the other coefficients in the Ehrhart polynomial: They involve sums of lower-dimensional volumes of faces. The faces correspond to subsets of variables set to 0. For a face where we ignore some variables, the volume would be scaled by product of the corresponding d_i's? More precisely, for the simplex Δ defined by ∑ d_i a_i = 1, the j-dimensional faces have volumes that are 1/(j! * product of corresponding d_i). So the Ehrhart polynomial is L_Δ(n) = ∑{I ⊆ [k], I nonempty} (some combinatorial factor?) Actually the number of integer points in nΔ can be expressed as the coefficient of x^n in ∏ (1-x^{d_i})^{-1}. There is a known formula using the partial fraction expansion: a_n = ∑{j=0}^{k-1} C_j(n) n^j, where C_j(n) are periodic. The constant term for the leading periodic? Actually it's a quasi-polynomial. But we can get an idea of magnitude by evaluating the generating function at n=10000 using approximate methods.
Better approach: Since we can just implement DP with 64-bit and trust it will not overflow, we need to verify that the maximum possible dp[n] for n≤10000 fits in 64-bit. Let's try to compute an approximate upper bound for dp[10000] by actually performing DP in our head? That's not feasible. But we can attempt to get an estimate by considering the contribution of the small coins. As argued, using only coins up to 729 yields a huge number (maybe billions). Could that number exceed 2^63? 2^63 ≈ 9.22e18. If the count from only small coins is less than 9e18, and adding larger coins only increases, we need to ensure the total is still ≤ 9e18. Let's estimate the number of ways using only coins up to 729 more carefully.
We can approximate the number of partitions of n into parts up to 729. This is like the partition function p_{≤729}(n). There is known asymptotic for partitions with restricted part sizes? For partitions into parts from a finite set S, the number grows polynomially. For S = {1,2,...,m}, the number of partitions of n into parts at most m is known to be asymptotic to n^{m-1}/( (m-1)! * m! * ??? Actually not exactly. But here S is specific set of cubes up to 729. However, we can approximate using the volume formula for the simplex with d_i being the cubes. But as we saw, the volume for 9-coin simplex gave about 5e10. That is an estimate of the number of solutions. But that estimate uses continuous approximation and assumes all d_i are such that n/d_i is large. For these 9 coins, the smallest d_i is 1 (range 10000), 8 (1250), 27 (370), 64 (156), 125 (80), 216 (46), 343 (29), 512 (19), 729 (13). The ranges are all >1, but some are not extremely large (e.g., 13). The continuous approximation might be off by a factor (like due to lattice points being more numerous). However, the number of integer points in a 8-dimensional simplex might be roughly volume plus contributions from boundary. Usually, the error is O(V^{(d-1)/d})? For a convex body, the number of integer points = volume + O(surface area). The surface area might be significant if the body is not smooth? For a simplex, the boundary consists of lower-dimensional faces. The sum of lower-dimensional volumes could be of comparable magnitude to the volume? In high dimensions, the volume might be concentrated, but I'm not sure.
But we can compute an exact number for the 9-coin case using generating function or DP? We can't run code now, but we can attempt to approximate by using the Ehrhart polynomial. The number of integer solutions to ∑{i=1}^9 d_i a_i = n is a quasi-polynomial of degree 8. Its leading coefficient is 1/(8! ∏ d_i). ∏ d_i we computed ≈ 4.78e16. So leading term ≈ n^8/(40320*4.78e16) = n^8/(1.93e21). n=10000 => 1e32/1.93e21 = 5.18e10. So the leading term is ~5e10. The next term might be of order n^7, with coefficient perhaps involving sums of reciprocals of products of subsets? The coefficient of n^7 might be something like (1/(7! * ∏ d_i)) * (sum of something). It's hard to compute exactly, but likely the n^7 term is also significant. However, the leading term dominates when n is large relative to the d_i? Since n is 10000 and d_i up to 729, n/d_i is at least 13. So it's moderate. The lower degree terms might contribute less because n^8 is much larger than n^7? For n=10000, n^8 = 1e32, n^7 = 1e28, which is 10000 times smaller. So if the coefficient of n^7 is comparable to that of n^8, then n^7 term would be 10000 times smaller. But the coefficients could differ by factors. For the simplex with d_i not all 1, the Ehrhart coefficients are given by formulas involving Bernoulli polynomials. In general, the polynomial is L(n) = ∑{j=0}^{d} (vol_j(Δ) * n^j) where vol_j are lattice point related measures? Actually the Ehrhart polynomial for a lattice polytope (with vertices not necessarily integer) but our simplex has vertices at (n/d_i) e_i, which are not integer vertices generally. So it's not a lattice polytope, but still Ehrhart theory applies to rational polytopes. The leading term is volume, the second term is half the surface area? Not exactly.
We can approximate by using the fact that the number of solutions is the coefficient of the generating function, which can be computed via DP. Since we can write a program to compute dp for n up to 10000 using 64-bit, we can test if it overflows. In practice, I suspect the values are well within 64-bit. I recall a similar problem: "Cubic Coins" from some contest. I think the number of ways indeed fits in 64-bit. I've seen problems like "Pay the amount with cubic coins" and the answer fits in 64-bit. Actually there's a known problem from UVA or SPOJ: "CUBIC COINS". Let me recall: UVA 11137 - Ingenuous Cubrency. Yes! That's a known problem: UVA 11137: Ingenuous Cubrency. The problem statement: In Cubeland they use cubic coins, denominations are cubes up to 21^3, count ways to pay amount up to 10000. I've solved that before. The UVA problem uses long long (64-bit) and it fits. I remember the DP values for 10000 is something like 158... Actually I recall that the answer for 10000 is about 1.5e? Let's quickly search memory: I think I've seen output for 10000 is 158... something? Actually I vaguely recall that the number for 10000 might be around 158, but I'm not sure. Wait, I've seen some solutions: They use unsigned long long and it works. Many online solutions use long long. So indeed it's safe.
Thus we can proceed with DP using 64-bit.
Now finalize solution.
One more nuance: The problem says "Coins with values of all cubic numbers up to 9261 (= 213), i.e., coins with the denominations of 1, 8, 27, ..., up to 9261 cubes, are available in Cubeland." They wrote 213? Actually 21^3 = 9261, they wrote (= 213) maybe a typo: they meant 21^3? But they wrote 213. Anyway we know correct.
Implementation details: We'll precompute dp[0..10000] as long long.
Time complexity: O(21*10000) = 210k, fine.
Multiple test cases, T lines.
Thus final answer.
We'll provide code in C++.
Now produce final response. ```cpp
#include #include
using namespace std;
const int MAX_AMOUNT = 10000; const int MAX_COIN_IDX = 21; // 21^3 = 9261 < 10000
int main() { // Precompute cubic coin denominations: 1^3, 2^3, ..., 21^3 vector coins; for (int i = 1; i <= MAX_COIN_IDX; ++i) { coins.push_back(i * i * i); }
// DP array: dp[x] = number of ways to pay amount x unsigned long long dp[MAX_AMOUNT + 1] = {0}; dp[0] = 1; // one way to pay amount 0: use no coins for (int coin : coins) { for (int amount = coin; amount <= MAX_AMOUNT; ++amount) { dp[amount] += dp[amount - coin]; } } int T, n; cin >> T; while (T--) { cin >> n; cout << dp[n] << endl; } return 0;}