编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#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;
}
子任务 #1
Accepted
得分:30
测试点 #1
Accepted
得分:100
用时:3 ms
内存:384 KiB

输入文件(small1.in

1 74

答案文件(small1.out

2

用户输出

2

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:3 ms
内存:372 KiB

输入文件(small2.in

2 69

答案文件(small2.out

2

用户输出

2

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:4 ms
内存:236 KiB

输入文件(small3.in

3 4

答案文件(small3.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(small4.in

4 18

答案文件(small4.out

6

用户输出

6

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(small5.in

5 99

答案文件(small5.out

10

用户输出

10

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:4 ms
内存:324 KiB

输入文件(small6.in

6 29

答案文件(small6.out

16

用户输出

16

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:4 ms
内存:260 KiB

输入文件(small7.in

7 43

答案文件(small7.out

26

用户输出

26

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:4 ms
内存:368 KiB

输入文件(small8.in

8 40

答案文件(small8.out

2

用户输出

2

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:3 ms
内存:332 KiB

输入文件(small9.in

9 52

答案文件(small9.out

16

用户输出

16

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:3 ms
内存:244 KiB

输入文件(small10.in

10 53

答案文件(small10.out

4

用户输出

4

系统信息

Exited with return code 0
测试点 #11
Accepted
得分:100
用时:3 ms
内存:280 KiB

输入文件(small11.in

11 37

答案文件(small11.out

30

用户输出

30

系统信息

Exited with return code 0
测试点 #12
Accepted
得分:100
用时:4 ms
内存:244 KiB

输入文件(small12.in

12 45

答案文件(small12.out

18

用户输出

18

系统信息

Exited with return code 0
测试点 #13
Accepted
得分:100
用时:3 ms
内存:256 KiB

输入文件(small13.in

13 5

答案文件(small13.out

1

用户输出

1

系统信息

Exited with return code 0
测试点 #14
Accepted
得分:100
用时:3 ms
内存:240 KiB

输入文件(small14.in

14 53

答案文件(small14.out

12

用户输出

12

系统信息

Exited with return code 0
测试点 #15
Accepted
得分:100
用时:3 ms
内存:240 KiB

输入文件(small15.in

15 51

答案文件(small15.out

47

用户输出

47

系统信息

Exited with return code 0
测试点 #16
Accepted
得分:100
用时:3 ms
内存:232 KiB

输入文件(small16.in

16 26

答案文件(small16.out

24

用户输出

24

系统信息

Exited with return code 0
测试点 #17
Accepted
得分:100
用时:3 ms
内存:332 KiB

输入文件(small17.in

17 70

答案文件(small17.out

44

用户输出

44

系统信息

Exited with return code 0
测试点 #18
Accepted
得分:100
用时:3 ms
内存:256 KiB

输入文件(small18.in

18 36

答案文件(small18.out

20

用户输出

20

系统信息

Exited with return code 0
测试点 #19
Accepted
得分:100
用时:3 ms
内存:324 KiB

输入文件(small19.in

19 64

答案文件(small19.out

42

用户输出

42

系统信息

Exited with return code 0
测试点 #20
Accepted
得分:100
用时:4 ms
内存:460 KiB

输入文件(small20.in

20 89

答案文件(small20.out

2

用户输出

2

系统信息

Exited with return code 0
子任务 #2
Accepted
得分:30
测试点 #1
Accepted
得分:100
用时:4 ms
内存:280 KiB

输入文件(big1.in

18446744073709551615 7994

答案文件(big1.out

5770

用户输出

5770

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(big2.in

18446744073709551614 29078

答案文件(big2.out

27662

用户输出

27662

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:3 ms
内存:256 KiB

输入文件(big3.in

18446744073709551613 19605

答案文件(big3.out

8791

用户输出

8791

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:3 ms
内存:324 KiB

输入文件(big4.in

18446744073709551612 12114

答案文件(big4.out

6732

用户输出

6732

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:4 ms
内存:268 KiB

输入文件(big5.in

18446744073709551611 11803

答案文件(big5.out

1454

用户输出

1454

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:4 ms
内存:300 KiB

输入文件(big6.in

18446744073709551610 30259

答案文件(big6.out

3790

用户输出

3790

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:4 ms
内存:252 KiB

输入文件(big7.in

18446744073709551609 25670

答案文件(big7.out

68

用户输出

68

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:3 ms
内存:228 KiB

输入文件(big8.in

18446744073709551608 19432

答案文件(big8.out

11690

用户输出

11690

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(big9.in

18446744073709551607 12450

答案文件(big9.out

26

用户输出

26

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:3 ms
内存:256 KiB

输入文件(big10.in

18446744073709551606 23556

答案文件(big10.out

16

用户输出

16

系统信息

Exited with return code 0
测试点 #11
Accepted
得分:100
用时:3 ms
内存:220 KiB

输入文件(big11.in

18446744073709551605 2015

答案文件(big11.out

10

用户输出

10

系统信息

Exited with return code 0
测试点 #12
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(big12.in

18446744073709551604 2613

答案文件(big12.out

2151

用户输出

2151

系统信息

Exited with return code 0
测试点 #13
Accepted
得分:100
用时:3 ms
内存:332 KiB

输入文件(big13.in

18446744073709551603 432

答案文件(big13.out

4

用户输出

4

系统信息

Exited with return code 0
测试点 #14
Accepted
得分:100
用时:3 ms
内存:300 KiB

输入文件(big14.in

18446744073709551602 12087

答案文件(big14.out

2

用户输出

2

系统信息

Exited with return code 0
测试点 #15
Accepted
得分:100
用时:3 ms
内存:256 KiB

输入文件(big15.in

18446744073709551601 31850

答案文件(big15.out

2

用户输出

2

系统信息

Exited with return code 0
测试点 #16
Accepted
得分:100
用时:4 ms
内存:244 KiB

输入文件(big16.in

18446744073709551600 7791

答案文件(big16.out

1617

用户输出

1617

系统信息

Exited with return code 0
测试点 #17
Accepted
得分:100
用时:4 ms
内存:216 KiB

输入文件(big17.in

18446744073709551599 15029

答案文件(big17.out

10509

用户输出

10509

系统信息

Exited with return code 0
测试点 #18
Accepted
得分:100
用时:4 ms
内存:244 KiB

输入文件(big18.in

18446744073709551598 16723

答案文件(big18.out

4380

用户输出

4380

系统信息

Exited with return code 0
测试点 #19
Accepted
得分:100
用时:4 ms
内存:236 KiB

输入文件(big19.in

18446744073709551597 13276

答案文件(big19.out

2560

用户输出

2560

系统信息

Exited with return code 0
测试点 #20
Accepted
得分:100
用时:4 ms
内存:368 KiB

输入文件(big20.in

18446744073709551596 16130

答案文件(big20.out

6434

用户输出

6434

系统信息

Exited with return code 0
子任务 #3
Accepted
得分:40
测试点 #1
Accepted
得分:100
用时:4 ms
内存:324 KiB

输入文件(random1.in

4464892338285178880 21466

答案文件(random1.out

1938

用户输出

1938

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:4 ms
内存:260 KiB

输入文件(random2.in

4427736507453402112 13663

答案文件(random2.out

10705

用户输出

10705

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:3 ms
内存:256 KiB

输入文件(random3.in

6999370374719408128 21187

答案文件(random3.out

9350

用户输出

9350

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(random4.in

18053230047173007360 9514

答案文件(random4.out

8076

用户输出

8076

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:4 ms
内存:272 KiB

输入文件(random5.in

14866836069781237760 9298

答案文件(random5.out

7210

用户输出

7210

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:3 ms
内存:352 KiB

输入文件(random6.in

2715753453522595328 1776

答案文件(random6.out

666

用户输出

666

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:3 ms
内存:268 KiB

输入文件(random7.in

3252261132048099840 25387

答案文件(random7.out

16089

用户输出

16089

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:3 ms
内存:368 KiB

输入文件(random8.in

1921969794843727104 6047

答案文件(random8.out

5065

用户输出

5065

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(random9.in

16761783442201856000 27092

答案文件(random9.out

9362

用户输出

9362

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:4 ms
内存:324 KiB

输入文件(random10.in

6339009926754648064 27913

答案文件(random10.out

9370

用户输出

9370

系统信息

Exited with return code 0
测试点 #11
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(random11.in

610256373055243264 7367

答案文件(random11.out

4198

用户输出

4198

系统信息

Exited with return code 0
测试点 #12
Accepted
得分:100
用时:4 ms
内存:324 KiB

输入文件(random12.in

7087193247594517504 12437

答案文件(random12.out

4041

用户输出

4041

系统信息

Exited with return code 0
测试点 #13
Accepted
得分:100
用时:3 ms
内存:328 KiB

输入文件(random13.in

8136563985025304576 6853

答案文件(random13.out

4361

用户输出

4361

系统信息

Exited with return code 0
测试点 #14
Accepted
得分:100
用时:4 ms
内存:268 KiB

输入文件(random14.in

4821813501123762176 29237

答案文件(random14.out

11702

用户输出

11702

系统信息

Exited with return code 0
测试点 #15
Accepted
得分:100
用时:5 ms
内存:256 KiB

输入文件(random15.in

10441914397996910592 18286

答案文件(random15.out

13980

用户输出

13980

系统信息

Exited with return code 0
测试点 #16
Accepted
得分:100
用时:4 ms
内存:284 KiB

输入文件(random16.in

16686345846270672896 10136

答案文件(random16.out

1442

用户输出

1442

系统信息

Exited with return code 0
测试点 #17
Accepted
得分:100
用时:3 ms
内存:324 KiB

输入文件(random17.in

501040749095172032 25615

答案文件(random17.out

24628

用户输出

24628

系统信息

Exited with return code 0
测试点 #18
Accepted
得分:100
用时:3 ms
内存:240 KiB

输入文件(random18.in

3320380155239690240 11168

答案文件(random18.out

6954

用户输出

6954

系统信息

Exited with return code 0
测试点 #19
Accepted
得分:100
用时:3 ms
内存:512 KiB

输入文件(random19.in

4927651322280944640 10939

答案文件(random19.out

5562

用户输出

5562

系统信息

Exited with return code 0
测试点 #20
Accepted
得分:100
用时:2 ms
内存:332 KiB

输入文件(random20.in

16261305660240498688 21014

答案文件(random20.out

5250

用户输出

5250

系统信息

Exited with return code 0