# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1115510 | Neco_arc | Tents (JOI18_tents) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include <C:\debug.hpp>
#endif // ONLINE_JUDGE
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "flagger"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x) >> (i))&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) (5e3 + 5)
using namespace std;
const ll mod = 1e9 + 7; //972663749
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, m;
ll f[maxn][maxn];
inline void Add(ll &x, ll y) {
if((x += y) >= mod) x -= mod;
}
ll C(ll x) { return (x * (x - 1) / 2) % mod; }
void solve()
{
cin >> n >> m;
fi(i, 0, n) fi(j, 0, m) {
if(i == 0 || j == 0) { f[i][j] = 1; continue; };
ll val = (f[i - 1][j] + 4 * j % mod * f[i - 1][j - 1] % mod) % mod;
Add(f[i][j], val);
/// chon cung hang
if(j >= 2) {
ll val = C(j) * f[i - 1][j - 2];
Add(f[i][j], val);
}
/// chon cung cot
if(i >= 2) {
ll val = (i - 1) * j % mod * f[i - 2][j - 1];
Add(f[i][j], val);
}
}
cout << (f[n][m] + mod - 1) % mod;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}