結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー qwewe
提出日時 2025-05-14 13:20:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,811 ms / 4,000 ms
コード長 7,689 bytes
コンパイル時間 1,167 ms
コンパイル使用メモリ 76,884 KB
実行使用メモリ 134,500 KB
最終ジャッジ日時 2025-05-14 13:21:28
合計ジャッジ時間 11,576 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // For input/output operations
#include <vector>   // For using std::vector
#include <numeric>  // Potentially useful for numeric algorithms, though not directly used here
#include <cassert>  // For assertions, useful for debugging (can be removed for final submission)

// Use long long for coefficients during calculations to prevent potential integer overflow.
// Intermediate coefficients can become large during FWHT and polynomial multiplication.
using ll = long long;

// Fast Walsh-Hadamard Transform (FWHT) function for XOR convolution.
// This function modifies the input vector P in-place.
// It assumes P.size() is a power of 2.
// This implementation uses integer arithmetic, suitable for the problem's requirement
// of performing sums and products over integers initially.
void fwht(std::vector<ll>& P) {
    int N = P.size(); // Get the size of the vector
    // Base case: If size is 0 or 1, no transformation is needed.
    if (N <= 1) return; 
    
    // Iterative implementation of FWHT
    // 'len' represents half the size of the blocks being merged at each stage.
    for (int len = 1; len < N; len <<= 1) { 
        // 'i' iterates through the starting indices of blocks of size 2*len.
        for (int i = 0; i < N; i += 2 * len) { 
            // 'j' iterates through elements within the first half of the current block.
            for (int j = 0; j < len; j++) { 
                ll u = P[i + j];         // Element from the first half of the block
                ll v = P[i + len + j];   // Corresponding element from the second half
                P[i + j] = u + v;        // Update the element in the first half: sum
                P[i + len + j] = u - v;  // Update the element in the second half: difference
            }
        }
    }
}

// Inverse Fast Walsh-Hadamard Transform (IFWHT) function for XOR convolution.
// This function modifies the input vector P in-place.
// It assumes P.size() is a power of 2.
// This implementation uses integer arithmetic.
void ifwht(std::vector<ll>& P) {
    int N = P.size(); // Get the size of the vector
    // Base case: If size is 0 or 1, no transformation is needed.
    if (N <= 1) return; 
    
    // The inverse FWHT is obtained by applying FWHT again...
    fwht(P); 
    
    // ...and then dividing each element by N.
    // Using long long for N avoids potential issues if N is large or intermediate P[i] values are large.
    ll N_ll = N; 
    for (int i = 0; i < N; ++i) {
        // For debugging: Check if P[i] is divisible by N. This should always hold true for valid inputs and correct implementation.
        // assert(P[i] % N_ll == 0); 
        P[i] /= N_ll; // Perform integer division by N
    }
}


