Baby Ehab Plays... -> 1516E
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