Tap here to switch tabs
Problem
Submissions

Problem: Ways to Express an Integer as Sum of Powers

Ways to Express an Integer as Sum of Powers asks you to count the sets of distinct positive integers whose powers with exponent x add up to n, returning the result modulo a large prime.

Statement

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, determine the number of sets of unique positive integers c1,c2,…,ck\\{c_1, c_2, \dots, c_k\\} such that n=c1x+c2x+⋯+ckxn = c_1^x + c_2^x + \dots + c_k^x.

Since the answer may be very large, return it modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq n ≤300\leq 300

  • 1≤1 \leq x ≤5\leq 5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Ways to Express an Integer as Sum of Powers

Ways to Express an Integer as Sum of Powers asks you to count the sets of distinct positive integers whose powers with exponent x add up to n, returning the result modulo a large prime.

Statement

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, determine the number of sets of unique positive integers c1,c2,…,ck\\{c_1, c_2, \dots, c_k\\} such that n=c1x+c2x+⋯+ckxn = c_1^x + c_2^x + \dots + c_k^x.

Since the answer may be very large, return it modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq n ≤300\leq 300

  • 1≤1 \leq x ≤5\leq 5