Submission #1225529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225529		mychecksedad	Tents (JOI18_tents)	C++20	100 / 100	191 ms	83128 KiB

tents

/* 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;
} 

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52