結果
問題 |
No.824 Many Shifts Hard
|
ユーザー |
|
提出日時 | 2019-06-30 17:21:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 1,682 bytes |
コンパイル時間 | 1,267 ms |
コンパイル使用メモリ | 168,720 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 08:30:55 |
合計ジャッジ時間 | 2,656 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) using namespace std; using ll = long long; const int MOD = 1000000007; struct mint { int n; mint(int n_ = 0) : n(n_) {} }; mint operator-(mint a) { return -a.n + MOD * (a.n != 0); } mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; } mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; } mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; } mint &operator+=(mint &a, mint b) { return a = a + b; } mint &operator-=(mint &a, mint b) { return a = a - b; } mint &operator*=(mint &a, mint b) { return a = a * b; } istream &operator>>(istream &i, mint &a) { return i >> a.n; } ostream &operator<<(ostream &o, mint a) { return o << a.n; } mint dp0[305][305]; mint dp1[305][305]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, K; cin >> N >> K; for (int i = 0; i <= K-1; i++) { dp0[i][i+1]=1; } rep(i, K) { memset(dp1, 0, sizeof(dp1)); rep(j, K+1) rep(k, K+1) { if (dp0[j][k].n == 0) continue; if (j == 0) { if (j < k-1) dp1[j][k-1] += dp0[j][k]; dp1[j][k] += dp0[j][k]*(N-1); } else { dp1[j-1][k] += dp0[j][k]; if (j < k-1) dp1[j][k-1] += dp0[j][k]; dp1[j][k] += dp0[j][k]*max(0, N-2); } } swap(dp0, dp1); } mint ans = 0; for (int i = 1; i <= N; i++) { if (i + K <= N) { ans += i * dp0[0][1]; } else { int x = N - i + 1; for (int j = 0; j < K-x+1; j++) { ans += i * dp0[j][K-x+1]; } } } cout << ans << '\n'; }