A partition of a positive integer n is a multiset of positive integers such that their sum is equal to n. We denote the number of partitions of n by p(n). What is the number of ways to partition n into no more than k positive integers?
Difficulty: Very hard.
Input
- There are two integers, n and k.
Output
Output the number of ways modulo 10^9+7 to split n into no more than k positive integers.
Example
Given n=5 and k=3, there are in total 5 solutions: (1+1+3), (1+2+2), (1+4), (2+3), and (5). Thus, the correct output is 5.
Solution: C++
#include<iostream>
using namespace std;
int const max_n=2000; //max value for n
int m[max_n][max_n]={0}; //memorization matrix supposing k <= n <= 2000
int mod = 1000000007;
int partition(int sum, int largestNumber){
if (largestNumber==0) //already consumed all k numbers, n can't be further partitioned
return 0;
if (sum==0) //n correctly partitioned
return 1;
if (sum<0) //n has not been correctly partitioned
return 0;
if (m[sum][largestNumber]!=0) //use memorization of previous calculated partitions
return m[sum][largestNumber];
// partitions including the largest number + partitions not including it
m[sum][largestNumber]=(partition(sum,largestNumber-1)%mod
+ partition(sum-largestNumber,largestNumber)%mod)%mod;
return m[sum][largestNumber];
}
int main(){
int n;
int k;
cin>>n;
cin>>k;
s=partition(n,k);
cout<<s;
}
KejiTech 