Submission #127451

#TimeUsernameProblemLanguageResultExecution timeMemory
127451RockyBTents (JOI18_tents)C++17
0 / 100
33 ms35704 KiB
#include <bits/stdc++.h> #define rep(a, b, c) for (int a = (b); (a) <= (c); a++) #define per(a, b, c) for (int a = (b); (a) >= (c); a--) #define nl '\n' #define ioi exit(0); const int mod = (int)1e9 + 7; const int N = (int)1e4; using namespace std; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; if (x < 0) x += mod; } int sum(int x, int y) { add(x, y); return x; } int bp(int x, int y) { int res = 1; while (y) { if (y & 1) res = res * 1ll * x % mod; x = x * 1ll * x % mod, y >>= 1; } return res; } int n, m; int f[N], rv[N]; int dp[3001][3001]; int cnk(int x, int y) { return (f[x] * 1ll * rv[x - y] % mod) * 1ll * rv[y] % mod; } int ank(int x, int y) { return f[x] * 1ll * rv[x - y] % mod; } int calc(int v = n, int free = m) { if (!v) return 1; if (~dp[v][free]) return dp[v][free]; int res = calc(v - 1, free); // put < or > or ^ or v if (free > 0) add(res, calc(v - 1, free - 1) * 1ll * free * 4 % mod); // connect v and ^ // if (must > 0) add(res, calc(v + 1, free, must - 1) * 1ll * must % mod); // open v // if (free > 0) add(res, calc(v + 1, free - 1, must + 1) * 1ll * free % mod); // connect > and < if (free > 1) add(res, calc(v - 1, free - 2) * 1ll * cnk(free, 2) % mod); return dp[v][free] = res; } int place(int put) { int res = 1; rep(i, 0, put - 1) { res = res * 1ll * cnk(n - 2 * i, 2); } return res; } int main() { #ifdef IOI freopen ("in.txt", "r", stdin); #endif f[0] = rv[0] = 1; rep(i, 1, N - 1) { f[i] = f[i - 1] * 1ll * i % mod; rv[i] = bp(f[i], mod - 2); } cin >> n >> m; //cout << calc() memset(dp, -1, sizeof(dp)); int ans = sum(-1, calc()); rep(i, 1, n / 2) { int take = cnk(m, i) * 1ll * place(i) % mod; // ans = 0; if (i <= m) add(ans, take * 1ll * calc(n - 2 * i, m - i) % mod); //cerr << ans << ' ' << take << ' ' << calc(n - 2 * i, m - i) << nl; } cout << ans; ioi } /* 5116 0 3720 1 450 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...