Creating a dp table

[4z86RXSz]

I want to create a DP table

  sudo code goes like this
f(n,k):
if(n==k)
return 1;
if(n==0)
return 0;
if(dp[n][k]!=-1)
return dp[n][k];
b=f(n-k,k)+f(n-1,k-1);
return dp[n][k]=b;

Dp table should look like this
https://dlmf.nist.gov/26.9#E1

It follow the recursion
https://dlmf.nist.gov/26.9.E8

Please help

[tpb]

How big do you expect this table to be? From your last post you said that n and k could both be up to 200000. A 200000 by 200000 (by 4-bytes per int) array is 80 160 gigabytes.

Can you give a link to the description of the problem?

[4z86RXSz]

@tpb You cant directly view the question on hackerearth without an account so here is the link to its image https://imgur.com/a/nwRmN6h

[jonnin]

I don't understand the last line which returns a boolean in C++, but that clearly isnt your intent, what is that line supposed to do?

[4z86RXSz]

@jonnin I jsut want to create a DP table that looks like this
https://dlmf.nist.gov/26.9#E1

My pseudo code has errors can you help me

the recursion that the DP table follows looks like this
https://dlmf.nist.gov/26.9.E8

I want to make a DP table as large as I can minimum row,cols being 10³

[jonnin]

oh, ok. I will dig into links at home later. I can't go to them from work.
if we throw out the incorrect table generation code, it makes more sense... I will see what I can do if no one beats me to it.

[tpb]

If you only need 1000x1000, that's doable.

#include <iostream>
#include <iomanip>

const int size = 20;    // change this to 1000 for 1000 x 1000
int p[size+1][size+1];

int main() {
    p[0][0] = 1;
    for (int i = 1; i <= size; i++)
        p[i][1] = 1;
    for (int n = 2; n <= size; n++)
        for (int k = 2; k <= n; k++)
            p[n][k] = p[n-k][k] + p[n-1][k-1];
    for (int n = 0; n <= size; n++)
        for (int k = 1; k <= size; k++)
            p[n][k] += p[n][k-1]; // cummulative sum

#if 1    // set this to 0 to turn off printing the table
    std::cout << "    ";
    for (int k = 0; k <= size; k++)
        std::cout << std::setw(3) << k << ' ';
    std::cout << '\n';
    for (int n = 0; n <= size; n++) {
        std::cout << std::setw(3) << n << ' ';
        std::cout << std::setw(3) << p[n][0] << ' ';
        for (int k = 1; k <= size; k++) {
            std::cout << std::setw(3) << p[n][k] << ' ';
        }
        std::cout << '\n';
    }
#endif
}

      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20 
  0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1 
  1   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1 
  2   0   1   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2 
  3   0   1   2   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3 
  4   0   1   3   4   5   5   5   5   5   5   5   5   5   5   5   5   5   5   5   5   5 
  5   0   1   3   5   6   7   7   7   7   7   7   7   7   7   7   7   7   7   7   7   7 
  6   0   1   4   7   9  10  11  11  11  11  11  11  11  11  11  11  11  11  11  11  11 
  7   0   1   4   8  11  13  14  15  15  15  15  15  15  15  15  15  15  15  15  15  15 
  8   0   1   5  10  15  18  20  21  22  22  22  22  22  22  22  22  22  22  22  22  22 
  9   0   1   5  12  18  23  26  28  29  30  30  30  30  30  30  30  30  30  30  30  30 
 10   0   1   6  14  23  30  35  38  40  41  42  42  42  42  42  42  42  42  42  42  42 
 11   0   1   6  16  27  37  44  49  52  54  55  56  56  56  56  56  56  56  56  56  56 
 12   0   1   7  19  34  47  58  65  70  73  75  76  77  77  77  77  77  77  77  77  77 
 13   0   1   7  21  39  57  71  82  89  94  97  99 100 101 101 101 101 101 101 101 101 
 14   0   1   8  24  47  70  90 105 116 123 128 131 133 134 135 135 135 135 135 135 135 
 15   0   1   8  27  54  84 110 131 146 157 164 169 172 174 175 176 176 176 176 176 176 
 16   0   1   9  30  64 101 136 164 186 201 212 219 224 227 229 230 231 231 231 231 231 
 17   0   1   9  33  72 119 163 201 230 252 267 278 285 290 293 295 296 297 297 297 297 
 18   0   1  10  37  84 141 199 248 288 318 340 355 366 373 378 381 383 384 385 385 385 
 19   0   1  10  40  94 164 235 300 352 393 423 445 460 471 478 483 486 488 489 490 490 
 20   0   1  11  44 108 192 282 364 434 488 530 560 582 597 608 615 620 623 625 626 627 

I'm pretty sure there's a way to do it without the table, though.

[4z86RXSz]

@tpb @jonnin
Thanks it worked
yes i also think there is a way to do it without the table but i cant figure out what i have been researching for like 2 days now
N and M required in my question are 2*10⁵
Can you please help me to figure out the way to do it without the table please

https://imgur.com/a/nwRmN6h -Here is the link to the original question

[jonnin]

I would venture a guess that
y = f(n,k) can be solved directly via their examples in 26.9.2 and .3 if you can find the coefficients. I don't see how they did that exactly; this may be the same as saying once you know the answer you can compute the answer.

that last equation might work too, but its using a huge factorial as K gets large, and it only works once N is also large. Table it out so far, then let that take over may be one approach, but I can't say for sure.

you can of course compute any table entry without saving the table, but that isn't any cheaper apart from the memory. you can put the ones you already found in a map, but what are the odds of needing the same entry twice?

