結果

問題 No.510 二次漸化式
ユーザー qwewe
提出日時 2025-05-14 13:01:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 164 ms / 3,000 ms
コード長 9,978 bytes
コンパイル時間 773 ms
コンパイル使用メモリ 81,884 KB
実行使用メモリ 37,608 KB
最終ジャッジ日時 2025-05-14 13:03:26
合計ジャッジ時間 7,128 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <vector>
#include <string>

// Use standard namespace
using namespace std;

// Define the modulo constant
const long long MOD = 1e9 + 7;

// Modular multiplication helper function
// Ensures result is within [0, MOD-1] and handles potential overflow with long long
long long mul(long long a, long long b) {
    // Use 1LL to promote operands to long long before multiplication
    return (1LL * a * b) % MOD;
}

// Matrix structure definition
struct Matrix {
    long long mat[4][4]; // 4x4 matrix to store transformation state

    // Default constructor initializes matrix to all zeros
    Matrix() {
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                mat[i][j] = 0;
            }
        }
    }

    // Static function to return an identity matrix
    static Matrix identity() {
        Matrix I;
        for (int i = 0; i < 4; ++i) {
            I.mat[i][i] = 1; // Diagonal elements are 1
        }
        return I;
    }

    // Overload the multiplication operator for matrix multiplication
    // result = this * other
    Matrix operator*(const Matrix& other) const {
        Matrix result; // Initialize result matrix to zeros
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                // Compute element result.mat[i][j]
                long long current_sum = 0;
                for (int k = 0; k < 4; ++k) {
                    // Perform multiplication and addition modulo MOD
                    // Use 1LL to ensure intermediate products are computed using long long
                    current_sum = (current_sum + mul(mat[i][k], other.mat[k][j])) % MOD;
                }
                // Ensure the final result for the element is non-negative
                result.mat[i][j] = (current_sum % MOD + MOD) % MOD; 
            }
        }
        return result;
    }
};

// Global variables
int N; // Problem parameter N: number of steps in recurrence
vector<long long> x_val, y_val; // Store current values of parameters x_i and y_i
vector<Matrix> tree; // Segment tree storing matrix products
int seg_tree_base_size; // Base size (number of leaves) for the segment tree, power of 2 >= N

// Function to compute the transformation matrix T_k for index k
// based on current values of x_k and y_k
Matrix compute_T(int k) {
    Matrix T; // Initialize matrix T to zeros
    // If index k is out of the valid range [0, N-1], treat parameters as 0.
    // This handles leaves in the segment tree that correspond to indices >= N.
    long long xk = (k >= 0 && k < N) ? x_val[k] : 0; 
    long long yk = (k >= 0 && k < N) ? y_val[k] : 0; 

    // Precompute y_k^2 and 2*y_k modulo MOD
    long long yk_sq = mul(yk, yk);
    long long two_yk = mul(2, yk);

    // Define the transformation matrix T_k based on the recurrence relations
    // T_k transforms state vector V_k to V_{k+1}
    // V_k = (a_k, b_k^2, b_k, 1)^T
    // V_{k+1} = T_k * V_k
    /* T_k =  ( 1  x_k   0   0 )
              ( 0 yk^2 2yk   1 )
              ( 0   0   yk   1 )
              ( 0   0    0   1 ) */
    T.mat[0][0] = 1; T.mat[0][1] = xk;       T.mat[0][2] = 0; T.mat[0][3] = 0;
    T.mat[1][0] = 0; T.mat[1][1] = yk_sq;   T.mat[1][2] = two_yk; T.mat[1][3] = 1;
    T.mat[2][0] = 0; T.mat[2][1] = 0;       T.mat[2][2] = yk;     T.mat[2][3] = 1;
    T.mat[3][0] = 0; T.mat[3][1] = 0;       T.mat[3][2] = 0;      T.mat[3][3] = 1;
    return T;
}

// Merge operation for segment tree nodes.
// Combines results from left child (range L..M) and right child (range M+1..R)
// The product for node representing range L..R is T_R * ... * T_L
// This is computed as (T_R * ... * T_{M+1}) * (T_M * ... * T_L) = right_child_matrix * left_child_matrix
Matrix merge(const Matrix& left, const Matrix& right) {
    return right * left; // Matrix multiplication is associative but not commutative, order matters
}

// Build the segment tree recursively
// Node 'node' covers range [start, end]
void build(int node, int start, int end) {
    if (start == end) {
        // Leaf node: store the base matrix T_start
        tree[node] = compute_T(start);
    } else {
        // Internal node: recursively build children and merge results
        int mid = start + (end - start) / 2; // Find midpoint
        build(2 * node, start, mid); // Build left child
        build(2 * node + 1, mid + 1, end); // Build right child
        // Merge results from children
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }
}

