Given two positive integers n and x.
Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1x + n2x + ... + nkx.
Since the result can be very large, return it modulo 109 + 7.
For example, if n = 160 and x = 3, one way to express n is n = 23 + 33 + 53.
Example 1:
Input: n = 10, x = 2 Output: 1 Explanation: We can express n as the following: n = 32 + 12 = 10. It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.
Example 2:
Input: n = 4, x = 1 Output: 2 Explanation: We can express n in the following ways: - n = 41 = 4. - n = 31 + 11 = 4.
Constraints:
1 <= n <= 3001 <= x <= 5class Solution {
public int numberOfWays(int n, int x) {
int MOD = 1_000_000_007;
long memo[] = new long[n + 1];
memo[0] = 1;
for (int i = 1; Math.pow(i, x) <= n; i++) {
int nk = (int) Math.pow(i, x);
for (int j = n; j >= nk; j--)
memo[j] += memo[j - nk];
}
return (int) (memo[n] % MOD);
}
}class Solution {
int MOD = 1_000_000_007;
public int numberOfWays(int n, int x) {
// Max term: n1^x=n => xlogn1=logn => n1 = 10^(logn/x)
int rt = (int) Math.ceil(Math.pow(10, Math.log10(n) / x));
int memo[][] = new int[n + 1][rt + 1];
for (int i = 0; i <= n; i++)
Arrays.fill(memo[i], -1);
return solve(n, x, rt, memo);
}
private int solve(int n, int x, int rt, int[][] memo) {
if (n == 0)
return 1; // 1 way
else if (n < 0 || rt == 0)
return 0; // invalid; backtrack
if (memo[n][rt] != -1)
return memo[n][rt];
return memo[n][rt] = (solve(n - (int) Math.pow(rt, x), x, rt - 1, memo) + solve(n, x, rt - 1, memo)) % MOD;
}
}class Solution {
int MOD = 1_000_000_007;
public int numberOfWays(int n, int x) {
// Max term: n1^x=n => xlogn1=logn => n1 = 10^(logn/x)
int rt = (int) Math.ceil(Math.pow(10, Math.log10(n) / x));
int memo[][] = new int[n + 1][rt + 1];
for (int i = 0; i <= n; i++)
Arrays.fill(memo[i], -1);
return solve(n, x, rt, memo);
}
private int solve(int n, int x, int rt, int[][] memo) {
if (n == 0)
return 1; // 1 way
else if (n < 0 || rt == 0)
return 0; // invalid; backtrack
if (memo[n][rt] != -1)
return memo[n][rt];
return memo[n][rt] = (solve(n - (int) Math.pow(rt, x), x, rt - 1, memo) + solve(n, x, rt - 1, memo)) % MOD;
}
}