Partition of n into atmost k distinct partitions modulo m

[4z86RXSz]

Given N and K we have to find the number of partitions of N into at most K parts modulo m.
I was wondering if there was any formula to calculate this type of query.
I know about the recurrence formula p_k(n)=p_k(n−k)+p_k-1(n) also about the ferrers diagram
But this can be used when N and K are small
I need to find for 1 ≤N,K≤ 2∗10⁵
For example:-
p₃(5) = 5,14,23,113,122=5
p₃(3) = 3,12,111=3

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll pk(ll n,ll k,ll m)
{
    if(k==1)
        return 1;
    if(n<0)
        return 0;
    return (pk(n-k,k,m)%m+pk(n,k-1,m)%m)%m;
}
int main()
{
    ll t,m;
    cin>>t>>m;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        cout<<pk(n,k,m)<<endl;
    }
    return 0;
}
Here is my implementation using the recurrence but it is giving TLE for  
large values as time complexity is 2n 

I want to create a dp table to find the value something like

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;

please help me


DP table should look like this

	k
        0 1 2	3	4	5	6	7	8	9	10
n 0	1 1 1	1	1	1	1	1	1	1	1
  1	0 1 1	1	1	1	1	1	1	1	1
  2	0 1 2	2	2	2	2	2	2	2	2
  3	0 1 2	3	3	3	3	3	3	3	3
  4	0 1 3	4	5	5	5	5	5	5	5
  5	0 1 3	5	6	7	7	7	7	7	7
  6	0 1 4	7	9	10	11	11	11	11	11
  7	0 1 4	8	11	13	14	15	15	15	15
  8	0 1 5	10	15	18	20	21	22	22	22
  9	0 1 5	12	18	23	26	28	29	30	30
  10	0 1 6	14	23	30	35	38	40	41	42

[jonnin]

work with me a little. I am old and a little slow.
what is b? Your pseudocode reads into english like
"to get dp[index] compute it from n and k and then use b".
the compute from n and k looks sensible. b came out of nowhere and its use is unclear.

if you can explain the b thing and the last like of your computations, we can probably figure it out, though "something like this" to generate a very specific output is a bit disconcerting.

is b just a placeholder, and it really means
dp[n][k] = f(n-k,k)+f(n-1,k-1);
return; //void function, or returns dp, but certainly not a bool function?!

are you sure this table is right?
N=1, K=1, value = 1, but 3,3 gives 3, from the logic
if(n==k)
return 1;

[ne555]

> I want to create a dp table to find the value
your recurrence is p{k,n}=p{k,n−k}+p{k-1,n}
notice that k decrements by 1 every step, but n decrements by k
you don't need the full table as you are skipping rows