Competetive-Code-Learns/array size concept + dp.cpp at master · RohanGoyal2014/Competetive-Code-Learns · GitHub

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
 * Problem:https://www.spoj.com/problems/COUNT/
 * References:https://brilliant.org/wiki/identical-objects-into-identical-bins/
 *
 *
 * Key Point: array of size 5000*5000 worked globally but did not work locally
 *            Further map<pii,int> and vector<int> dp[] were slow so did not work
 * */
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mkp(a,b) make_pair(a,b)
#define eb emplace_back
#define mod (long long)(1e9+7)
#define FILE_READ freopen("input.txt","r",stdin)
#define FILE_WRITE freopen("output.txt","w",stdout)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long ul;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int dp[5001][5001],cum[5001][5001];
ll solve(int n,int r)
{
    if(n<r)
    {
        return 0;
    }
    if(n==r || r==1 || n==r+1)
    {
        return 1;
    }
    if(r==2)
    {
        return n/2;
    }
    ll ans=0;
    for(int i=1;i<=r;++i)
    {
        ans=ans+solve(n-r,i);
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
//    FILE_READ;
//    FILE_WRITE;
    int mod2=1988;
    memset(cum,0,sizeof(cum));
    for(int i=1;i<=5000;++i)
    {
        for(int j=1;j<=5000;++j)
        {
            if(j==1)
            {
                dp[i][j]=1;
            }
            else if(j>i)
            {
                dp[i][j]=0;
            }
            else if(j==2)
            {
                dp[i][j]=i/2;
            }
            else if(i==j || i==j+1)
            {
                dp[i][j]=1;
            }
            else
            {
                dp[i][j]=cum[i-j][j];
            }
            cum[i][j]=(cum[i][j-1]+dp[i][j])%mod2;
        }
    }
//    for(int i=1;i<=7;++i)
//    {
//        for(int j=1;j<=4;++j)
//        {
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    while(1)
    {
        int a,b;
        cin>>a>>b;
        if(a==0 && b==0)
        {
            break;
        }
        cout<<dp[a][b]<<endl;
    }


    return 0;
}