#1184729 (C++23(gcc16)) No.1697 Deque House

• 問題: No.1697 Deque House
• ユーザー: Drtever
• 提出日時: 2026-09-07 10:03:49
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 403 ms / 3,500 ms
• コード長: 4,056 bytes
• コンパイル時間: 3,431 ms
• コンパイル使用メモリ: 190,488 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-09-07 10:05:03
• 合計ジャッジ時間: 6,522 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 20

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MOD = 998244353;

// 快速幂计算
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    if (base < 0) base += MOD;
    exp %= (MOD - 1);
    if (exp < 0) exp += MOD - 1;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long pow2_val[40];

long long P_ways[16][16][2];
long long P_sum[16][16][2];
long long M_ways[16][16][2];
long long M_sum[16][16][2];
long long N_ways[16][16][2];
long long N_sum[16][16][2];

int main() {
    // 提升 I/O 速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    if (!(cin >> N >> K)) return 0;
    
    // 预处理2的各次幂及其逆元（带有平移以支持负数指数）
    for (int d = -15; d <= 15; d++) {
        pow2_val[d + 15] = power(2, d);
    }
    
    memset(P_ways, 0, sizeof(P_ways));
    memset(P_sum, 0, sizeof(P_sum));
    
    // 初始状态 (x=0, y=0, valid=0) 方案数为1
    P_ways[0][0][0] = 1;
    
    for (int i = 1; i <= N; i++) {
        long long A_i;
        cin >> A_i;
        
        // 预处理 A_i 的 0~K 次幂
        long long A_pow[16];
        A_pow[0] = 1;
        for (int d = 1; d <= K; d++) {
            A_pow[d] = (A_pow[d - 1] * A_i) % MOD;
        }
        
        memset(M_ways, 0, sizeof(M_ways));
        memset(M_sum, 0, sizeof(M_sum));
        
        // 降维优化前缀和累加 - 阶段 1 (迭代转移 x)
        for (int y_p = 0; y_p <= K; y_p++) {
            for (int v = 0; v < 2; v++) {
                long long accum_ways = 0;
                long long accum_sum = 0;
                for (int x_curr = 0; x_curr <= K; x_curr++) {
                    long long W_fact = pow2_val[x_curr - y_p + 15];
                    accum_ways = (accum_ways + P_ways[x_curr][y_p][v] * W_fact) % MOD;
                    accum_sum = (accum_sum + P_sum[x_curr][y_p][v] * W_fact) % MOD;
                    
                    int min_val = min(x_curr, K - y_p);
                    long long contrib = A_pow[min_val];
                    
                    M_ways[x_curr][y_p][v] = accum_ways;
                    M_sum[x_curr][y_p][v] = (accum_sum + accum_ways * contrib) % MOD;
                }
            }
        }
        
        memset(N_ways, 0, sizeof(N_ways));
        memset(N_sum, 0, sizeof(N_sum));
        
        // 降维优化前缀和累加 - 阶段 2 (迭代转移 y 并且判定合法性)
        for (int x_curr = 0; x_curr <= K; x_curr++) {
            for (int v = 0; v < 2; v++) {
                long long accum_ways = 0;
                long long accum_sum = 0;
                for (int y_curr = 0; y_curr <= K; y_curr++) {
                    accum_ways = (accum_ways + M_ways[x_curr][y_curr][v]) % MOD;
                    accum_sum = (accum_sum + M_sum[x_curr][y_curr][v]) % MOD;
                    
                    int v_new = v;
                    if (x_curr == K && y_curr == 0) {
                        v_new = 1; // 经过了 (K, 0) 触发合法性标记意味着严格满足 L_K < R_K
                    }
                    
                    N_ways[x_curr][y_curr][v_new] = (N_ways[x_curr][y_curr][v_new] + accum_ways) % MOD;
                    N_sum[x_curr][y_curr][v_new] = (N_sum[x_curr][y_curr][v_new] + accum_sum) % MOD;
                }
            }
        }
        
        // 复制更新后 DP 数组到前置状态中，等待处理下个人
        memcpy(P_ways, N_ways, sizeof(P_ways));
        memcpy(P_sum, N_sum, sizeof(P_sum));
    }
    
    // 我们仅接受抵达状态 x_N = K, y_N = K 且触发过 valid = 1 的解集
    long long final_ans = P_sum[K][K][1];
    long long inv_2_K = power((MOD + 1) / 2, K); // 即 2^{-K} mod 998244353
    final_ans = (final_ans * inv_2_K) % MOD;
    
    cout << final_ans << "\n";
    
    return 0;
}