Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
1.6 kB
3
Indexable
Never
//Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
void debug(int out){ cerr << out << endl; }
clock_t Timer_Start , Timer_Stop;

#define int long long
#define loop(i , l , r) for (int i = l; i <= r; i++)
#define arc(i , r , l) for (int i = r; i >= l; i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define Turbo ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sep " "

const int Delta = 1e4+333 , MD = 1e9+7 , mxxn = 1e4+10;
int pw (int base , int e , int M)
{ return e? pw(base*base%M,e>>1,M)*(e&1 ? base:1)%M:1; }
int F[mxxn] , Inv[mxxn];
void fill_Ferma ()
{ F[0] = 1;
    loop(i,1,mxxn-1){ F[i] = (F[i-1]*i)%Delta; }
    Inv[mxxn-1] = pw(F[mxxn-1],Delta-2,Delta);
    arc(i,mxxn-1,1){ Inv[i-1] = (Inv[i]*i)%Delta; }
} int nCr (int r , int n)
{ return (F[n]*Inv[r]*Inv[n-r])%Delta; }


void Engine ()
{
    int N , K; cin >> N >> K;
    Timer_Start = clock();

    int dp[N+2][K+1];
    memset(dp,0,sizeof(dp));
    dp[1][0] = 1;
    loop(n,1,N){
        loop(k,0,K){ if (k>(n-1)){ continue; }
            dp[n][k] %= Delta;
            int sz = dp[n][k];
            if (k!=K){ dp[n+1][k+1] += sz; }
            loop(w,0,k){
                dp[n+1][k-w] += sz;
            }
        }
    } cout << dp[N+1][0]%Delta << endl;
}

signed main()
{
    Turbo
    int Tc = 1; //cin >> Tc;
    while (Tc--){ Engine(); }
    Timer_Stop = clock();
    double elapsed = (double)(Timer_Stop-Timer_Start)/CLOCKS_PER_SEC;
    cout << "\nTime elapsed : " << elapsed << 's';
}
Leave a Comment