Problem: CodeChef: Practical coding for everyone
DIFFICULTY:
EASY.
PROBLEM:
The chef was playing with numbers and he found that natural number N can be obtained by sum various unique natural numbers, For challenging himself chef wrote one problem statement, which he decided to solve in future.
Problem statement: N can be obtained as the sum of Kth power of integers in multiple ways, find total number ways?
After that Cheffina came and read what chef wrote in the problem statement, for having some fun Cheffina made some changes in the problem statement as.
New problem statement: N can be obtained as the sum of Kth power of unique +ve integers in multiple ways, find total number ways?
But, the chef is now confused, how to solve a new problem statement, help the chef to solve this new problem statement.
Program:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,x;
cin>>n>>x;
long long int dp[n+1],i,j;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=1;i<=n;i++)
{
for(j=n;j>=i;j--)
{
long long int y=pow(i,x);
if(j>=y)
{
dp[j]+=dp[j-y];
}
}
}
cout<<dp[n]<<endl;
}
return 0;
}