Submission #127552

#TimeUsernameProblemLanguageResultExecution timeMemory
127552RockyBTents (JOI18_tents)C++17
100 / 100
136 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; } int sum(int x, int y) { add(x, y); return x; } int n, m; int dp[3005][3005]; int main() { #ifdef IOI freopen ("in.txt", "r", stdin); freopen ("slow.out", "w", stdout); #endif cin >> n >> m; /* memset(dp, -1, sizeof(dp)); int ans = sum(calc(), -1); cout << ans << nl; */ dp[0][m] = 1; rep(i, 0, n - 1) { rep(j, 0, m) { add(dp[i + 1][j], dp[i][j]); if (j > 0) { add(dp[i + 1][j - 1], dp[i][j] * 1ll * 4 * j % mod); add(dp[i + 2][j - 1], dp[i][j] * 1ll * (n - i - 1) * j % mod); } if (j > 1) add(dp[i + 1][j - 2], dp[i][j] * 1ll * (j * (j - 1) / 2) % mod); } } int ans = -1; rep(i, 0, m) add(ans, dp[n][i]); if (ans < 0) ans += mod; cout << ans; ioi } /* 5116 0 3720 1 450 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...