結果
| 問題 |
No.3036 Nauclhlt型文字列
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:18 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,404 bytes |
| コンパイル時間 | 480 ms |
| コンパイル使用メモリ | 72,044 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:55 |
| 合計ジャッジ時間 | 1,287 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | WA * 15 |
ソースコード
#include <iostream> // Required for input/output operations (cin, cout)
// Use a namespace to group related constants and functions, avoiding global scope pollution.
namespace RestrictedLucas {
// Define constants using sizeof(char) and basic arithmetic operations.
// This avoids using forbidden digit characters.
struct Constants {
// Basic integer constants
static const long long ONE = sizeof(char); // sizeof(char) is guaranteed to be 1
static const long long ZERO = ONE - ONE; // 0
static const long long TWO = ONE + ONE; // 2
static const long long THREE = TWO + ONE; // 3
static const long long FOUR = TWO + TWO; // 4
static const long long FIVE = FOUR + ONE; // 5
static const long long SIX = THREE + THREE; // 6
// static const long long SEVEN = SIX + ONE; // 7 - defined below for P calculation
static const long long EIGHT = FOUR + FOUR; // 8
// static const long long NINE = EIGHT + ONE; // 9 - unused
static const long long TEN = FIVE + FIVE; // 10
// Constant 64 using bit shift (1 << 6)
static const long long SIXTYFOUR = ONE << SIX; // 64
// Constant 63 (used for sign bit check in 64-bit integers)
static const long long SIXTYTHREE = SIXTYFOUR - ONE; // 63
// Newline character (ASCII value 10)
static const char NEWLINE = static_cast<char>(TEN);
// Unsigned constants needed for constructing the large modulus P
static const unsigned long long uONE = sizeof(char);
static const unsigned long long uTWO = uONE + uONE;
static const unsigned long long uFOUR = uTWO + uTWO;
static const unsigned long long uEIGHT = uFOUR + uFOUR;
static const unsigned long long uTEN = uEIGHT + uTWO; // 10
};
// Global variable to store the modulus P = 1000000007
long long P_MOD;
// Helper function for unsigned multiplication without using the '*' operator.
// Uses the binary method (similar to exponentiation by squaring).
unsigned long long multiply_unsigned(unsigned long long a, unsigned long long b) {
unsigned long long res = Constants::ZERO;
// Loop while b is greater than 0
while (b) {
// Check the least significant bit of b
if (b & Constants::uONE) { // If b is odd
res = res + a; // Add a to the result
}
// Double a (equivalent to a * 2)
a = a + a;
// Halve b (integer division, equivalent to b / 2)
b >>= Constants::uONE; // Right shift by 1
}
return res;
}
// Function to initialize the global modulus P_MOD = 1000000007
// Calculates P without using digit characters or forbidden operators.
void initialize_P_MOD() {
// Calculate powers of 10 using multiply_unsigned
const unsigned long long uHUNDRED = multiply_unsigned(Constants::uTEN, Constants::uTEN); // 100
const unsigned long long uTHOUSAND = multiply_unsigned(uHUNDRED, Constants::uTEN); // 1000
const unsigned long long uMILLION = multiply_unsigned(uTHOUSAND, uTHOUSAND); // 1,000,000
const unsigned long long uBILLION = multiply_unsigned(uMILLION, uTHOUSAND); // 1,000,000,000
// Constant 7
const unsigned long long uSEVEN = Constants::uFOUR + Constants::uTWO + Constants::uONE; // 4 + 2 + 1 = 7
// P = 10^9 + 7
P_MOD = static_cast<long long>(uBILLION + uSEVEN); // 1,000,000,007
}
// Utility function to check if a < b without using '<' operator.
// Uses properties of two's complement representation and bit shifts.
// Assumes 64-bit long long.
bool is_less(long long a, long long b) {
long long diff = a - b;
// Check the sign bit (most significant bit).
// Casting to unsigned long long ensures arithmetic right shift is not used on negative values.
// Right shifting by 63 bits isolates the sign bit for a 64-bit integer.
// Result is 1 if diff is negative (a < b), 0 otherwise.
return ((unsigned long long)diff >> Constants::SIXTYTHREE);
}
// Modular addition: computes (a + b) mod P_MOD without using '%' operator.
long long mod_add(long long a, long long b) {
long long res = a + b;
// If the sum is greater than or equal to P_MOD, subtract P_MOD to bring it into range [0, P_MOD-1].
// This works correctly because if a, b are in [0, P_MOD-1], then a+b is in [0, 2*P_MOD-2].
// So at most one subtraction is needed.
if (!is_less(res, P_MOD)) { // Equivalent to: if (res >= P_MOD)
res = res - P_MOD;
}
return res;
}
// Modular subtraction: computes (a - b) mod P_MOD without using '%' operator.
long long mod_sub(long long a, long long b) {
long long res = a - b;
// If the result is negative, add P_MOD to bring it into range [0, P_MOD-1].
if (is_less(res, Constants::ZERO)) { // Equivalent to: if (res < 0)
res = res + P_MOD;
}
return res;
}
// Modular multiplication: computes (a * b) mod P_MOD without using '*' or '%' operators.
// Uses the binary method (also known as Russian peasant multiplication).
long long mod_mul(long long a, long long b) {
long long res = Constants::ZERO;
// Pre-conditions: Assume a and b are non-negative and already within [0, P_MOD-1].
// This holds true within the matrix exponentiation context where results are always kept modulo P_MOD.
// The loop iterates based on the bits of b. Max iterations is the number of bits in b (e.g., 64).
while (b) { // Loop while b is non-zero
if (b & Constants::ONE) { // Check if the last bit of b is 1 (i.e., if b is odd)
res = mod_add(res, a); // Add a to the result (modulo P_MOD)
}
// Double a (modulo P_MOD). Equivalent to a = (a * 2) % P_MOD
a = mod_add(a, a);
// Halve b (integer division). Equivalent to b = b / 2
b >>= Constants::ONE;
}
return res;
}
// Structure to represent a 2x2 matrix.
struct Matrix {
// The dimension of the matrix (2). Uses sizeof(short), assuming it is 2.
// This is a common assumption in competitive programming environments.
static const int _DIM = sizeof(short);
long long mat[_DIM][_DIM]; // 2x2 matrix storage
// Default constructor
Matrix() {}
// Matrix multiplication: Computes C = this * other (mod P_MOD).
Matrix multiply(Matrix other) {
Matrix result;
int i = Constants::ZERO;
// Loop through rows of the result matrix
while (is_less(i, _DIM)) { // Equivalent to: for(int i = 0; i < _DIM; ++i)
int j = Constants::ZERO;
// Loop through columns of the result matrix
while (is_less(j, _DIM)) { // Equivalent to: for(int j = 0; j < _DIM; ++j)
result.mat[i][j] = Constants::ZERO; // Initialize element to 0
int k = Constants::ZERO;
// Inner loop for dot product calculation
while (is_less(k, _DIM)) { // Equivalent to: for(int k = 0; k < _DIM; ++k)
// Compute term this->mat[i][k] * other.mat[k][j] (mod P_MOD)
long long term = mod_mul(mat[i][k], other.mat[k][j]);
// Add the term to the result element (mod P_MOD)
result.mat[i][j] = mod_add(result.mat[i][j], term);
// Increment inner loop counter
k = k + Constants::ONE; // k++
}
// Increment column loop counter
j = j + Constants::ONE; // j++
}
// Increment row loop counter
i = i + Constants::ONE; // i++
}
return result;
}
};
// Matrix exponentiation: Computes base^exp (mod P_MOD) using exponentiation by squaring.
Matrix matrix_pow(Matrix base, long long exp) {
Matrix result;
// Initialize result matrix to the identity matrix [[1, 0], [0, 1]]
result.mat[Constants::ZERO][Constants::ZERO] = Constants::ONE;
result.mat[Constants::ZERO][Constants::ONE] = Constants::ZERO;
result.mat[Constants::ONE][Constants::ZERO] = Constants::ZERO;
result.mat[Constants::ONE][Constants::ONE] = Constants::ONE;
// Perform exponentiation by squaring
while (exp) { // Loop while exponent is greater than 0
if (exp & Constants::ONE) { // If the current exponent bit is 1 (i.e., exp is odd)
// Multiply result by the current base power: result = result * base
result = result.multiply(base);
}
// Square the base: base = base * base
base = base.multiply(base);
// Halve the exponent (integer division): exp = exp / 2
exp >>= Constants::ONE;
}
return result; // Return the final computed matrix power
}
} // namespace RestrictedLucas
// Main function - entry point of the program
int main() {
// Initialize the global modulus P_MOD = 1000000007
RestrictedLucas::initialize_P_MOD();
// Optimize standard input/output operations by disabling synchronization with C stdio
std::ios_base::sync_with_stdio(false);
// Note: Untie cin from cout (cin.tie(nullptr)) is usually done too, but omitted here for simplicity
// as `nullptr` might require headers or features potentially problematic under constraints.
int T; // Variable to store the number of test cases
std::cin >> T; // Read the number of test cases
int t_count = RestrictedLucas::Constants::ZERO; // Initialize test case counter
// Loop T times to process each test case
while (RestrictedLucas::is_less(t_count, T)) { // Equivalent to: for(t_count=0; t_count < T; ++t_count)
long long N; // Variable to store the input index N for the Lucas sequence
std::cin >> N; // Read N for the current test case
// Define the base matrix M = [[1, 1], [1, 0]]
// This matrix represents the linear recurrence relation L(k+2) = L(k+1) + L(k)
RestrictedLucas::Matrix M;
M.mat[RestrictedLucas::Constants::ZERO][RestrictedLucas::Constants::ZERO] = RestrictedLucas::Constants::ONE;
M.mat[RestrictedLucas::Constants::ZERO][RestrictedLucas::Constants::ONE] = RestrictedLucas::Constants::ONE;
M.mat[RestrictedLucas::Constants::ONE][RestrictedLucas::Constants::ZERO] = RestrictedLucas::Constants::ONE;
M.mat[RestrictedLucas::Constants::ONE][RestrictedLucas::Constants::ONE] = RestrictedLucas::Constants::ZERO;
// Compute M^N using matrix exponentiation. This takes O(log N) matrix multiplications.
RestrictedLucas::Matrix MN = RestrictedLucas::matrix_pow(M, N);
// The N-th Lucas number L(N) can be found using the identity L(N) = F(N-1) + F(N+1),
// where F are Fibonacci numbers.
// It is also known that L(N) = trace(M^N), where trace is the sum of diagonal elements.
// The computed matrix MN = [[F(N+1), F(N)], [F(N), F(N-1)]].
// So, trace(MN) = F(N+1) + F(N-1).
long long LN = RestrictedLucas::mod_add(MN.mat[RestrictedLucas::Constants::ZERO][RestrictedLucas::Constants::ZERO], MN.mat[RestrictedLucas::Constants::ONE][RestrictedLucas::Constants::ONE]);
// Output the computed N-th Lucas number (modulo P_MOD) followed by a newline character.
std::cout << LN << RestrictedLucas::Constants::NEWLINE;
// Increment the test case counter
t_count = t_count + RestrictedLucas::Constants::ONE;
}
// Return 0 to indicate successful program execution.
return RestrictedLucas::Constants::ZERO;
}