玄关求调 关于刚才的 C 题
查看原帖
玄关求调 关于刚才的 C 题
531746
Composite_Function楼主2024/8/11 22:05
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
struct Matrix {
#define uint unsigned long long
#define __ERROR_OF_NOT_FIT_MATRIX__ 893167885
	uint row, col;
	vector<vector<int> > mat;
	Matrix(int R, int C) {
		row = R, col = C;
		vector<int> __ROW_OF_MATRIX__;
		__ROW_OF_MATRIX__.assign(C + 1, 0);
		mat.assign(R + 1, __ROW_OF_MATRIX__);
	}
	Matrix(int R, int C, int num) {
		row = R, col = C;
		vector<int> __ROW_OF_MATRIX__;
		__ROW_OF_MATRIX__.assign(C + 1, num);
		mat.assign(R + 1, __ROW_OF_MATRIX__);
	}
	Matrix operator +(const Matrix& ADD) {
		if (row != ADD.row || col != ADD.col) exit(__ERROR_OF_NOT_FIT_MATRIX__);
		Matrix RET(row, col);
		for (uint r = 0; r <= row; ++r)
			for (uint c = 0; c <= col; ++c)
				RET.mat[r][c] = (mat[r][c] + ADD.mat[r][c]) % mod;
		return RET;
	}
	Matrix operator *(const Matrix& MUL) {
		if (col != MUL.row) exit(__ERROR_OF_NOT_FIT_MATRIX__);
		Matrix RET(row, MUL.col);
		for (uint r = 0; r <= row; ++r)
			for (uint c = 0; c <= MUL.col; ++c)
				for (uint k = 0; k <= col; ++k)
					RET.mat[r][c] = (RET.mat[r][c] + mat[r][k] * MUL.mat[k][c]) % mod;
		return RET;
	}
	Matrix operator ^(const uint& INDEX) {
		if (row != col) exit(__ERROR_OF_NOT_FIT_MATRIX__);
		Matrix RET = *this, BASE = *this;
		uint __INDEX = INDEX - 1;
		while (__INDEX) {
			if (__INDEX & 1) RET = RET * BASE;
			BASE = BASE * BASE, __INDEX >>= 1;
		}
		return RET;
	}
};
const int p[6] = {2, 3, 5, 7, 11, 13};
int n, m;
inline int calc(int x) {
	if (x == 2) return 1;
	if (x == 3) return 2;
	if (x == 5) return 3;
	if (x == 7) return 4;
	if (x == 11) return 5;
	if (x == 13) return 6;
	return 0;
}
inline int qpow(int x, int y) {
	int ret = 1;
	while (y) {
		if (y & 1) ret *= x;
		x *= x, y >>= 1;
	}
	return ret;
}
signed main() {
	cin >> n >> m;
	Matrix bas(63, 63), rec(63, 63);
	for (int i = 0; i < 64; ++i) {
		bas.mat[1][i] = 1;
		for (int j = 1; j <= m; ++j) {
			if (j == 1) {
				rec.mat[i][i] += 2;
				continue;
			}
			int J = j, cnt = 0, p[2] = {0, 0}, q[2] = {0, 0};
			for (int k = 2; k <= J; ++k)
				if (J % k == 0) {
					p[cnt] = k;
					q[cnt] = 0;
					while (J % k == 0) J /= k, ++q[cnt];
					++cnt;
				}
			if (cnt == 1) {
				int P = calc(p[0]);
				if (i & (1 << (P - 1))) {
					rec.mat[i][i] += 1;
					rec.mat[i ^ (1 << (P - 1))][i] += q[0];
				}
				else ++rec.mat[i][i];
			}
			else {
				int P0 = calc(p[0]), P1 = calc(p[1]);
				if ((i & (1 << (P0 - 1))) && (i & (1 << (P1 - 1)))) {
					rec.mat[i][i] += 1;
					rec.mat[i ^ (1 << (P0 - 1))][i] += q[0];
					rec.mat[i ^ (1 << (P1 - 1))][i] += q[1];
					rec.mat[i ^ (1 << (P0 - 1)) ^ (1 << (P1 - 1))][i] += q[0] * q[1];
				}
				else if (i & (1 << (P0 - 1))) {
					rec.mat[i][i] += 1;
					rec.mat[i ^ (1 << (P0 - 1))][i] += q[0];
				}
				else if (i & (1 << (P1 - 1))) {
					rec.mat[i][i] += 1;
					rec.mat[i ^ (1 << (P1 - 1))][i] += q[1];
				}
				else ++rec.mat[i][i];
			}
		}
	}
//	for (int i = 0; i < 64; ++i) cout << rec.mat[i][63] << " ";
 	bas = bas * (rec ^ n);
	cout << (bas.mat[1][63] - 1 + mod) % mod << endl;
	return 0;
}

请问这样做哪里错了

2024/8/11 22:05
加载中...