编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#107901 | #1029. 寒域爷的兔子 | Accepted | 100 | 211 ms | 512 K | C++ / 889 B | 2177277017 | 2024-07-05 11:42:33 |
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll M;
int K;
struct matrix {
int n, m;
int z[3][3];
matrix() {
n = m = 0;
memset(z, 0, sizeof(z));
}
} F, G;
matrix operator*(const matrix &a, const matrix b) {
matrix c;
c.n = a.n;
c.m = b.m;
for (int i = 1; i <= c.n; i++)
for (int j = 1; j <= c.m; j++)
for (int k = 1; k <= a.m; k++) c.z[i][j] = (c.z[i][j] + a.z[i][k] * b.z[k][j] % K) % K;
return c;
}
matrix ksm(matrix a, ll b) {
matrix c;
c.n = a.n;
c.m = a.m;
c.z[1][1] = c.z[2][2] = 1;
for (; b; b >>= 1uLL, a = a * a)
if (b & 1)
c = c * a;
return c;
}
int main() {
cin >> M >> K;
F.n = 1;
F.m = 2;
F.z[1][1] = 1;
F.z[1][2] = 1;
G.n = G.m = 2;
G.z[1][2] = G.z[2][1] = G.z[2][2] = 1;
if (M == 1) {
printf("%d", (2LL * F.z[1][2]) % K);
return 0;
}
G = ksm(G, M - 2);
F = F * G;
printf("%d\n", (2uLL * F.z[1][2]) % K);
return 0;
}
用户输出
5770
系统信息
Exited with return code 0
用户输出
27662
系统信息
Exited with return code 0
用户输出
8791
系统信息
Exited with return code 0
用户输出
6732
系统信息
Exited with return code 0
用户输出
1454
系统信息
Exited with return code 0
用户输出
3790
系统信息
Exited with return code 0
用户输出
11690
系统信息
Exited with return code 0
用户输出
2151
系统信息
Exited with return code 0
用户输出
1617
系统信息
Exited with return code 0
用户输出
10509
系统信息
Exited with return code 0
用户输出
4380
系统信息
Exited with return code 0
用户输出
2560
系统信息
Exited with return code 0
用户输出
1938
系统信息
Exited with return code 0
用户输出
10705
系统信息
Exited with return code 0
用户输出
9350
系统信息
Exited with return code 0
用户输出
8076
系统信息
Exited with return code 0
用户输出
7210
系统信息
Exited with return code 0
用户输出
666
系统信息
Exited with return code 0
用户输出
16089
系统信息
Exited with return code 0
用户输出
5065
系统信息
Exited with return code 0
用户输出
9362
系统信息
Exited with return code 0
用户输出
9370
系统信息
Exited with return code 0
用户输出
4198
系统信息
Exited with return code 0
用户输出
4041
系统信息
Exited with return code 0
用户输出
4361
系统信息
Exited with return code 0
用户输出
11702
系统信息
Exited with return code 0
用户输出
13980
系统信息
Exited with return code 0
用户输出
1442
系统信息
Exited with return code 0
用户输出
24628
系统信息
Exited with return code 0
用户输出
6954
系统信息
Exited with return code 0
用户输出
5562
系统信息
Exited with return code 0