// Update the segment tree after a parameter at index 'idx' changes
// Node 'node' covers range [start, end]
void update(int node, int start, int end, int idx) {
    if (start == end) {
        // Leaf node corresponding to index 'idx': recompute T_idx
        tree[node] = compute_T(idx);
    } else {
        // Internal node: determine which child contains 'idx' and recurse
        int mid = start + (end - start) / 2;
        if (start <= idx && idx <= mid) {
            // Update is in the left subtree
            update(2 * node, start, mid, idx);
        } else {
            // Update is in the right subtree
            update(2 * node + 1, mid + 1, end, idx);
        }
        // After child update, recompute the merged matrix for the current node
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }
}

// Query the segment tree for the product matrix over a given range [l, r]
// Node 'node' covers range [start, end]
Matrix query(int node, int start, int end, int l, int r) {
    // Base cases for recursion termination
    // If query range [l, r] is empty or invalid
    if (l > r) {
         return Matrix::identity(); // Return identity matrix for empty product
    }
    // If the current node's range [start, end] is completely outside the query range [l, r]
    if (r < start || end < l) {
        return Matrix::identity(); // Return identity matrix, contributes nothing to product
    }
    // If the current node's range is fully contained within the query range
    if (l <= start && end <= r) {
        return tree[node]; // Return the precomputed matrix for this node
    }
    
    // Recursive case: current node's range partially overlaps query range
    int mid = start + (end - start) / 2; // Find midpoint
    // Query left and right children for the parts of [l, r] they cover
    Matrix p1 = query(2 * node, start, mid, l, r); 
    Matrix p2 = query(2 * node + 1, mid + 1, end, l, r);
    
    // Combine results from children. Product = P_right * P_left
    return merge(p1, p2);
}

// Utility function to determine the segment tree base size (number of leaves)
// Finds the smallest power of 2 greater than or equal to n
int get_seg_tree_base_size(int n) {
    int size = 1;
    if (n == 0) return 1; // Handle edge case n=0
    while (size < n) {
        size <<= 1; // Double the size until it's >= n
    }
    return size; 
}


int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int Q; // Number of queries
    cin >> N >> Q; // Read problem parameters N and Q

    // Initialize storage for parameter values x_i and y_i
    x_val.resize(N, 0); 
    y_val.resize(N, 0); 
    
    // Calculate required segment tree base size
    seg_tree_base_size = get_seg_tree_base_size(N);
    // Resize segment tree vector. Total nodes = 2 * base_size. Use 1-based indexing for nodes.
    tree.resize(2 * seg_tree_base_size); 

    // Build the initial segment tree. It covers indices [0, seg_tree_base_size - 1].
    // Leaves corresponding to indices >= N will correctly use default values (x_k=0, y_k=0).
    build(1, 0, seg_tree_base_size - 1);

    // Process Q queries
    for (int k = 0; k < Q; ++k) {
        char type; // Query type: 'x', 'y', or 'a'
        cin >> type;
        if (type == 'x') {
            int i; // Index to update
            long long v; // New value
            cin >> i >> v;
            // Check if index 'i' is within valid bounds [0, N-1]
            if (i >= 0 && i < N) { 
                 x_val[i] = v; // Update the stored value
                 // Update the segment tree at index 'i'
                 update(1, 0, seg_tree_base_size - 1, i);
            }
        } else if (type == 'y') {
            int i; // Index to update
            long long v; // New value
            cin >> i >> v;
             // Check if index 'i' is within valid bounds [0, N-1]
             if (i >= 0 && i < N) {
                 y_val[i] = v; // Update the stored value
                 // Update the segment tree at index 'i'
                 update(1, 0, seg_tree_base_size - 1, i);
             }
        } else { // type == 'a'
            int i; // Index to query: compute a_i
            cin >> i;
            // Handle base case a_0 = 1 directly
            if (i == 0) {
                cout << 1 << "\n";
            } 
            // Handle i > 0 case using segment tree query
            else if (i > 0) {
                // Compute a_i requires the product matrix P_i = T_{i-1} * ... * T_0
                // Query the segment tree for the product over range [0, i-1]
                Matrix P = query(1, 0, seg_tree_base_size - 1, 0, i - 1);
                
                // Calculate final state vector V_i = P * V_0 where V_0 = (1, 1, 1, 1)^T
                // The value a_i is the first component of V_i
                // a_i = P.mat[0][0]*1 + P.mat[0][1]*1 + P.mat[0][2]*1 + P.mat[0][3]*1
                long long a_i = (P.mat[0][0] + P.mat[0][1] + P.mat[0][2] + P.mat[0][3]) % MOD;
                
                // Ensure the final result is non-negative modulo MOD
                if (a_i < 0) a_i += MOD; 
                cout << a_i << "\n";
            }
            // Note: Problem constraints state 0 <= i <= N. The code handles this range correctly.
            // Querying a_N involves range [0, N-1], which is valid.
        }
    }

    return 0; // Indicate successful execution
}
0