Problem 5: Partitions

Points:

Small Case: 10 Answer: 23

Large Case: 20 Answer: 81198940

For any number N, a special partition S= { a1,a2,a3,...... ap } with respect to a given integer 'R', is defined as

1- ai >0 for 1<=i<=p
2- ai+1 >=ai
3- a1+a2+a3+.....ap = N
4- Every number 'm' such that 1<=m<= R*N can be expressed as

where xi belongs to X= {-R,-R+1, ...,-1, 0,1 ,.... ,R-1,R }

For e.g. if N = 3, R = 2 and K = 2,
X = {-2, -1, 0, 1, 2}
There are only two such possible partitions: {1,2} and {1,1,1}.

1 = 1 * 1 + 0 * 2 = 1 * 1 + 0 * 1 + 0 * 1
2 = 0 * 1 + 1 * 2 = 1 * 1 + 1 * 1 + 0 * 1
3 = 1 * 1 + 1 * 2 = 1 * 1 + 1 * 1 + 1 * 1
4 = 2 * 1 + 1 * 2 = 2 * 1 + 1 * 1 + 1 * 1
5 = 1 * 1 + 2 * 2 = 2 * 1 + 2 * 1 + 1 * 1
6 = 2 * 1 + 2 * 2 = 2 * 1 + 2 * 1 + 2 * 1

Small Case:N=10 ,R=2 ,K=5
Large Case:N=1000 ,R=15 ,K=1000

Solution:

Let Sr,k(n) be the number of r-subcomplete partitions of n whose largest part is at most k. Then Sr,1(n) = 1 for all n and for k >= 2

with initial conditions Sr,1(0) = 1 and Sr,0(n) = 0 for all n.

Reference:HoKyu Lee and SeungKyung Park,The r-subcomplete Partitions,2002,Theorem 2.13

Code:

#include <iostream>
#include <cassert>
using namespace std;
const int MOD=100000007;
int S[1001][1001];
int main()
{

    int r=15,k=1000,n=1000;
    int ans=0;

    for(int i=0;i<=k;++i)
        for(int j=0;j<=n;++j)
            S[i][j]=0;

    for ( int i=0;i<=n;++i)
        S[1][i]=1;

    for ( int i=2;i<=k;++i)
        for ( int j=1;j<=n;++j){
            int val=(2*r*j+1)/(2*r+1);
            if ( i > val )
                S[i][j]=S[val][j];
            else
                S[i][j]=(S[i-1][j]+S[i][j-i])%MOD;

        }
    cout<<S[k][n];
return 0;
}