QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765750#9489. 0100 InsertionremmymilkywayWA 0ms4096kbC++231.5kb2024-11-20 15:10:332024-11-20 15:10:36

Judging History

This is the latest submission verdict.

  • [2024-11-20 15:10:36]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 4096kb
  • [2024-11-20 15:10:33]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
int N, M;
ll f[65][2];
struct mat {
	int h, w;
	ll arr[3][3];
	ll* operator[] (int x) {
		return arr[x];
	}
	mat() {}
	mat(vector<vector<int>> v) {
		h = v.size();
		w = v[0].size();
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				arr[i][j] = v[i][j];
			}
		}
	}
	friend mat operator* (mat x, mat y) {
		mat ret;
		ret.h = x.h;
		ret.w = y.w;
		for (int i = 0; i < x.h; i++) {
			for (int j = 0; j < y.w; j++) {
				ret[i][j] = 0;
				for (int ii = 0; ii < x.w; ii++) {
					(ret[i][j] += x[i][ii] * y[ii][j] % MOD) %= MOD;
				}
			}
		}
		return ret;
	}
};
mat qpow(mat x, int e) {
	mat ret({{1, 0, 0}, {0, 1, 0}, {0, 0, 1}});
	while (e) {
		if (e & 1) {
			ret = ret * x;
		}
		x = x * x;
		e >>= 1;
	}
	return ret;
}
int main() {
	scanf("%d %d", &N, &M);
	mat trans({{0, 1, 0}, {0, 0, 1}, {1, 1, 0}}), vec({{0}, {2}, {3}});
	ll wN = 0;
	if (N > 3) {
		wN = (qpow(trans, N - 3) * vec)[2][0];
	} else {
		wN = vec[N - 1][0];
	}
	// cout << wN << '\n';
	f[0][0] = 1;
	for (int i = 1; i <= 30; i++) {
		if (!((M >> (i - 1)) & 1)) {
			f[i][0] = f[i - 1][0];
			f[i][1] = (f[i - 1][1] * wN % MOD + f[i - 1][0]) % MOD;
		} else {
			f[i][0] = (f[i - 1][0] * wN % MOD + f[i - 1][1]) % MOD;
			f[i][1] = f[i - 1][1];
		}
		// cout << f[i][0] << ' ' << f[i][1] << '\n';
	}
	printf("%lld\n", f[30][0]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4096kb

input:

8
0??0?100

output:

1

result:

wrong answer 1st words differ - expected: '2', found: '1'