結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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 }