問題 1：数論的和の計算
この問題では、大きな指数を持つべき乗の和を特定の素数で割った余りを求める必要がある。 naive な快速幂を用いた計算では $O(\sqrt{m} \cdot \log n)$ となり、制限時間を超えてしまう。ここで、法となる数が小さくかつ素数であることに注目する。
フェルマの小定理より、指数部分は法 $p$ に対して $p-1$ で割った余りとして扱ってよい。これにより指数を事前に削減し、べき乗の値をテーブルに预处理しておくことで、計算量を $O(p \cdot \log n + \sqrt{m})$ まで落とすことができる。また、整数 $n$ は非常に大きいため、文字列として読み込みながら剰余演算を行う処理が必要となる。
最終的な和の計算には、値 $\lfloor m/i \rfloor$ が一定となる区間をまとめる「整数値ブロッキング（整除分块）」の技法を適用する。
実装コード（問題 1）
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using int64 = long long;
const int MOD = 10007;
// 快速幂による modular exponentiation
int64 mod_pow(int64 base, int64 exp) {
int64 res = 1;
base %= MOD;
while (exp > 0) {
if (exp & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string n_str;
int64 limit_m;
cin >> n_str >> limit_m;
// フェルマの小定理を用いて指数を MOD-1 で剰余
int64 exponent = 0;
for (char c : n_str) {
exponent = (exponent * 10 + (c - '0')) % (MOD - 1);
}
// べき乗の事前計算
vector<int64> powers(MOD);
for (int i = 0; i < MOD; ++i) {
powers[i] = mod_pow(i, exponent);
}
int64 total_sum = 0;
for (int64 left = 1, right; left <= limit_m; left = right + 1) {
right = limit_m / (limit_m / left);
int64 val_index = (limit_m / left) % MOD;
int64 count = (right - left + 1) % MOD;
total_sum = (total_sum + powers[val_index] * count) % MOD;
}
cout << total_sum << endl;
return 0;
}
問題 2：貪欲法の検討
本問題については、初期段階で貪欲アルゴリズムを適用することを検討したが、最適な部分構造を持たず誤った結果を導くことが判明した。また、実装過程において出力形式のミス（小数点の扱いなど）も確認された。 editorial を参照しても理解が困難な部分があり、本稿では詳細な解法の提示は省略する。
問題 3：平方分割とデータ構造の組み合わせ
この問題は典型的には「樹套樹（Tree of Trees）」を用いて解決されるが、平方分解（Square Root Decomposition）を応用することで同等の性能を発揮させることができる。実装においては、配列をブロックに分割し、各ブロック内で値をソートした構造を維持する。
クエリ処理では、範囲内の最大値を特定の条件付きで検索する必要がある。これに対し、二分探索木や Fenwick Tree（Binary Indexed Tree）を前処理に利用し、ブロック内では Sparse Table（ST テーブル）を用いて区間最大値を高速に取得する構成とした。暗号化された入力に対しては、直前の回答結果を用いて復号化する処理を含む。
実装コード（問題 3）
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using int_t = int;
const int MAXN = 100010;
const int BLOCK_SIZE = 320;
int n, k, q_count, encrypt_flag;
int arr[MAXN], sorted_vals[MAXN];
int block_id[MAXN], block_start[MAXN], block_end[MAXN];
int bit_tree[MAXN];
int weight[MAXN];
// Sparse Table for range max/min on original indices
int st_max[MAXN][20], st_min[MAXN][20];
int lg_table[MAXN];
// Block internal structures
vector<int> block_sorted_vals[MAXN / BLOCK_SIZE + 5];
vector<int> block_weights[MAXN / BLOCK_SIZE + 5];
int block_st[MAXN / BLOCK_SIZE + 5][BLOCK_SIZE][12];
int lowbit(int x) { return x & -x; }
void bit_add(int idx, int val) {
for (; idx <= n; idx += lowbit(idx))
bit_tree[idx] += val;
}
int bit_query(int idx) {
int sum = 0;
for (; idx > 0; idx -= lowbit(idx))
sum += bit_tree[idx];
return sum;
}
void init_st_tables() {
for (int i = 1; i <= n; ++i) {
st_max[i][0] = st_min[i][0] = arr[i];
}
for (int j = 1; j < 20; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
}
}
}
int query_st_max(int l, int r) {
int k = lg_table[r - l + 1];
return max(st_max[l][k], st_max[r - (1 << k) + 1][k]);
}
int query_st_min(int l, int r) {
int k = lg_table[r - l + 1];
return min(st_min[l][k], st_min[r - (1 << k) + 1][k]);
}
void build_block(int b_idx) {
int sz = block_sorted_vals[b_idx].size();
// Build ST table inside block for weights
for (int i = 0; i < sz; ++i) {
block_st[b_idx][i + 1][0] = block_weights[b_idx][i];
}
for (int j = 1; j < 12; ++j) {
for (int i = 1; i + (1 << j) - 1 <= sz; ++i) {
block_st[b_idx][i][j] = max(block_st[b_idx][i][j - 1],
block_st[b_idx][i + (1 << (j - 1))][j - 1]);
}
}
}
int query_block_max(int b_idx, int l, int r) {
if (l > r) return 0;
int len = r - l + 1;
int k = lg_table[len];
return max(block_st[b_idx][l][k], block_st[b_idx][r - (1 << k) + 1][k]);
}
int solve_range_query(int L, int R, int val_min, int val_max) {
int ans = 0;
int bL = block_id[L], bR = block_id[R];
if (bL == bR) {
for (int i = L; i <= R; ++i) {
if (arr[i] >= val_min && arr[i] <= val_max)
ans = max(ans, weight[i]);
}
return ans;
}
for (int i = L; i <= block_end[bL]; ++i) {
if (arr[i] >= val_min && arr[i] <= val_max)
ans = max(ans, weight[i]);
}
for (int i = block_start[bR]; i <= R; ++i) {
if (arr[i] >= val_min && arr[i] <= val_max)
ans = max(ans, weight[i]);
}
for (int b = bL + 1; b < bR; ++b) {
auto it_l = lower_bound(block_sorted_vals[b].begin(), block_sorted_vals[b].end(), val_min);
auto it_r = upper_bound(block_sorted_vals[b].begin(), block_sorted_vals[b].end(), val_max);
int idx_l = it_l - block_sorted_vals[b].begin() + 1;
int idx_r = it_r - block_sorted_vals[b].begin(); // upper_bound returns one past
if (idx_l <= idx_r) {
ans = max(ans, query_block_max(b, idx_l, idx_r));
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int sub_id;
cin >> sub_id >> n >> k >> q_count >> encrypt_flag;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
sorted_vals[i] = arr[i];
}
// Block decomposition setup
int num_blocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
for (int i = 1; i <= num_blocks; ++i) {
block_start[i] = (i - 1) * BLOCK_SIZE + 1;
block_end[i] = min(i * BLOCK_SIZE, n);
for (int j = block_start[i]; j <= block_end[i]; ++j) {
block_id[j] = i;
}
}
// Log table precomputation
lg_table[1] = 0;
for (int i = 2; i <= n; ++i) lg_table[i] = lg_table[i / 2] + 1;
// Coordinate compression
sort(sorted_vals + 1, sorted_vals + n + 1);
int m = unique(sorted_vals + 1, sorted_vals + n + 1) - sorted_vals - 1;
for (int i = 1; i <= n; ++i) {
arr[i] = lower_bound(sorted_vals + 1, sorted_vals + m + 1, arr[i]) - sorted_vals;
}
init_st_tables();
// Calculate weights using BIT (count neighbors within k)
for (int i = n; i >= 1; --i) {
bit_add(arr[i], 1);
int l_idx = lower_bound(sorted_vals + 1, sorted_vals + m + 1, sorted_vals[arr[i]] - k) - sorted_vals;
int r_idx = upper_bound(sorted_vals + 1, sorted_vals + m + 1, sorted_vals[arr[i]] + k) - sorted_vals - 1;
weight[i] = bit_query(r_idx) - bit_query(l_idx - 1);
}
// Build block internal structures
for (int i = 1; i <= num_blocks; ++i) {
for (int j = block_start[i]; j <= block_end[i]; ++j) {
block_sorted_vals[i].push_back(arr[j]);
block_weights[i].push_back(weight[j]);
}
// Sort based on values to enable binary search
vector<pair<int, int>> temp;
for (size_t idx = 0; idx < block_sorted_vals[i].size(); ++idx) {
temp.push_back({block_sorted_vals[i][idx], block_weights[i][idx]});
}
sort(temp.begin(), temp.end());
for (size_t idx = 0; idx < temp.size(); ++idx) {
block_sorted_vals[i][idx] = temp[idx].first;
block_weights[i][idx] = temp[idx].second;
}
build_block(i);
}
int last_ans = 0;
while (q_count--) {
int type, l, r;
cin >> type >> l >> r;
if (encrypt_flag == 1) {
type ^= last_ans;
l ^= last_ans;
r ^= last_ans;
}
int min_val = query_st_min(l, r);
int max_val = query_st_max(l, r);
int search_l = lower_bound(sorted_vals + 1, sorted_vals + m + 1, sorted_vals[max_val] - k) - sorted_vals;
int search_r = upper_bound(sorted_vals + 1, sorted_vals + m + 1, sorted_vals[min_val] + k) - sorted_vals - 1;
if (search_l > search_r || type > l) {
cout << (last_ans = 0) << '\n';
continue;
}
last_ans = solve_range_query(type, l, search_l, search_r);
cout << last_ans << '\n';
}
return 0;
}