結果
| 問題 | No.3478 XOR-Folding Primes |
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-03-21 00:20:45 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 500 ms / 4,000 ms |
| コード長 | 7,732 bytes |
| 記録 | |
| コンパイル時間 | 4,541 ms |
| コンパイル使用メモリ | 385,212 KB |
| 実行使用メモリ | 14,632 KB |
| 最終ジャッジ日時 | 2026-03-21 00:21:37 |
| 合計ジャッジ時間 | 6,828 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 8 |
コンパイルメッセージ
main.cpp:124:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
124 | #pragma once
| ^~~~
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
std::vector<long long> sieveOfEratosthenes(long long n = 1000000) {
std::vector<bool>p(n + 1, true);
std::vector<long long>ret;
p[0] = false;
p[1] = false;
for (int i = 2; i <= n; ++i) {
if (!p[i]) continue;
ret.push_back(i);
for (int j = 2 * i; j <= n; j += i) p[j] = false;
}
return ret;
}
//long long にしているのは p*pとかでこまらないように
#ifndef KWM_T_MATH_MATRIX_SIMPLE_MATRIX_HPP
#define KWM_T_MATH_MATRIX_SIMPLE_MATRIX_HPP
// #include
#include <vector>
#include <cassert>
/**
* @brief シンプルな行列演算（vector版・軽量）
*
* 最低限の行列演算（乗算・累乗）を提供する。
* とりあえず使う用の軽量実装。
*
* 典型用途:
* - 行列累乗（DP遷移）
* - 小規模な行列計算
*
* 計算量:
* - 乗算: O(N^3)
* - 累乗: O(N^3 log K)
*
* @tparam T
* - 要素型（+, *, += が定義されていること）
*
* 制約 / 注意:
* - 正方行列のみ想定（matrixPow）
* - サイズ不一致は assert
* - 単位元は T(1) を使用
*
* 使用例:
* vector<vector<long long>> A(n, vector<long long>(n));
* auto B = matrixPow(10, A);
*
* verified:
* - 未検証
*/
namespace kwm_t::math::matrix {
template<typename T>
std::vector<std::vector<T>> matrixMul(
const std::vector<std::vector<T>>& A,
const std::vector<std::vector<T>>& B
) {
assert(!A.empty() && !B.empty());
assert(A[0].size() == B.size());
int n = (int)A.size();
int m = (int)B[0].size();
int p = (int)A[0].size();
std::vector<std::vector<T>> C(n, std::vector<T>(m, T(0)));
for (int i = 0; i < n; ++i) {
for (int k = 0; k < p; ++k) {
for (int j = 0; j < m; ++j) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
template<typename T>
std::vector<std::vector<T>> matrixPow(
long long n,
const std::vector<std::vector<T>>& mat
) {
assert(!mat.empty());
assert(mat.size() == mat[0].size());
int size = (int)mat.size();
std::vector<std::vector<T>> res(size, std::vector<T>(size, T(0)));
for (int i = 0; i < size; ++i) {
res[i][i] = T(1);
}
auto base = mat;
while (n > 0) {
if (n & 1) res = matrixMul(res, base);
base = matrixMul(base, base);
n >>= 1;
}
return res;
}
} // namespace kwm_t::math::matrix
#endif // KWM_T_MATH_MATRIX_SIMPLE_MATRIX_HPP
#pragma once
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstddef>
namespace stl {
namespace sorted_vector {
// x と等しい要素の個数
template <class T>
std::size_t count_equal(const std::vector<T>& v, const T& x) {
auto l = std::lower_bound(v.begin(), v.end(), x);
auto r = std::upper_bound(v.begin(), v.end(), x);
return std::distance(l, r);
}
// x 未満の個数
template <class T>
std::size_t count_less(const std::vector<T>& v, const T& x) {
return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x));
}
// x 以下の個数
template <class T>
std::size_t count_leq(const std::vector<T>& v, const T& x) {
return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x));
}
// x 以上の個数
template <class T>
std::size_t count_geq(const std::vector<T>& v, const T& x) {
return std::distance(std::lower_bound(v.begin(), v.end(), x), v.end());
}
// x より大きい個数
template <class T>
std::size_t count_greater(const std::vector<T>& v, const T& x) {
return std::distance(std::upper_bound(v.begin(), v.end(), x), v.end());
}
// [l, r) に含まれる個数
template <class T>
std::size_t count_range(const std::vector<T>& v, const T& l, const T& r) {
auto L = std::lower_bound(v.begin(), v.end(), l);
auto R = std::lower_bound(v.begin(), v.end(), r);
return std::distance(L, R);
}
// 存在判定（1個以上あるか）
template <class T>
bool contains(const std::vector<T>& v, const T& x) {
auto it = std::lower_bound(v.begin(), v.end(), x);
return it != v.end() && *it == x;
}
// 最初の出現位置（なければ v.size()）
template <class T>
std::size_t first_index(const std::vector<T>& v, const T& x) {
auto it = std::lower_bound(v.begin(), v.end(), x);
return (it != v.end() && *it == x) ? std::size_t(it - v.begin()) : v.size();
}
// 最後の出現位置（なければ v.size()）
template <class T>
std::size_t last_index(const std::vector<T>& v, const T& x) {
auto it = std::upper_bound(v.begin(), v.end(), x);
if (it == v.begin()) return v.size();
--it;
return (*it == x) ? std::size_t(it - v.begin()) : v.size();
}
// x 未満のうち最大の要素
template <class T>
auto it_less(const std::vector<T>& v, const T& x) {
auto it = std::lower_bound(v.begin(), v.end(), x);
if (it == v.begin()) return v.end();
--it;
return it;
}
// x 以下のうち最大の要素
template <class T>
auto it_leq(const std::vector<T>& v, const T& x) {
auto it = std::upper_bound(v.begin(), v.end(), x);
if (it == v.begin()) return v.end();
--it;
return it;
}
// x 以上のうち最小の要素
template <class T>
auto it_geq(const std::vector<T>& v, const T& x) {
return std::lower_bound(v.begin(), v.end(), x);
}
// x より大きい最小の要素
template <class T>
auto it_greater(const std::vector<T>& v, const T& x) {
return std::upper_bound(v.begin(), v.end(), x);
}
// x の最初の出現位置（なければ v.end()）
template <class T>
auto it_first(const std::vector<T>& v, const T& x) {
auto it = std::lower_bound(v.begin(), v.end(), x);
if (it != v.end() && *it == x) return it;
return v.end();
}
// x の最後の出現位置（なければ v.end()）
template <class T>
auto it_last(const std::vector<T>& v, const T& x) {
auto it = std::upper_bound(v.begin(), v.end(), x);
if (it == v.begin()) return v.end();
--it;
if (*it == x) return it;
return v.end();
}
} // namespace sorted_vector
} // namespace stl
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t; cin >> t;
vector<int>p0, p1, p2, p3, p4;
auto ps = sieveOfEratosthenes(10000000);
vector<int>p;
rep(i, ps.size() - 1) {
if (ps[i] % 4 != 1)continue;
if (ps[i] + 2 == ps[i + 1]) {
p.push_back(ps[i]);
p.push_back(ps[i + 1]);
}
}
while (t--) {
int n, m; cin >> n >> m;
if (n == 1) {
int ans = stl::sorted_vector::count_leq<long long>(ps, m);
cout << ans << endl;
continue;
}
int c = stl::sorted_vector::count_leq(p, m);
if (m % 4 == 1 && stl::sorted_vector::contains(p, m)) {
c--;
}
else if (m % 4 == 2 && stl::sorted_vector::contains(p, m - 1)) {
c--;
}
vector<vector<mint>> mat = { {1,1},{c,0} };
mat = kwm_t::math::matrix::matrixPow(n - 1, mat);
mint ans = c * (mat[0][0] + mat[0][1]);
ans += 1 * (mat[1][0] + mat[1][1]);
cout << ans.val() << endl;
}
return 0;
}