Openjudge 复杂的整数划分问题

复杂的整数划分问题

总时间限制:
200ms
内存限制:
65536kB
描述
将正整数n 表示成一系列正整数之和,n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ,k>=1 。
正整数n 的这种表示称为正整数n 的划分。
输入
标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N)
输出
对于每组测试数据,输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目
样例输入
5 2
样例输出
2
3
3
提示
第一行: 4+1, 3+2,
第二行: 5,4+1,3+2
第三行: 5,1+1+3, 1+1+1+1+1+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<cstring>
using namespace std;
int arr_1[51][51][51];
int arr_2[51][51];
int arr_3[51][51];
int N_To_K(int n,int max,int k){
    int r=arr_1[n][max][k];
    if(r!=-1)return r;
    else{
        if(max==0){
            r=0;
        }else{
            if(k==0){
                if(n==0)r=1;
                else r=0;
            }else{
                if(n>=max)r=N_To_K(n-max,max,k-1)+N_To_K(n,max-1,k);
                else r=N_To_K(n,n,k);
            }
        }
    }
    arr_1[n][max][k]=r;
    return r;
}
int N_To_Diff(int n,int max){
    int r=arr_2[n][max];
    if(r!=-1)return r;
    else{
        if(max==0||n<0)r=0;
        else if(n==0||n==1)r=1;
        else{
            if(n>=max){
                r=N_To_Diff(n-max,max-1)+N_To_Diff(n,max-1);
            }
            else r=N_To_Diff(n,n);
        }
    }
    arr_2[n][max]=r;
    return r;
}
int N_To_Odd(int n,int max){
    int r=arr_3[n][max];
    if(r!=-1)return r;
    else{
        if(max<=0||n<0)r=0;
        else if(n==0||n==1)r=1;
        else{
            if(n>=max){
                if(max%2==0)r=N_To_Odd(n,max-1);
                else r=N_To_Odd(n-max,max)+N_To_Odd(n,max-2);
            }
            else r=N_To_Odd(n,n);
        }
    }
    arr_3[n][max]=r;
    return r;
}
int main(){
    memset(arr_1,-1,sizeof(arr_1));
    memset(arr_2,-1,sizeof(arr_2));
    memset(arr_3,-1,sizeof(arr_3));
    int n,k;
    while(~scanf("%d %d",&n,&k)){
        printf("%d\n%d\n%d\n",N_To_K(n,n,k),N_To_Diff(n,n),N_To_Odd(n,n));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注