int main() {
    // Enable fast standard input/output operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Read the parameter n from input
    std::cin >> n;
    int N = 1 << n; // Calculate N = 2^n

    // Store the input polynomials A_i and B_i. To process efficiently column-wise with FWHT,
    // we store them in a transposed format.
    // A_T[p][i] will store the coefficient of x^p in the polynomial A_i. Dimensions: 32 rows x N columns.
    std::vector<std::vector<ll>> A_T(32, std::vector<ll>(N));
    for (int i = 0; i < N; ++i) { // Iterate over polynomial index i (0 to N-1)
        for (int j = 0; j < 32; ++j) { // Iterate over coefficient degree j (0 to 31)
            std::cin >> A_T[j][i]; // Read the coefficient a_{i,j} and store it at A_T[j][i]
        }
    }
    
    // B_T[q][i] will store the coefficient of x^q in the polynomial B_i. Dimensions: 32 rows x N columns.
    std::vector<std::vector<ll>> B_T(32, std::vector<ll>(N));
    for (int i = 0; i < N; ++i) { // Iterate over polynomial index i (0 to N-1)
        for (int j = 0; j < 32; ++j) { // Iterate over coefficient degree j (0 to 31)
            std::cin >> B_T[j][i]; // Read the coefficient b_{i,j} and store it at B_T[j][i]
        }
    }

    // Apply FWHT to each column p of the original matrix A (which corresponds to row p of A_T).
    // After this loop, A_T[p] contains the FWHT transform of the sequence (a_{0,p}, a_{1,p}, ..., a_{N-1,p}).
    for(int p = 0; p < 32; ++p) {
        fwht(A_T[p]); 
    }
    
    // Apply FWHT to each column q of the original matrix B (which corresponds to row q of B_T).
    // After this loop, B_T[q] contains the FWHT transform of the sequence (b_{0,q}, b_{1,q}, ..., b_{N-1,q}).
    for(int q = 0; q < 32; ++q) {
        fwht(B_T[q]); 
    }
    
    // Compute the element-wise polynomial products in the transformed domain.
    // The product of two polynomials of degree 31 can have degree up to 62.
    // We need 63 coefficients (for degrees 0 to 62).
    // Store the transformed result C_hat also in transposed format:
    // C_hat_T[r][k] will store the coefficient of x^r in the transformed polynomial C_hat_k. Dimensions: 63 rows x N columns.
    std::vector<std::vector<ll>> C_hat_T(63, std::vector<ll>(N, 0)); // Initialize with zeros
    
    // Iterate over the transformed index k (from 0 to N-1).
    for (int k = 0; k < N; ++k) { 
        // For each k, compute the product of the transformed polynomials: A_hat_k(x) * B_hat_k(x).
        // The coefficients of A_hat_k(x) are A_T[p][k] for p = 0..31.
        // The coefficients of B_hat_k(x) are B_T[q][k] for q = 0..31.
        for (int p = 0; p < 32; ++p) { // Iterate through coefficients of A_hat_k
            ll A_kp = A_T[p][k]; // Get coefficient of x^p in A_hat_k
            // Optimization: If A_kp is zero, the product A_kp * B_kq will be zero for all q, so skip the inner loop.
            if (A_kp == 0) continue; 
            
            for (int q = 0; q < 32; ++q) { // Iterate through coefficients of B_hat_k
                ll B_kq = B_T[q][k]; // Get coefficient of x^q in B_hat_k
                // If B_kq is zero, the product is zero, contributing nothing. No explicit check needed inside the loop.
                
                // The product A_kp * B_kq contributes to the coefficient of x^(p+q) in the resulting polynomial C_hat_k.
                // Add this contribution to the appropriate entry in C_hat_T.
                C_hat_T[p + q][k] += A_kp * B_kq; 
            }
        }
    }

    // Apply Inverse FWHT to each column r of C_hat (which corresponds to row r of C_hat_T).
    // After this loop, C_hat_T[r][k] will store the final coefficient C[k][r] (coefficient of x^r in C_k).
    for (int r = 0; r < 63; ++r) {
        ifwht(C_hat_T[r]); 
    }

    // Output the resulting polynomials C_k. The final step is to take coefficients modulo 2.
    // The coefficient C[i][j] (coefficient of x^j in polynomial C_i) is stored in C_hat_T[j][i].
    for (int i = 0; i < N; ++i) { // Iterate over the original polynomial index i (this determines the output row)
        for (int j = 0; j < 63; ++j) { // Iterate over the polynomial degree j (this determines the output column)
            ll val = C_hat_T[j][i]; // Retrieve the final coefficient C[i][j]
            
            // Compute the coefficient modulo 2. 
            // The expression `(val % 2 + 2) % 2` correctly handles potential negative results from subtraction during FWHT, ensuring a 0 or 1 result.
            ll result_bit = (val % 2 + 2) % 2; 
            
            // Print the resulting bit (0 or 1). Add a space separator, except after the last coefficient.
            std::cout << result_bit << (j == 62 ? "" : " "); 
        }
        std::cout << "\n"; // Print a newline character after outputting all coefficients for polynomial C_i
    }

    return 0; // Indicate successful program execution
}
0