結果

問題 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:24:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,818 bytes
コンパイル時間 1,000 ms
コンパイル使用メモリ 90,332 KB
実行使用メモリ 16,064 KB
最終ジャッジ日時 2025-05-14 13:25:28
合計ジャッジ時間 5,067 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;

const long long MOD = 998244353;

// Computes Q(x) = P(x) / (x + term_val)
// p_coeffs: coefficients of P(x)
// q_coeffs: output coefficients of Q(x)
// p_actual_degree: actual degree of P(x)
// coeffs_array_size: allocated size of p_coeffs and q_coeffs arrays (max_coeffs_stored + 1)
void poly_divide_by_linear(const vector<long long>& p_coeffs, vector<long long>& q_coeffs, 
                           long long term_val, int p_actual_degree, int coeffs_array_size) {
    
    fill(q_coeffs.begin(), q_coeffs.begin() + coeffs_array_size, 0);

    if (p_actual_degree < 0) p_actual_degree = 0; // Should not happen, but defensive

    if (p_actual_degree == 0) {
        // P(x) is a constant. If (x+term_val) was a factor, P(x) must have been 0.
        // The resulting polynomial Q(x) is 0. q_coeffs is already filled with 0.
        return;
    }

    // q_{D-1} = p_D
    q_coeffs[p_actual_degree - 1] = p_coeffs[p_actual_degree];
    
    // For k from D-1 down to 1: q_{k-1} = p_k - term_val * q_k
    for (int k = p_actual_degree - 1; k >= 1; --k) {
        long long val_q_k = q_coeffs[k];
        q_coeffs[k - 1] = (p_coeffs[k] - (term_val * val_q_k) % MOD + MOD) % MOD;
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q_count;
    cin >> n >> q_count;

    vector<long long> a_arr(n);
    map<long long, int> a_freq;
    for (int i = 0; i < n; ++i) {
        cin >> a_arr[i];
        a_freq[a_arr[i]]++;
    }

    vector<long long> query_results_final;

    for (int qi = 0; qi < q_count; ++qi) {
        long long l_query, r_query, p_target;
        cin >> l_query >> r_query >> p_target;

        int s_range = r_query - l_query;
        // max_coeffs_stored is the highest DEGREE we might need for p_coeffs
        int max_coeffs_stored = p_target + s_range; 
        if (max_coeffs_stored > n) max_coeffs_stored = n;

        // p_coeffs array stores coefficients from degree 0 to max_coeffs_stored
        // Its size is max_coeffs_stored + 1
        vector<long long> p_coeffs(max_coeffs_stored + 1, 0);
        p_coeffs[0] = 1; 
        long long k_val = 1;
        int current_poly_actual_degree = 0; 

        for (int i = 0; i < n; ++i) {
            if (a_arr[i] >= l_query) {
                long long term_const = (a_arr[i] - 1 + MOD) % MOD;
                int next_poly_degree = min(n, current_poly_actual_degree + 1);
                
                // Loop k from highest possible degree downwards
                for (int k = min(next_poly_degree, max_coeffs_stored); k >= 0; --k) {
                    long long prev_coeff_val = (k > 0) ? p_coeffs[k - 1] : 0; // Coeff of x^(k-1) from previous poly
                    long long current_coeff_val_times_const = (p_coeffs[k] * term_const) % MOD;
                    p_coeffs[k] = (current_coeff_val_times_const + prev_coeff_val) % MOD;
                }
                current_poly_actual_degree = next_poly_degree;
            } else {
                k_val = (k_val * a_arr[i]) % MOD;
            }
        }
        
        long long total_xor_sum = 0;
        vector<long long> temp_q_coeffs(max_coeffs_stored + 1); 

        for (long long c = l_query; c <= r_query; ++c) {
            long long needed_p_coeff_val = 0;
            if (p_target <= current_poly_actual_degree && p_target <= max_coeffs_stored) {
                 needed_p_coeff_val = p_coeffs[p_target];
            }
            long long term_result = (k_val * needed_p_coeff_val) % MOD;
            total_xor_sum ^= term_result;

            if (c < r_query) {
                int num_aj_equal_c = 0;
                if (a_freq.count(c)) {
                    num_aj_equal_c = a_freq[c];
                }

                if (num_aj_equal_c > 0) {
                    for (int k_iter = 0; k_iter < num_aj_equal_c; ++k_iter) {
                        k_val = (k_val * c) % MOD;
                        // Check if polynomial is not already zero or degree effectively < 0
                        if (current_poly_actual_degree >= 0) { 
                           long long term_to_divide_val = (c - 1 + MOD) % MOD;
                           poly_divide_by_linear(p_coeffs, temp_q_coeffs, term_to_divide_val, current_poly_actual_degree, max_coeffs_stored + 1);
                           p_coeffs.swap(temp_q_coeffs); // Efficiently swap contents
                           current_poly_actual_degree--;
                        } else { 
                            // Polynomial is already 0. Division keeps it 0.
                            // This state means current_poly_actual_degree can be -1, -2 etc.
                            // p_coeffs should be all zeros if degree is <0
                            fill(p_coeffs.begin(), p_coeffs.end(), 0);
                        }
                    }
                }
                // Normalize degree if it went negative, polynomial 0 has degree usually undefined or -1, for practical purposes 0 is fine for array access if it means coeff[0] could be non-zero.
                // If current_poly_actual_degree becomes < 0, it implies the polynomial is identically zero.
                // For safety, if it's < 0, all its coefficients should be zero.
                 if(current_poly_actual_degree < 0) {
                    fill(p_coeffs.begin(), p_coeffs.begin() + max_coeffs_stored + 1, 0);
                 }
            }
        }
        query_results_final.push_back(total_xor_sum);
    }

    for (int i = 0; i < query_results_final.size(); ++i) {
        cout << query_results_final[i] << (i == query_results_final.size() - 1 ? "" : "\n");
    }
    if (!query_results_final.empty()) {
         cout << endl;
    }
    
    return 0;
}
0