結果
| 問題 |
No.896 友達以上恋人未満
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 815 ms / 3,500 ms |
| コード長 | 8,540 bytes |
| コンパイル時間 | 1,435 ms |
| コンパイル使用メモリ | 96,228 KB |
| 実行使用メモリ | 155,008 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:41 |
| 合計ジャッジ時間 | 4,185 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 7 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:25:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
25 | scanf("%d %d %u %u %u %u %d", &M, &N, &mulX, &addX, &mulY, &addY, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:48:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
48 | for (int i = 1; i <= M; ++i) scanf("%u", &X[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:49:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
49 | for (int i = 1; i <= M; ++i) scanf("%u", &Y[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:50:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
50 | for (int i = 1; i <= M; ++i) scanf("%u", &A[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:51:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
51 | for (int i = 1; i <= M; ++i) scanf("%u", &B[i]);
| ~~~~~^~~~~~~~~~~~~
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdio> // Using C standard I/O for speed
#include <new> // For std::bad_alloc
#include <cmath> // For log function (used in reserve estimation)
#include <algorithm> // For std::max
// Define global variables
// Use pointers for large arrays to manage memory explicitly
unsigned long long* z = nullptr; // Array to store eel counts and later transformed sums
bool* is_prime = nullptr; // Array for Sieve of Eratosthenes
int MOD; // Modulus for calculations, guaranteed to be power of 2
int main() {
// Use faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int M; // Number of initial values provided directly
int N; // Total number of rabbits and eel types
unsigned int mulX, addX, mulY, addY; // Parameters for generating sequences
// Read initial parameters
scanf("%d %d %u %u %u %u %d", &M, &N, &mulX, &addX, &mulY, &addY, &MOD);
// Basic validation for MOD
if (MOD <= 0) {
// fprintf(stderr, "MOD must be positive.\n"); // Comment out error messages for final submission
return 1;
}
// Allocate memory for z array (size MOD). Use unsigned long long for counts potentially exceeding 2^32.
try {
z = new unsigned long long[MOD];
} catch (const std::bad_alloc& e) {
// fprintf(stderr, "Memory allocation for z failed: %s\n", e.what()); // Comment out error messages
return 1;
}
// Initialize z array to 0
for(int i = 0; i < MOD; ++i) {
z[i] = 0;
}
// Store initial M values (X_i, Y_i, A_i, B_i) using vectors
std::vector<unsigned int> X(M + 1), Y(M + 1), A(M + 1), B(M + 1);
// Read M values for X, Y, A, B sequences
for (int i = 1; i <= M; ++i) scanf("%u", &X[i]);
for (int i = 1; i <= M; ++i) scanf("%u", &Y[i]);
for (int i = 1; i <= M; ++i) scanf("%u", &A[i]);
for (int i = 1; i <= M; ++i) scanf("%u", &B[i]);
// --- Step 1: Generate x_i, y_i sequences and compute initial eel counts z[k] ---
unsigned int current_x = 0, current_y = 0;
// Initialize generation state using the M-th values if M > 0
if (M > 0) {
current_x = X[M];
current_y = Y[M];
} // Constraint M >= 1 ensures this is safe.
// Aggregate counts for the first M eels
for (int i = 1; i <= M; ++i) {
// Check index bounds based on constraints 0 <= X_i < MOD
if (X[i] < MOD) {
z[X[i]] += Y[i];
}
// else { fprintf(stderr, "Warning: X[%d] = %u is out of bounds [0, %d)\n", i, X[i], MOD); } // Comment out error messages
}
// Use bitwise AND for fast modulo operation since MOD is power of 2
unsigned int MOD_mask = MOD - 1;
// Generate remaining values for i = M+1 to N and update counts
for (int i = M + 1; i <= N; ++i) {
// Use unsigned long long for intermediate calculations to prevent overflow
current_x = (unsigned int)((1ULL * current_x * mulX + addX) & MOD_mask);
current_y = (unsigned int)((1ULL * current_y * mulY + addY) & MOD_mask);
// current_x is guaranteed to be < MOD due to the mask
z[current_x] += current_y;
}
// --- Step 2: Compute Sum-over-Multiples using Sieve and Transform ---
// Allocate memory for the sieve array
try {
is_prime = new bool[MOD];
} catch (const std::bad_alloc& e) {
// fprintf(stderr, "Memory allocation for is_prime failed: %s\n", e.what()); // Comment out error messages
delete[] z; z = nullptr; // Clean up previously allocated memory
return 1;
}
// Initialize sieve array
for(int i=0; i<MOD; ++i) is_prime[i] = true;
// 0 and 1 are not prime
if (MOD > 0) is_prime[0] = false;
if (MOD > 1) is_prime[1] = false;
// Standard Sieve of Eratosthenes algorithm
// Iterate up to sqrt(MOD)
for (int p = 2; (unsigned long long)p * p < MOD; ++p) {
if (is_prime[p]) {
// Mark multiples of p starting from p*p
for (int k = p * p; k < MOD; k += p) {
is_prime[k] = false;
}
}
}
// Collect primes found by the sieve
std::vector<int> primes;
// Estimate number of primes and reserve space in vector to potentially improve performance
// A simple heuristic: reserve roughly MOD/10 space
primes.reserve(MOD / 10 + 1);
for (int p = 2; p < MOD; ++p) {
if (is_prime[p]) {
primes.push_back(p);
}
}
delete[] is_prime; // Sieve array no longer needed, free memory
is_prime = nullptr;
// Perform the sum-over-multiples transform in-place on z array.
// After this step, z[p] for p >= 1 will store S'(p) = sum_{k: p|k, 1<=k<MOD} z_k (using original z_k values)
// z[0] remains unchanged, storing the initial count z_0.
for (int p : primes) {
// Iterate `i` from largest multiple index down to 1
// Integer division ensures i*p <= MOD-1
for (int i = (MOD - 1) / p; i >= 1; --i) {
// Add the sum from multiple `i*p` to the sum for `i`.
// Since we iterate `i` downwards, z[i*p] already contains the fully computed sum S'(i*p).
z[i] += z[i * p];
}
}
// --- Step 3: Calculate answers C_j for each rabbit and the total XOR sum ---
unsigned long long total_xor_sum = 0; // Stores the XOR sum of all C_j
unsigned long long C_j = 0; // Stores the answer for the current rabbit j
// Process rabbits j=1 to M using the initially provided A_j, B_j values
for (int j = 1; j <= M; ++j) {
unsigned int aj = A[j];
unsigned int bj = B[j];
// Validate aj (constraints guarantee 1 <= aj <= MOD)
// if (aj == 0 || aj > MOD) { // Safety check, could be removed based on trust in constraints
// fprintf(stderr, "Warning: Invalid A[%d]=%u\n", j, aj); // Comment out error messages
// continue;
// }
unsigned long long val_aj = 0; // Stores S'(aj)
// If aj = MOD, its only multiple in [0, MOD-1] is 0. S'(MOD) is effectively 0.
if (aj < MOD) val_aj = z[aj];
unsigned long long val_ajbj = 0; // Stores S'(aj * bj)
// Calculate product using unsigned long long to avoid overflow
unsigned long long prod = 1ULL * aj * bj;
// Calculate C_j based on whether prod is < MOD
if (prod < MOD) {
// Since aj, bj >= 1, prod >= 1. prod is always positive.
val_ajbj = z[prod]; // Access S'(prod) from transformed z array
// Formula when prod < MOD: C_j = S'(aj) - S'(aj*bj)
C_j = val_aj - val_ajbj;
} else { // Case prod >= MOD
// Formula when prod >= MOD: C_j = S'(aj)
C_j = val_aj;
}
// Print C_j for the first M rabbits
printf("%llu\n", C_j);
// Update total XOR sum
total_xor_sum ^= C_j;
}
// Process rabbits j=M+1 to N by regenerating a_j, b_j values
unsigned int current_a = 0, current_b = 0;
// Initialize generation state using the M-th values (if M>0)
if (M > 0) {
current_a = A[M];
current_b = B[M];
} // M >= 1 guaranteed by constraints
for (int j = M + 1; j <= N; ++j) {
// Generate a[j], b[j] using the pseudo-random formulas
// Use unsigned long long for intermediate calculations before mask and +1
current_a = (unsigned int)((1ULL * current_a * mulX + addX + MOD - 1) & MOD_mask) + 1;
current_b = (unsigned int)((1ULL * current_b * mulY + addY + MOD - 1) & MOD_mask) + 1;
unsigned int aj = current_a;
unsigned int bj = current_b;
// Calculate C_j using the same logic as above
unsigned long long val_aj = 0;
if (aj < MOD) val_aj = z[aj];
unsigned long long val_ajbj = 0;
unsigned long long prod = 1ULL * aj * bj;
if (prod < MOD) {
if (prod > 0) val_ajbj = z[prod]; // Check prod > 0, always true since aj, bj >= 1
C_j = val_aj - val_ajbj;
} else { // Case prod >= MOD
C_j = val_aj;
}
// Accumulate XOR sum for rabbits M+1 to N
total_xor_sum ^= C_j;
}
// Print the final total XOR sum
printf("%llu\n", total_xor_sum);
// Clean up dynamically allocated memory
delete[] z;
z = nullptr;
return 0;
}