oj.uz

Submission #659769

# Submission time Handle Problem Language Result Execution time Memory
659769 2022-11-19T08:59:05 Z MohammadAghil Tents (JOI18_tents) C++17
100 / 100
 157 ms 117292 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     //      freopen("inp.txt", "r", stdin);
     //      freopen("out.txt", "w", stdout);
     // #else
     //      #define er(args ...) 0
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 3e3 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

ll f[maxn][maxn];
ll C[maxn][maxn], G[maxn];
 
int main(){ IOS();
     int n, m; cin >> n >> m;
     rep(i,0,n+1){
          rep(j,0,m+1){
               f[i][j] = 1;
               if(j && i) f[i][j] = (f[i][j-1] + 4ll*i*f[i-1][j-1])%mod;
          }
     }
     rep(i,0,maxn){
          C[i][0] = 1;
          rep(j,1,i+1) C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
     }
     G[0] = 1;
     rep(i,1,maxn){
          G[i] = 1ll*G[i-1]*i%mod*(2*i-1)%mod;
     }
     ll ans = mod - 1;
     rep(a,0,n+1){
          rep(b,0,m+1){
               if(2*a + b <= n && 2*b + a <= m){
                    ans += f[n - 2*a - b][m - 2*b - a]*C[m][a]%mod*C[n][2*a]%mod*G[a]%mod*C[n-2*a][b]%mod*C[m-a][2*b]%mod*G[b]%mod;
                    ans %= mod;
               }
          }
     }
     cout << ans << '\n';
     return 0-0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 46676 KB Output is correct
2 Correct 26 ms 46764 KB Output is correct
3 Correct 23 ms 46928 KB Output is correct
4 Correct 23 ms 47564 KB Output is correct
5 Correct 24 ms 47032 KB Output is correct
6 Correct 24 ms 47828 KB Output is correct
7 Correct 24 ms 47192 KB Output is correct
8 Correct 24 ms 47824 KB Output is correct
9 Correct 23 ms 47180 KB Output is correct
10 Correct 24 ms 48176 KB Output is correct
11 Correct 23 ms 46760 KB Output is correct
12 Correct 24 ms 48560 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 46676 KB Output is correct
2 Correct 26 ms 46764 KB Output is correct
3 Correct 23 ms 46928 KB Output is correct
4 Correct 23 ms 47564 KB Output is correct
5 Correct 24 ms 47032 KB Output is correct
6 Correct 24 ms 47828 KB Output is correct
7 Correct 24 ms 47192 KB Output is correct
8 Correct 24 ms 47824 KB Output is correct
9 Correct 23 ms 47180 KB Output is correct
10 Correct 24 ms 48176 KB Output is correct
11 Correct 23 ms 46760 KB Output is correct
12 Correct 24 ms 48560 KB Output is correct
13 Correct 26 ms 46700 KB Output is correct
14 Correct 27 ms 56016 KB Output is correct
15 Correct 105 ms 101580 KB Output is correct
16 Correct 28 ms 50396 KB Output is correct
17 Correct 40 ms 59204 KB Output is correct
18 Correct 47 ms 63564 KB Output is correct
19 Correct 124 ms 109432 KB Output is correct
20 Correct 103 ms 97272 KB Output is correct
21 Correct 77 ms 80128 KB Output is correct
22 Correct 75 ms 81832 KB Output is correct
23 Correct 52 ms 73400 KB Output is correct
24 Correct 152 ms 117292 KB Output is correct
25 Correct 121 ms 107816 KB Output is correct
26 Correct 138 ms 113008 KB Output is correct
27 Correct 157 ms 115476 KB Output is correct