Submission #56617393

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int mod = 998244353;

using matrix = array<array<ll, 65>, 65>;
const int p[] = {2, 3, 5, 7, 11, 13};

matrix operator*(const matrix &a, const matrix &b) {
    matrix c;
    for (int i = 0; i < 65; i++) {
        for (int j = 0; j < 65; j++) {
            c[i][j] = 0;
        }
    }

    for (int i = 0; i < 65; i++)
        for (int j = 0; j < 65; j++)
            for (int k = 0; k < 65; k++)
                (c[i][j] += a[i][k] * b[k][j]) %= mod;
    return c;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    ll n;
    int m;
    cin >> n >> m;

    matrix base;
    for (int i = 0; i < 65; i++) {
        for (int j = 0; j < 65; j++) {
            base[i][j] = 0;
        }
    }

    for (int x = 1; x <= m; x++) {
        vector<int> have(6);
        for (int i = 0; i < 6; i++) {
            for (int y = x; y % p[i] == 0; y /= p[i])
                have[i]++;
        }

        for (int i = 0; i < 64; i++) {
            for (int j = 0; j < 64; j++) {
                if ((i & j) != i)
                    continue;

                int ways = 1;
                for (int b = 0; b < 6; b++) {
                    if ((i >> b & 1) == 0 && (j >> b & 1))
                        ways *= have[b];
                }

                (base[i][j] += ways) %= mod;
            }
        }
    }
    base[63][64] = base[64][64] = 1;

    matrix res;
    for (int i = 0; i < 65; i++)
        for (int j = 0; j < 65; j++)
            res[i][j] = i == j;

    for (; n; n >>= 1, base = base * base)
        if (n & 1)
            res = res * base;

    ll ans = mod - 1;
    for (int i = 0; i < 64; i++)
        (ans += res[i][63] + res[i][64]) %= mod;

    cout << ans << '\n';

    return 0;
}

Submission Info

Judge Result