Baby Ehab Plays... -> 1516E

 avatar
unknown
c_cpp
9 months ago
1.7 kB
5
Indexable
//Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
void debug(int out){ cerr << out << endl; }

#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 " "
//#define endl "\n"

const int Delta = 1e9+7 , mxxW = 5e2+10 , mxxK = 2e2+10;
int dp[mxxW][mxxK] , out[mxxK] , nCr[mxxW];
int pw (int base , int e)
{ return e? pw(base*base%Delta,e>>1)*(e&1 ? base:1)%Delta:1; }
void fill_nCr (int N)
{
    int Inv[mxxW] , F[mxxW];
    Inv[0] = 1; F[0] = 1;
    loop(i,1,min(N,mxxW-1)){
        Inv[i] = Inv[i-1]*i %Delta;
        F[i] = F[i-1]*(N-i+1) %Delta;
    } Inv[min(N,mxxW-1)] = pw(Inv[min(N,mxxW-1)],Delta-2);
    arc(i,min(N,mxxW-1),1){ Inv[i-1] = Inv[i]*i %Delta; }

    loop(i,1,min(N,mxxW-1)){
        nCr[i] = (Inv[i]*F[i])%Delta;
    }
}

void Engine ()
{
    int N , K; cin >> N >> K;
    fill_nCr(N);
    memset(dp,0,sizeof(dp));
    memset(out,0,sizeof(out));
    dp[0][0] = 1;
    loop(i,2,2*K+5){
        loop(j,1,K){
            dp[i][j] = (dp[i-2][j-1]+dp[i-1][j-1])%Delta;
            dp[i][j] = dp[i][j]*(i-1) %Delta;
        }
    } out[0] = 1;
    loop(i,1,K){
        loop(j,0,2*K+5){
            out[i] = (out[i]+ (dp[j][i]*nCr[j] %Delta))%Delta;
        } if (i>1){ out[i] = (out[i]+out[i-2])%Delta; }
        cout << out[i] << sep;
    } cout << endl;
}

signed main()
{
    Turbo
    int Tc = 1; //cin >> Tc;
    while (Tc--){ Engine(); }
}
Editor is loading...
Leave a Comment