結果
問題 |
No.535 自然数の収納方法
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:24:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,594 bytes |
コンパイル時間 | 639 ms |
コンパイル使用メモリ | 81,860 KB |
実行使用メモリ | 16,068 KB |
最終ジャッジ日時 | 2025-05-14 13:25:35 |
合計ジャッジ時間 | 4,276 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 TLE * 1 -- * 15 |
ソースコード
#include <iostream> #include <vector> #include <numeric> // For std::min, though not strictly needed if using cmath or algorithm #include <algorithm> // For std::min using namespace std; const int MOD = 1e9 + 7; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; // dp_prev[k][a1_val] means A_{i-1}=k and A_1 was fixed to a1_val // dp_curr[k][a1_val] means A_i=k and A_1 was fixed to a1_val vector<vector<int>> dp_curr(n + 1, vector<int>(n + 1, 0)); vector<vector<int>> dp_prev(n + 1, vector<int>(n + 1, 0)); // Base case for A_1: // If A_1 is set to val, and we are considering paths where A_1 was fixed to val, there's 1 way. for (int val_a1 = 1; val_a1 <= n; ++val_a1) { dp_prev[val_a1][val_a1] = 1; } vector<long long> prefix_sum(n + 1); // Using long long for prefix_sum to avoid overflow before modulo // Loop for A_i from i=2 to N for (int i = 2; i <= n; ++i) { for (int val_a1 = 1; val_a1 <= n; ++val_a1) { // A_1 is fixed to val_a1 // Calculate prefix sums for dp_prev[...][val_a1] prefix_sum[0] = 0; for (int k = 1; k <= n; ++k) { prefix_sum[k] = (prefix_sum[k - 1] + dp_prev[k][val_a1]) % MOD; } for (int val_ai = 1; val_ai <= n; ++val_ai) { // Current A_i is val_ai if (i == 2) { // A_1 = val_a1, A_2 = val_ai // Conditions: A_1-1 < A_2 AND A_1 < A_2+2 bool cond_A2_on_A1 = (val_a1 - 1 < val_ai); bool cond_A1_on_A2 = (val_a1 < val_ai + 2); if (cond_A2_on_A1 && cond_A1_on_A2) { // dp_prev[val_a1][val_a1] is count of ways to set A_1=val_a1 given A_1=val_a1. This is 1. dp_curr[val_ai][val_a1] = dp_prev[val_a1][val_a1]; } else { dp_curr[val_ai][val_a1] = 0; } } else { // A_i for i >= 3 // Sum over A_{i-1} (denoted x): // x <= min(N, val_ai + i - 2) int limit = min(n, val_ai + i - 2); if (limit < 1) { // No possible values for A_{i-1} dp_curr[val_ai][val_a1] = 0; } else { dp_curr[val_ai][val_a1] = prefix_sum[limit]; } } } } // Current dp_curr becomes dp_prev for next iteration // And clear dp_curr if not the last iteration (i.e. if i < N) for(int r = 1; r <= n; ++r) { for(int c = 1; c <= n; ++c) { dp_prev[r][c] = dp_curr[r][c]; if (i < n) { // Only clear if there's a next iteration dp_curr[r][c] = 0; } } } } long long total_ways = 0; // dp_curr table now holds results for A_N (dp_curr[val_aN][val_a1]) for (int val_a1 = 1; val_a1 <= n; ++val_a1) { for (int val_aN = 1; val_aN <= n; ++val_aN) { if (dp_curr[val_aN][val_a1] == 0) continue; // Final conditions involving A_N (val_aN) and A_1 (val_a1): // 1. A_N - N < A_1 // 2. A_N < A_1 + 1 bool cond1 = (val_aN - n < val_a1); bool cond2 = (val_aN < val_a1 + 1); if (cond1 && cond2) { total_ways = (total_ways + dp_curr[val_aN][val_a1]) % MOD; } } } cout << total_ways << endl; return 0; }