結果
| 問題 |
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 |
ソースコード
#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
}