Submission #526590

#TimeUsernameProblemLanguageResultExecution timeMemory
526590XEMPLI5Tents (JOI18_tents)C++17
100 / 100
83 ms73092 KiB
#include <bits/stdc++.h> using namespace std; #define gc getchar_unlocked #define fo(i, n) for (int i = 0; i < n; i++) #define rfo(i, n) for (int i = n - 1; i >= 0; i--) #define REP(i, a, b) for (int i = a; i < b; i++) #define RREP(i, a, b) for (int i = a; i >= b; i--) #define ll long long #define si(x) scanf("%d", &x) #define sl(x) scanf("%lld", &x) #define ss(s) scanf("%s", s) #define pi(x) printf("%d\n", x) #define pl(x) printf("%lld\n", x) #define ps(s) printf("%s\n", s) #define deb(x) cout << #x << "=" << x << endl #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl #define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl #define pb push_back #define mp make_pair #define F first #define S second #define all(x) x.begin(), x.end() #define clr(x) memset(x, 0, sizeof(x)) #define sortall(x) sort(all(x)) #define tr(it, a) for (auto it = a.begin(); it != a.end(); it++) #define PI 3.1415926535897932384626 typedef pair<int, int> pii; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpii; typedef vector<pl> vpl; typedef vector<vi> vvi; typedef vector<vl> vvl; int mpow(int base, int exp); void dfs(int u, int par); const int mod = 1'000'000'007; const int N = 3000 + 100, M = N; vi g[N]; ll dp[N][N], ans[N]; void solve() { int h, w; cin >> h >> w; // dp[i][j] i free rows, j free coloumns ll ans = 0; fo(i, h + 1) { fo(j, w + 1) { if (i == 0 || j == 0) dp[i][j] = 1; else { // place nothing dp[i][j] += dp[i - 1][j]; // place any one tent dp[i][j] += (4 * j * dp[i - 1][j - 1]); // place < > if (j >= 2) dp[i][j] += ((((j * (j - 1)) / 2)) * dp[i - 1][j - 2]); // place up down if (i >= 2) dp[i][j] += (((j * (i - 1))) * (dp[i - 2][j - 1])); dp[i][j] %= mod; } } } ans = dp[h][w] - 1; ans %= mod; ans += mod; ans %= mod; cout << ans << '\n'; return; } int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); srand(chrono::high_resolution_clock::now().time_since_epoch().count()); int t = 1; int cs = 0; while (t - cs) { solve(); cs++; } return 0; } int mpow(int base, int exp) { base %= mod; int result = 1; while (exp > 0) { if (exp & 1) result = ((ll)result * base) % mod; base = ((ll)base * base) % mod; exp >>= 1; } return result; } void ipgraph(int n, int m) { int u, v; while (m--) { cin >> u >> v; u--, v--; g[u].pb(v); g[v].pb(u); } } void dfs(int u, int par) { for (int v : g[u]) { if (v == par) continue; dfs(v, u); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...