Given two numbers n and x, find out the total number of ways n can be expressed as the sum of the Xth power of unique natural numbers. As the total number of ways can be very large, so return the number of ways modulo 10^{9 }+ 7. 
Example 1:
Input: 
n = 10, x = 2
Output: 
1 
Explanation: 
10 = 1^{2} + 3^{2}, Hence total 1 possibility. 
Example 2:
Input: 
n = 100, x = 2
Output: 
3
Explanation: 
100 = 10^{2} 
6^{2} + 8^{2} and 1^{2} + 3^{2} + 4^{2} + 5^{2} + 7^{2} 
Hence total 3 possibilities. 
Your Task:  
You don't need to read input or print anything. Complete the function numOfWays() which takes n and x as input parameters and returns the total number of ways n can be expressed as the sum of xth power of unique natural numbers.
Expected Time Complexity: O(n^{2}logn)
Expected Auxiliary Space: O(n)
Constraints:
1 <= n <= 10^{3}
1 <= x <= 5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Complete search

Starter code: #User function Template for python3

class Solution:

	def numOfWays(self, n, x):

		# code here



Solutions:
class Solution:

	def numOfWays(self, n, x):
		M = int(1000000000.0) + 7
		p = []
		i = 1
		while True:
			if pow(i, x) <= n:
				p.append(pow(i, x))
				i += 1
			else:
				break
		dp = [0] * (n + 1)
		dp[0] = 1
		for a in p:
			for i in range(n, -1, -1):
				if i - a >= 0:
					dp[i] = (dp[i - a] + dp[i]) % M
		return dp[n]


import math

class Solution:

	def numOfWays(self, n, x):
		dp = [0] * (n + 1)
		dp[0] = 1
		MOD = 1000000000.0 + 7
		for i in range(1, n + 1):
			for j in range(n, i - 1, -1):
				s = i ** x
				if j >= s:
					dp[j] = (dp[j] + dp[j - s]) % MOD
		return int(dp[n])


from collections import defaultdict

class Solution:

	def numOfWays(self, n, x):
		d = defaultdict(lambda : 0)
		d[0] = 1
		i = 1
		while i ** x <= n:
			temp = defaultdict(lambda : 0)
			for item in d:
				summa = item + i ** x
				if summa <= n:
					temp[summa] += d[item]
			for item in temp:
				d[item] = (d[item] + temp[item]) % (10 ** 9 + 7)
			i += 1
		return d[n]


class Solution:

	def numOfWays(self, n, x):
		list = []
		list.append(1)
		for i in range(1, n + 1):
			list.append(0)
		for i in range(1, n + 1):
			for j in range(n, i - 1, -1):
				a = i ** x
				if j >= a:
					list[j] = (list[j] + list[j - a]) % (10 ** 9 + 7)
		return list[n]


import math

class Solution:

	def rec(self, n, x):
		dp = [0 for i in range(n + 1)]
		dp[0] = dp[1] = 1
		max = int(pow(n, 1.0 / x))
		for i in range(2, max + 1):
			curr = pow(i, x)
			for j in range(n, curr - 1, -1):
				dp[j] += dp[j - curr]
		return dp[n] % (pow(10, 9) + 7)

	def numOfWays(self, n, x):
		return self.rec(n, x)