anyway, the 'fixed k' approach seems like you would combine that with the observation from the other thread that you are skipping some values...

[tpb]

Only two people solved this one. Here's a cleaned-up copy of the shorter program of the two (the other is almost 600 lines, uses "bigint"s and took 3 times as long using 5 times the memory). Comments were added by me. (I also reduced some array sizes which reduced the time a little and the memory quite a bit.)

// Zhong Ziqian:  Time: 15.82 s   Mem: 13.7 MB

#pragma GCC optimize("-O3","-funroll-all-loops")

#include <vector>
#include <stdio.h>   // printf, scanf
#include <math.h>    // sqrt
#include <string.h>  // memset
#include <stdlib.h>  // atoi
#include <algorithm> // __gcd
using namespace std;

typedef long long ll;

int f[1001][1001], MOD;
int s[11][30001];
int T;
int g[200001], h[2][200001], t[200001];
ll ms[11];

/// a to power b mod MOD
ll qp(ll a, ll b) {
    ll x = 1;
    a %= MOD;
    while (b) {
        if (b & 1) x = x * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return x;
}

ll lcm(ll a, ll b) {
    return a / __gcd(a, b) * b;
}

/// This is used when n is <= 10
/// The program also assumes that MOD == 1000000007 in that case
/// (which is likely, but not technically part of the constraints).
struct Newton {
    ll y[11], g[11];
    int N;

    void work() {
        ll ii = 1;
        for (int i = 1; i <= N; ++i)
            y[i] = (y[i] % MOD + MOD) % MOD;
        for (int i = 1; i <= N; ++i) { 
            g[i] = y[1] * ii % MOD;
            ii = ii * qp(i, MOD-2) % MOD;
            for (int j = 1; j <= N - i; ++j) {
                y[j] = y[j + 1] - y[j];
                if (y[j] < 0)
                    y[j] += MOD;
            }
            y[N - i + 1] = 0;
        }
    }

    ll calc(int x) {
        ll w = 1, a = 0;
        for (int i = 1; i <= N; ++i) {
            a = (a + w * g[i]) % MOD;
            w = w * (x - i) % MOD;
        }
        a = (a % MOD + MOD) % MOD;
        return a;
    }

} ns[11][2520];


int main() {
    scanf("%d%d", &T, &MOD);

    /// Init table used if n and m are <= 1000 (and n > 10)
    f[0][0] = 1;
    for (int i = 1; i <= 1000; ++i)
        for (int j = 0; j <= 1000; ++j) {
            f[i][j] = f[i - 1][j];
            if (j >= i)
                (f[i][j] += f[i][j - i]) %= MOD;
        }

    /// Init table used if n <= 10
    if (MOD == 1000000007) {
        s[0][0] = 1;
        for (int i = 1; i <= 10; ++i)
            for (int j = 0; j <= 30000; ++j) {
                s[i][j] = s[i - 1][j];
                if (j >= i)
                    (s[i][j] += s[i][j - i]) %= MOD;
            }
        ms[0] = 1;
        for (int i = 1; i <= 10; ++i)
            ms[i] = lcm(ms[i - 1], i);
        for (int i = 2; i <= 10; ++i) {
            for (int s = 0; s < ms[i]; ++s) {
                int cn = 0;
                for (int j = s; j <= 30000 && cn <= 29; j += ms[i])
                    ns[i][s].y[ns[i][s].N = ++cn] = ::s[i][j];
                ns[i][s].work();
            }
        }
    }

    while (T--) {
        int n;
        static char s[100001];

        scanf("%d%s", &n, s);

        if (n == 1) {
            puts("1");
            continue;
        }

        /// Subtask 3: T:1,100000  N:1,10  M:1,10^100000  MOD:1e9+7
        if (n <= 10) {
            ll w = 0;
            for (int i = 0; s[i]; ++i)
                w = (w * 10 + s[i] - '0') % (ms[n] * MOD);
            printf("%lld\n", ns[n][w % ms[n]].calc(w / ms[n] + 1));
            continue;
        }

        int m = atoi(s);

        /// Subtask 1: T:1,100000  N:1,1000  M:1,1000  MOD:1,1e9+7
        if (n <= 1000 && m <= 1000)
            printf("%d\n", f[n][m]);

        /// Subtask 2: T:1  N:1,200000  M:1,200000  MOD:1,1e9+7
        else {
            int S = sqrt(max(n,m));
            if (S > n)
                S = n;
            if (!S)
                ++S;
            memset(g, 0, sizeof g);
            g[0] = 1;
            for (int i = 1; i < S; ++i)
                for (int j = i; j <= m; ++j)
                    (g[j] += g[j-i]) %= MOD;
            memset(h, 0, sizeof h);
            memset(t, 0, sizeof t);
            int c = 0;
            h[c][0] = 1;
            for (int i = 0; i * S <= m; ++i) {
                c ^= 1;
                for (int j = 0; j + i * S <= m; ++j) {
                    h[c][j] = h[c ^ 1][j];
                    if (i && j >= i) {
                        (h[c][j] += h[c][j - i]) %= MOD;
                        if (j - i >= n - S)
                            (h[c][j] -= h[c ^ 1][j - i - (n - S)]) %= MOD;
                    }
                    (t[j + i * S] += h[c][j]) %= MOD;
                }
            }
            ll ans = 0;
            for (int i = 0; i <= m; ++i)
                ans = (ans + g[i] * (ll)t[m-i]) % MOD;
            ans = (ans % MOD + MOD) % MOD;
            printf("%d\n", int(ans));
        }
    }
}