結果

問題 No.1696 Nonnil
ユーザー 已经死了
提出日時 2025-08-05 21:06:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,819 bytes
コンパイル時間 3,418 ms
コンパイル使用メモリ 282,672 KB
実行使用メモリ 31,312 KB
最終ジャッジ日時 2025-08-05 21:07:14
合計ジャッジ時間 37,410 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 31 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MOD = 998244353;

// 快速幂
i64 mod_pow(i64 a, i64 e){
    i64 r = 1;
    while(e){
        if(e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int sub(int a, int b){ a -= b; if(a < 0 ) a += MOD; return a; }
int mul(i64 a, i64 b){ return int(a * b % MOD); }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 N; 
    int K;
    cin >> N >> K;
    int M;
    cin >> M;

    // forbiddenLen[r] = 在位置 r 结束的所有区间中，最短的那个区间长度
    // 如果没有任何区间以 r 结束，设为 K+1（即不受限制）
    vector<int> forbiddenLen(K+1, K+1);
    for(int i = 0; i < M; i++){
        int L, R;
        cin >> L >> R;
        int len = R - L + 1;
        forbiddenLen[R] = min(forbiddenLen[R], len);
    }

    // dp_prev[t][l]: 在处理到 pos-1 时，缺失集合中已经选了 t 个点，
    // 且末尾连续“1”（缺失）的长度为 l 的方案数。
    // 我们用两个 2D 数组交替滚动。
    vector<vector<int>> dp_prev(K+1), dp_cur(K+1);

    // 初始化 pos=0：还没选任何点，t=0，l=0
    dp_prev[0].assign(1, 1);

    // 从 pos=1 … K 逐步 DP
    for(int pos = 1; pos <= K; pos++){
        int fL = forbiddenLen[pos]; // 当前位置允许的最小禁止长度
        // dp_cur[t] 里，l 最多也只需要到 pos
        for(int t = 0; t <= pos; t++){
            dp_cur[t].assign(pos+1, 0);
        }
        // 先预算 dp_prev 各行的前缀和（全 l 的和）
        static int sum_prev[1505];
        for(int t = 0; t <= pos-1; t++){
            i64 s = 0;
            for(int l = 0; l < (int)dp_prev[t].size(); l++){
                s += dp_prev[t][l];
            }
            sum_prev[t] = int(s % MOD);
        }
        // 转移：当前位置标 0（不缺失）→ 连续缺失 l 归 0
        for(int t = 0; t <= pos-1; t++){
            dp_cur[t][0] = add(dp_cur[t][0], sum_prev[t]);
        }
        // 当前位置标 1（缺失）→ 连续缺失 l+1，但必须 l+1 < fL
        for(int t = 0; t <= pos-1; t++){
            int lim = min(fL-1, (int)dp_prev[t].size()); 
            for(int l = 0; l < lim; l++){
                // dp_prev[t][l] 贡献给 dp_cur[t+1][l+1]
                dp_cur[t+1][l+1] = add(dp_cur[t+1][l+1], dp_prev[t][l]);
            }
        }
        // swap
        dp_prev.swap(dp_cur);
    }

    // 统计 N_t：缺失集合恰好大小 t 的可行方案数
    vector<int> N_t(K+1, 0);
    for(int t = 0; t <= K; t++){
        i64 s = 0;
        for(int l = 0; l < (int)dp_prev[t].size(); l++){
            s += dp_prev[t][l];
        }
        N_t[t] = int(s % MOD);
    }

    // 预计算 pow_jN[j] = j^N mod
    vector<int> pow_jN(K+1, 1);
    for(int j = 1; j <= K; j++){
        pow_jN[j] = mod_pow(j, N);
    }

    // 预计算二项式系数 C[k][j]
    static int C[1505][1505];
    for(int i = 0; i <= K; i++){
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++){
            C[i][j] = add(C[i-1][j-1], C[i-1][j]);
        }
    }

    // 计算 P[k] = k! * S(N,k) = ∑_{j=0..k} (-1)^{k-j} C(k,j) * j^N
    vector<int> P(K+1, 0);
    for(int k = 0; k <= K; k++){
        i64 s = 0;
        for(int j = 0; j <= k; j++){
            i64 term = 1LL * C[k][j] * pow_jN[j] % MOD;
            if((k-j)&1) s = (s - term) % MOD;
            else          s = (s + term) % MOD;
        }
        P[k] = int((s + MOD) % MOD);
    }

    // 最终答案：ans = ∑_{t=0..K} N_t * P[K - t]
    i64 ans = 0;
    for(int t = 0; t <= K; t++){
        ans = (ans + 1LL * N_t[t] * P[K - t]) % MOD;
    }
    cout << (ans + MOD) % MOD << "\n";
    return 0;
}
0