Submission #1088583

#TimeUsernameProblemLanguageResultExecution timeMemory
1088583DobromirAngelovTents (JOI18_tents)C++14
100 / 100
88 ms70996 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MOD=1e9+7; const int MAXN=3005; int h,w; long long dp[MAXN][MAXN]; long long fact[MAXN]; long long invF[MAXN]; int fastPow(long long x,int pwr) { long long ret=1; while(pwr>0) { if(pwr&1) ret=ret*x%MOD; pwr/=2; x=x*x%MOD; } return ret; } int inverse(int x) { return fastPow(x,MOD-2); } void precomp() { for(int i=0;i<=w;i++) dp[0][i]=1; for(int i=0;i<=h;i++) dp[i][0]=1; for(int i=1;i<=h;i++) { for(int j=1;j<=w;j++) { dp[i][j]=(dp[i][j-1]+i*dp[i-1][j-1]*4)%MOD; } } fact[0]=1; for(int i=1;i<MAXN;i++) fact[i]=fact[i-1]*i%MOD; for(int i=0;i<MAXN;i++) invF[i]=inverse(fact[i]); } int comb(int n,int k) { return (fact[n]*invF[n-k]%MOD)*invF[k]%MOD; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>h>>w; precomp(); long long ans=0; long long P1=1; for(int r=0;r<=min(h,w/2);r++) { long long cur1=comb(h,r); if(r>0) P1=P1*comb(w-2*r+2,2)%MOD; cur1=cur1*P1%MOD; long long P2=1; for(int c=0;c<=min((h-r)/2,w-2*r);c++) { long long cur2=cur1*comb(w-2*r,c)%MOD; if(c>0) P2=P2*comb(h-r-2*c+2,2)%MOD; cur2=cur2*P2%MOD; cur2=cur2*dp[h-r-2*c][w-2*r-c]%MOD; ans+=cur2; if(ans>=MOD) ans-=MOD; } } cout<<(ans-1+MOD)%MOD<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...