Baby Ehab Plays... -> 1516E
unknown
c_cpp
a year ago
1.7 kB
11
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