QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765750 | #9489. 0100 Insertion | remmymilkyway | WA | 0ms | 4096kb | C++23 | 1.5kb | 2024-11-20 15:10:33 | 2024-11-20 15:10:36 |
Judging History
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'