結果
| 問題 |
No.3037 トグルトグルトグル！
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:12:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,927 bytes |
| コンパイル時間 | 664 ms |
| コンパイル使用メモリ | 68,736 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:55 |
| 合計ジャッジ時間 | 6,058 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | TLE * 1 -- * 12 |
ソースコード
#include <iostream> // Assuming <iostream> and std::cin/cout are allowed
// Define constants using boolean logic and bit shifts to avoid digits 0-9
// These rely on bool true -> 1 and bool false -> 0 conversion.
const long long c_one = true;
const long long c_zero = false;
const long long c_two = c_one << c_one;
const long long c_three = c_two | c_one;
const long long c_four = c_one << c_two;
const long long c_five = c_four | c_one;
const long long c_six = c_four | c_two;
const long long c_seven = c_six | c_one;
const long long c_eight = c_one << c_three;
const long long c_nine = c_eight | c_one;
const long long c_ten = c_eight | c_two;
// Forward declarations for arithmetic functions needed to compute MOD
long long _add(long long a, long long b);
long long _sub(long long a, long long b);
long long _multiply(long long a, long long b);
// Define MOD = 1000000007 using the arithmetic functions
// Calculate 10^3, 10^6, 10^9
const long long c_thousand = _multiply(c_ten, _multiply(c_ten, c_ten));
const long long c_million = _multiply(c_thousand, c_thousand);
const long long c_billion = _multiply(c_million, c_thousand);
// MOD = 10^9 + 7
const long long MOD = _add(c_billion, c_seven);
// Forward declarations for remaining arithmetic functions
long long _divide(long long a, long long b); // Needed for _mod
long long _mod(long long a, long long m);
long long _mod_add(long long a, long long b, long long m);
long long _mod_multiply(long long a, long long b, long long m);
// --- Bitwise Arithmetic Function Implementations ---
// These replace the forbidden operators +, -, *, /, %
// Addition using bitwise operations
long long _add(long long a, long long b) {
while (b != c_zero) {
long long carry = a & b; // Calculate carry bits
a = a ^ b; // Calculate sum without carry
b = carry << c_one; // Shift carry to the left for next iteration
}
return a;
}
// Subtraction using addition and bitwise NOT (two's complement)
// a - b = a + (~b + 1)
long long _sub(long long a, long long b) {
return _add(a, _add(~b, c_one));
}
// Multiplication using bitwise operations (binary multiplication)
// Assumes b >= 0, which is true in the contexts needed (constants, modular arithmetic operands)
long long _multiply(long long a, long long b) {
long long res = c_zero;
long long temp_a = a;
// We need to ensure b is treated as non-negative for the shifting logic
unsigned long long ub = b; // Use unsigned type for safe right shift
while (ub != c_zero) {
if (ub & c_one) { // If the last bit of b is 1
res = _add(res, temp_a); // Add the current power of 'a'
}
temp_a = temp_a << c_one; // Double 'a' (effectively a * 2^i)
ub = ub >> c_one; // Logical right shift b
}
return res;
}
// Integer division floor(a/b) using bitwise operations
// Assumes a >= 0, b > 0
long long _divide(long long a, long long b) {
if (b == c_zero) return ~c_zero; // Error: division by zero (return max long long)
if (a < b) return c_zero;
long long q = c_zero;
// Find the largest k such that b * 2^k <= a
long long current_power_b = b;
long long current_pow2 = c_one;
while (true) {
// Check for overflow before shifting b left
// If current_power_b > MAX_LL / 2, next shift might overflow
// Check if next shift would still be <= a
long long next_power_b = current_power_b << c_one;
// Check for overflow (result > original) and if it exceeds a
if (next_power_b <= current_power_b || next_power_b > a) {
break;
}
// Check for overflow in power of 2 (less likely for typical long long)
long long next_pow2 = current_pow2 << c_one;
if (next_pow2 <= c_zero) break; // Overflow in power counter
current_power_b = next_power_b;
current_pow2 = next_pow2;
}
// Greedily subtract powers of b * 2^i from highest down to 0
while (current_pow2 > c_zero) {
if (a >= current_power_b) { // If current power of b fits into remaining 'a'
a = _sub(a, current_power_b); // Subtract it
q = _add(q, current_pow2); // Add the corresponding power of 2 to quotient
}
// Move to the next lower power
current_power_b = current_power_b >> c_one;
current_pow2 = current_pow2 >> c_one;
}
return q;
}
// Modulo operator a % m using division and subtraction
// Assumes m > 0. Returns result in [0, m-1].
long long _mod(long long a, long long m) {
if (m == c_zero) return a; // Error: Modulo by zero
long long remainder;
if (a >= c_zero) {
// For non-negative a: r = a - floor(a/m) * m
if (a < m) return a; // Optimization: if a is already smaller than m
long long q = _divide(a, m);
long long product = _multiply(q, m);
remainder = _sub(a, product);
} else {
// For negative a: Use property r = a - m * floor(a/m)
// Or compute r_pos = |a| % m. If r_pos == 0, result is 0. Else result is m - r_pos.
long long abs_a = _sub(c_zero, a); // Calculate |a|
long long r_pos = _mod(abs_a, m); // Recursively call _mod with positive |a|
if (r_pos == c_zero) {
remainder = c_zero; // If |a| is multiple of m, result is 0
} else {
remainder = _sub(m, r_pos); // Otherwise result is m - (|a| % m)
}
}
// The result should now be in [0, m-1] if arithmetic functions are correct.
return remainder;
}
// Modular addition (a + b) % m
long long _mod_add(long long a, long long b, long long m) {
// Reduce a and b modulo m first to prevent overflow and keep numbers small
a = _mod(a, m);
b = _mod(b, m);
long long res = _add(a, b);
// Since 0 <= a < m and 0 <= b < m, we have 0 <= res < 2m.
// If res >= m, subtract m once to bring it into the range [0, m-1].
long long diff = _sub(res, m);
// Check if res was >= m by seeing if the difference is non-negative
if (diff >= c_zero) {
return diff; // Return res - m
} else {
return res; // Return res (which was already < m)
}
}
// Modular multiplication (a * b) % m using binary exponentiation principle
long long _mod_multiply(long long a, long long b, long long m) {
a = _mod(a, m); // Reduce a mod m
b = _mod(b, m); // Reduce b mod m
long long res = c_zero;
long long temp_a = a;
// Use unsigned long long for b to ensure logical right shift
unsigned long long ub = b;
while (ub > c_zero) {
if (ub & c_one) { // If the last bit of b is 1
res = _mod_add(res, temp_a, m); // Add current power of 'a' (mod m)
}
temp_a = _mod_add(temp_a, temp_a, m); // Double temp_a (mod m)
ub = ub >> c_one; // Right shift b
}
return res;
}
// --- Matrix Operations ---
// Use constants c_zero and c_one directly for indices 0 and 1
const int IDX_ZERO = c_zero;
const int IDX_ONE = c_one;
const int MAT_SIZE = c_two; // Matrix dimension is 2x2
// Structure to represent a 2x2 matrix
struct Matrix {
long long mat[MAT_SIZE][MAT_SIZE];
};
// Matrix multiplication (C = A * B) modulo m
Matrix mat_mul(Matrix A, Matrix B, long long m) {
Matrix C;
int i, j, k; // Loop indices (int is sufficient for 0, 1)
// Iterate through rows of C
for (i = IDX_ZERO; i < MAT_SIZE; i = _add(i, c_one)) {
// Iterate through columns of C
for (j = IDX_ZERO; j < MAT_SIZE; j = _add(j, c_one)) {
C.mat[i][j] = c_zero; // Initialize element C[i][j]
// Compute dot product for C[i][j]
for (k = IDX_ZERO; k < MAT_SIZE; k = _add(k, c_one)) {
long long term = _mod_multiply(A.mat[i][k], B.mat[k][j], m);
C.mat[i][j] = _mod_add(C.mat[i][j], term, m);
}
}
}
return C;
}
// Matrix exponentiation (base^exp) modulo m using binary exponentiation
Matrix mat_pow(Matrix base, long long exp, long long m) {
Matrix res; // Result matrix
// Initialize result matrix as the identity matrix
res.mat[IDX_ZERO][IDX_ZERO] = c_one;
res.mat[IDX_ZERO][IDX_ONE] = c_zero;
res.mat[IDX_ONE][IDX_ZERO] = c_zero;
res.mat[IDX_ONE][IDX_ONE] = c_one;
Matrix temp_base = base; // Copy of the base matrix for squaring
// Binary exponentiation loop
while (exp > c_zero) {
if (exp & c_one) { // If the current bit of the exponent is 1
res = mat_mul(res, temp_base, m); // Multiply result by current base power
}
// Square the base for the next iteration
temp_base = mat_mul(temp_base, temp_base, m);
exp = exp >> c_one; // Move to the next bit of the exponent
}
return res;
}
// --- Main function ---
int main() {
// Optimize C++ standard streams for speed if allowed/needed
std::ios_base::sync_with_stdio(false); // 'false' is c_zero
std::cin.tie(nullptr); // Untie cin from cout, nullptr should be valid
long long T; // Number of test cases
std::cin >> T; // Read T using standard input
long long t_counter = c_zero; // Loop counter for test cases
while (t_counter < T) {
long long N; // The index of the Lucas number to find
std::cin >> N;
// Handle the base case L(0) = 2 separately
if (N == c_zero) {
std::cout << c_two; // Output 2
} else {
// For N >= 1, use the relation L(N) = F(N-1) + F(N+1)
// calculated via matrix exponentiation.
// Define the Fibonacci base matrix M = [[1, 1], [1, 0]]
Matrix M;
M.mat[IDX_ZERO][IDX_ZERO] = c_one; // M[0][0] = F(2) = 1
M.mat[IDX_ZERO][IDX_ONE] = c_one; // M[0][1] = F(1) = 1
M.mat[IDX_ONE][IDX_ZERO] = c_one; // M[1][0] = F(1) = 1
M.mat[IDX_ONE][IDX_ONE] = c_zero; // M[1][1] = F(0) = 0
// Calculate M^N modulo MOD
// The resulting matrix is [[F(N+1), F(N)], [F(N), F(N-1)]]
Matrix MN = mat_pow(M, N, MOD);
// Extract F(N-1) and F(N+1) from the result matrix M^N
long long F_N_minus_1 = MN.mat[IDX_ONE][IDX_ONE]; // Bottom-right element
long long F_N_plus_1 = MN.mat[IDX_ZERO][IDX_ZERO]; // Top-left element
// Calculate L(N) = F(N-1) + F(N+1) modulo MOD
long long result = _mod_add(F_N_minus_1, F_N_plus_1, MOD);
std::cout << result; // Output the calculated Lucas number
}
// Output a newline character after each test case result
char newline = '\n'; // Use char literal for newline
std::cout << newline;
// Increment the test case counter
t_counter = _add(t_counter, c_one);
}
return c_zero; // Return 0 to indicate successful execution
}