Submission #1225529

#TimeUsernameProblemLanguageResultExecution timeMemory
1225529mychecksedadTents (JOI18_tents)C++20
100 / 100
191 ms83128 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 5000+100, M = 1e5+10, K = 52, MX = 30; ll f[N], rf[N]; ll po(ll a, ll b){ll res = 1; while(b){if(b&1) (res*=a)%=MOD; b>>=1; (a*=a)%=MOD;} return res;} void precalc(){ f[0] = 1; for(ll i = 1; i < N; ++i) f[i] = (f[i - 1] * i) % MOD; rf[N-1] = po(f[N-1], MOD-2); for(ll i = N-2; i >= 0; --i) rf[i] = (rf[i + 1] * (i+1)) % MOD; } ll c(ll n, ll k){ if(n < k) return 0; return (((f[n] * rf[k]) % MOD) * rf[n - k]) % MOD; } ll n, m, dp[N][N], p2[N], pref[N][N], pref2[N][N]; void solve(){ cin >> n >> m; precalc(); p2[0] = 1; for(int i = 2; i <= max(n, m); i += 2){ p2[i] = (p2[i - 2] * po(2, MOD-2)) % MOD; } ll ans = 0; for(int i = 0; i <= n; ++i){ for(int j = 0; j <= m; ++j){ dp[i][j] = 0; } } for(int i = 0; i <= max(n, m); ++i){ dp[0][i] = dp[i][0] = 1; } // dp[i][j] = using only row - col structure count for(ll i = 1; i <= n; ++i){ for(ll j = 1; j <= m; ++j){ if(i >= 2 && j >= 2){ dp[i][j] = (dp[i - 1][j - 2] * c(j, 2) + dp[i - 2][j - 1] * c(i, 2)) % MOD; dp[i][j] += dp[i - 2][j - 2] * (j - 1) * (i - 1) % MOD; dp[i][j] += dp[i - 2][j - 2] * (j - 1) * (i - 1) % MOD; if(i >= 3 && j >= 3){ ll num = c(i-1, 2) * c(j-1, 2) * 3 % MOD; dp[i][j] += dp[i - 3][j - 3] * num % MOD; } }else if(i >= 2){ dp[i][j] = (dp[i - 2][j - 1] * c(i, 2)) % MOD; // dp[i][j] += dp[i - 2][j - 2] * (j - 1) * (i - 1) % MOD; }else if(j >= 2){ dp[i][j] = (dp[i - 1][j - 2] * c(j, 2)) % MOD; // dp[i][j] += dp[i - 2][j - 2] * (j - 1) * (i - 1) % MOD; } dp[i][j] += dp[i - 1][j - 1] + MOD; dp[i][j] %= MOD; // cerr << dp[i][j] << ' ' << i << ' ' << j << '\n'; } } ll e = 1; for(ll C = 0; C <= min(n, m); ++C, (e*=4)%=MOD){ ll x = ((c(n, C) * c(m, C) % MOD) * e % MOD) * f[C] % MOD; ans += x * dp[n - C][m - C] % MOD; ans %= MOD; } // for(ll A = 0; A <= n && A * 2 <= m; ++A){ // for(ll B = 0; B + 2 * A <= m && 2 * B + A <= n; ++B){ // ll e = 1; // for(ll C = 0; C + A + 2*B <= n && C + 2*A + B <= m; ++C, (e*=4)%=MOD){ // // cerr << A << ' ' << B << ' ' << C << '\n'; // ll y = (c(n-C, A) * c(m-C, 2*A) % MOD) * (f[2*A] * p2[2*A] % MOD) % MOD; // ll z = (c(m-C-2*A, B) * c(n-C-A, 2*B) % MOD) * (f[2*B] * p2[2*B] % MOD) % MOD; // ans += (x*y % MOD) * z; // ans %= MOD; // // cerr << A << ' ' << B << ' ' << C << ' ' << ans << '\n'; // } // } // } // dp[0][0] = 1; // for(int i = 1; i <= max(n, m); ++i){ // dp[0][i] = dp[i][0] = 1; // } // for(int i = 1; i <= n; ++i){ // for(int j = 1; j <= m; ++j){ // if(i >= 2 && j >= 2){ // dp[i][j] = (dp[i - 1][j - 2] * c(j, 2) + dp[i - 2][j - 1] * c(i, 2)) % MOD; // }else if(i >= 2){ // dp[i][j] = (dp[i - 2][j - 1] * c(i, 2)) % MOD; // }else if(j >= 2){ // dp[i][j] = (dp[i - 1][j - 2] * c(j, 2)) % MOD; // } // // cerr << dp[i][j] << " g "; // dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + MOD; // dp[i][j] %= MOD; // // cerr << dp[i][j] << " f "; // dp[i][j] += 4 * (i + j - 1) * dp[i - 1][j - 1]; // dp[i][j] %= MOD; // cerr << i << ' ' << j << ' ' << dp[i][j] << '\n'; // } // } // for(int a = 0; a <= min(n, m); ++a){ // ll x = (po(4, a) * c(n, a) % MOD) * (c(m, a)) % MOD; // ans += x * dp[n - a][m - a] % MOD; // ans %= MOD; // // cerr << a << ' ' << ans << '\n' ; // } cout << ans - 1; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...