#1153084 (C++23) No.3478 XOR-Folding Primes

• 問題: No.3478 XOR-Folding Primes
• ユーザー: abc864197532
• 提出日時: 2026-03-20 22:00:41
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 638 ms / 4,000 ms
• コード長: 3,784 bytes
• コンパイル時間: 2,534 ms
• コンパイル使用メモリ: 348,124 KB
• 実行使用メモリ: 120,924 KB
• 最終ジャッジ日時: 2026-03-20 22:00:49
• 合計ジャッジ時間: 5,810 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 8

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
#ifdef Doludu
template <typename T>
ostream& operator << (ostream &o, vector <T> vec) {
    o << "{"; int f = 0;
    for (T i : vec) o << (f++ ? " " : "") << i;
    return o << "}";
}
void bug__(int c, auto ...a) {
    cerr << "\e[1;" << c << "m";
    (..., (cerr << a << " "));
    cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif
const int mod = 998244353, N = 10000006;

int add(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
int sub(int a, int b) { a -= b; if (a < 0) a += mod; return a; }
int mul(int a, int b) { return 1ll * a * b % mod; }
int Pow(int a, int b) { int ans = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ans = mul(ans, a); return ans; }

int lp[N], pre1[N], pre2[N];

struct mat {
    int n;
    long long mod2;
    vector <vector <long long>> val;
    mat () = default;
    mat (int _n, int _mode = 0) : n(_n), mod2(1ll * mod * mod) {
        // mode 1 -> I, other -> O
        val.assign(n, vector<long long>(n, 0));
        if (_mode == 1) {
            for (int i = 0; i < n; ++i) val[i][i] = 1;
        }
    }
    mat (const mat& M) : n(M.n), mod2(1ll * mod * mod) {
        val.assign(n, vector<long long>(n, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                val[i][j] = M.val[i][j];
            }
        }
    }
    mat (vector <vector <long long>> v) : n(v.size()), mod2(1ll * mod * mod), val(v) {}
    mat operator + (const mat& o) {
        mat ans(o);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ans.val[i][j] += val[i][j];
                if (ans.val[i][j] >= mod) ans.val[i][j] -= mod;
            }
        }
        return ans;
    }
    mat operator * (const mat& o) {
        mat ans(n, 0);
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < n; ++k) {
                for (int j = 0; j < n; ++j) {
                    ans.val[i][j] += val[i][k] * o.val[k][j];
                    if (ans.val[i][j] >= mod2) ans.val[i][j] -= mod2;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ans.val[i][j] %= mod;
            }
        }
        return ans;
    }
    mat operator ^ (long long k) {
        mat ans(n, 1), a(*this);
        for (; k; k >>= 1, a = a * a) {
            if (k & 1) ans = ans * a;
        }
        return ans;
    }
    mat& operator = (mat o) {
        this->n = o.n, this->val = o.val, this->mod2 = o.mod2;
        return *this;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    for (int i = 2; i < N; ++i) if (!lp[i]) {
        for (int j = i + i; j < N; j += i) {
            lp[j] = 1;
        }
    }
    lp[0] = lp[1] = 1;
    for (int i = 1; i < N; ++i) {
        pre1[i] = pre1[i - 1] + ((i ^ 2) < i && !lp[i ^ 2] && !lp[i]);
        pre2[i] = pre2[i - 1] + (!lp[i]);
    }

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n == 1) {
            cout << pre2[m] << "\n";
        } else {
            vector a(2, vector(2, 0ll));
            a[0][1] = 2 * pre1[m];
            a[1][0] = 1;
            a[1][1] = 1;
            mat tmp(a);
            tmp = tmp ^ (n - 1);
            cout << add(add(tmp.val[0][0], tmp.val[0][1]), mul(2 * pre1[m], add(tmp.val[1][0], tmp.val[1][1]))) << "\n";
        }
    }
}