class Solution:

	def numOfWays(self, n, x):
		l = []
		i = 1
		while i ** x <= n:
			l.append(i)
			i += 1
		t = n
		n = len(l)
		dp = [[0 for _ in range(t + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, t + 1):
				if l[i - 1] ** x <= j:
					dp[i][j] = (dp[i - 1][j - l[i - 1] ** x] + dp[i - 1][j]) % 1000000007
				else:
					dp[i][j] = dp[i - 1][j] % 1000000007
		return dp[-1][-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, x) = input().split()
		n = int(n)
		x = int(x)
		ob = Solution()
		print(ob.numOfWays(n, x))


class Solution:

	def numOfWays(self, n, x):
		d = [i for i in range(1, int(n ** (1 / x)) + 1)]
		n1 = len(d)
		t = [[0 for i in range(n + 1)] for j in range(n1 + 1)]
		for i in range(n1 + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					if i == 0:
						t[i][j] = 0
					if j == 0:
						t[i][j] = 1
				elif d[i - 1] ** x <= j:
					t[i][j] = (t[i - 1][j - d[i - 1] ** x] + t[i - 1][j]) % (10 ** 9 + 7)
				else:
					t[i][j] = t[i - 1][j]
		return t[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numOfWays(self, n, x):

		def fun(n, x, s, k):
			if s == n:
				return 1
			if s > n or k == 0:
				return 0
			if dp[s][k] != -1:
				return dp[s][k]
			ans = (fun(n, x, s, k - 1) + fun(n, x, s + k ** x, k - 1)) % 1000000007
			dp[s][k] = ans
			return ans
		k = int(pow(n, 1 / x))
		s = 0
		dp = []
		for i in range(n):
			dp.append([-1] * (k + 1))
		ans = fun(n, x, s, k)
		return ans


class Solution:

	def express(self, x, target, i, dp):
		if target == 0:
			return 1
		if i < 0:
			return 0
		if dp[target][i] != -1:
			return dp[target][i]
		pa = pow(i, x)
		if pa <= target:
			dp[target][i] = self.express(x, target - pa, i - 1, dp) + self.express(x, target, i - 1, dp)
			return dp[target][i]
		else:
			dp[target][i] = self.express(x, target, i - 1, dp)
			return dp[target][i]

	def numOfWays(self, n, x):
		mod = 10 ** 9 + 7
		dp = [[-1] * 1001 for _ in range(1001)]
		return self.express(x, n, n, dp) % mod


def numHelper(i, n, x, dp):
	if i ** x > n:
		return 0
	if i ** x == n:
		return 1
	if dp[n - i ** x][i + 1] == -1:
		tempAns = numHelper(i + 1, n - i ** x, x, dp)
		dp[n - i ** x][i + 1] = tempAns
	else:
		tempAns = dp[n - i ** x][i + 1]
	if dp[n][i + 1] == -1:
		tempAns2 = numHelper(i + 1, n, x, dp)
		dp[n][i + 1] = tempAns2
	else:
		tempAns2 = dp[n][i + 1]
	return tempAns + tempAns2

class Solution:

	def numOfWays(self, n, x):
		ii = int(n ** (1 / x)) + 1
		dp = [[-1 for i in range(ii + 10)] for j in range(n + 10)]
		count = numHelper(1, n, x, dp)
		return count % (7 + 10 ** 9)


class Solution:

	def numOfWays(self, n, x):
		dp = [0 for i in range(n + 1)]
		dp[0] = 1
		MOD = 10 ** 9 + 7
		for i in range(1, n + 1):
			for j in range(n, i - 1, -1):
				y = i ** x
				if j >= y:
					dp[j] = (dp[j] + dp[j - y]) % MOD
		return dp[n]


import math

class Solution:

	def numOfWays(self, n, x):
		mod = 1000000000.0 + 7
		dp = [0] * (n + 1)
		dp[0] = dp[1] = 1
		for i in range(2, n + 1):
			for j in range(n, i - 1, -1):
				y = i ** x
				if y <= j:
					dp[j] = int((dp[j] + dp[j - y]) % mod)
		return dp[n]


import math

class Solution:

	def numOfWays(self, n, x):
		i = 1
		p = []
		while math.pow(i, x) <= n:
			p.append(int(math.pow(i, x)))
			i += 1
		dp = [[-1 for i in range(0, n + 1)] for j in range(0, len(p))]
		mod = pow(10, 9) + 7

		def back(i, n, x, s, p):
			if s == n:
				return 1
			if s > n or i > len(p) - 1:
				return 0
			if dp[i][s] != -1:
				return dp[i][s]
			dp[i][s] = back(i + 1, n, x, s, p) + back(i + 1, n, x, s + p[i], p)
			return dp[i][s] % mod
		return back(0, n, x, 0, p) % mod


class Solution:

	def numOfWays(self, n, x):

		def solve(n, x, curr_val, dp):
			mod = 1000000007
			if n == 0:
				return 1
			if n < 0 or curr_val <= 0:
				return 0
			if dp[n][curr_val] != -1:
				return dp[n][curr_val]
			dp[n][curr_val] = (solve(n - curr_val ** x, x, curr_val - 1, dp) + solve(n, x, curr_val - 1, dp)) % mod
			return dp[n][curr_val]
		st_val = int(n ** (1.0 / x))
		dp = [[-1] * (st_val + 1) for _ in range(n + 1)]
		return solve(n, x, st_val, dp)


class Solution:

	def numOfWays(self, n, x):
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		maxLimit = int(n ** (1 / x))
		for i in range(2, maxLimit + 1):
			curr = i ** x
			for j in range(n, curr - 1, -1):
				dp[j] += dp[j - curr]
		mm = 1000000007
		return dp[n] % mm


class Solution:

	def numOfWays(self, n, x):
		dp = [0] * (n + 1)
		dp[0] = 1
		mod = 1000000007
		for i in range(1, n + 1):
			for j in range(n, i - 1, -1):
				y = pow(i, x)
				if j >= y:
					dp[j] = (dp[j] + dp[j - y]) % mod
		return dp[n]


class Solution:

	def numOfWays(self, n, x):
		dp = [0 for _ in range(n + 1)]
		dp[0] = 1
		M = pow(10, 9) + 7
		for i in range(1, n + 1):
			for j in range(n, i - 1, -1):
				y = pow(i, x)
				if j >= y:
					dp[j] = (dp[j] + dp[j - y]) % M
		return dp[n]