Submission #56609081

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

using ll = long long;

const int MOD = 998244353, primes[] = {2, 3, 5, 7, 11, 13};
ll N;
int M, cnt[25][6], s[(1 << 6) + 1];

struct matrix {
    int mat[(1 << 6) + 1][(1 << 6) + 1];
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i <= (1 << 6); i++) {
          for (int j = 0; j <= (1 << 6); j++) {
              c.mat[i][j] = 0;
              for (int k = 0; k <= (1 << 6); k++) {
                  c.mat[i][j] += (ll)a.mat[i][k] * b.mat[k][j] % MOD;
                  if (c.mat[i][j] >= MOD) {
					  c.mat[i][j] -= MOD;
				  }
              }
          }
        }
        return c;
    }
};

matrix matpow(matrix base, ll n) {
    matrix ans;
    for (int i = 0; i <= (1 << 6); i++) {
		for (int j = 0; j <= (1 << 6); j++) {
			ans.mat[i][j] = (i == j);
		}
	}
    while (n) {
        if (n % 2 == 1) {
            ans = ans * base;
		}
        base = base * base;
        n /= 2;
    }
    return ans;
}

matrix base;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int cur = i;
		for (int j = 0; j < 6; j++) {
			while (cur % primes[j] == 0) {
				cnt[i][j]++;
				cur /= primes[j];
			}
		}
	}
	for (int i = 0; i <= (1 << 6); i++) {
		for (int j = 0; j <= (1 << 6); j++) {
			base.mat[i][j] = 0;
		}
	}
	for (int bm = 0; bm < (1 << 6); bm++) {
		for (int i = 1; i <= M; i++) {
			vector<int> poss;
			for (int j = 0; j < 6; j++) {
				if (!(bm & (1 << j)) && cnt[i][j]) {
					poss.pb(j);
				}
			}
			for (int j = 0; j < (1 << (int)poss.size()); j++) {
				int new_bm = bm, mul = 1;
				for (int k = 0; k < (int)poss.size(); k++) {
					if (j & (1 << k)) {
						new_bm |= (1 << poss[k]);
						mul = (ll)mul * cnt[i][poss[k]] % MOD;
					}
				}
				base.mat[bm][new_bm] += mul;
				if (base.mat[bm][new_bm] >= MOD) {
					base.mat[bm][new_bm] -= MOD;
				}
			}
		}
		base.mat[bm][1 << 6] = 1;
	}
	base.mat[1 << 6][1 << 6] = 1;
	auto res = matpow(base, N - 1);
	for (int i = 0; i <= (1 << 6); i++) {
		for (int j = 0; j <= (1 << 6); j++) {
			s[i] += res.mat[i][j];
			if (s[i] >= MOD) {
				s[i] -= MOD;
			}
		}
	}
	int ret = 0, bm = 0;
	for (int i = 1; i <= M; i++) {
		vector<int> poss;
		for (int j = 0; j < 6; j++) {
			if (!(bm & (1 << j)) && cnt[i][j]) {
				poss.pb(j);
			}
		}
		for (int j = 0; j < (1 << (int)poss.size()); j++) {
			int new_bm = bm, mul = 1;
			for (int k = 0; k < (int)poss.size(); k++) {
				if (j & (1 << k)) {
					new_bm |= (1 << poss[k]);
					mul = (ll)mul * cnt[i][poss[k]] % MOD;
				}
			}
			ret += (ll)s[new_bm] * mul % MOD;
			if (ret >= MOD) {
				ret -= MOD;
			}
		}
	}
	cout << ret << '\n';
}

Submission Info

Judge Result