結果

問題 No.535 自然数の収納方法
コンテスト
ユーザー qwewe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0