XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#63258 #1029. 寒域爷的兔子 Accepted 100 125 ms 380 K C++ 11 / 1.0 K 电类047-王宇晗 2021-07-21 17:52:23
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef struct {
    ll mat[2][2];
} matrix;
ll k;
matrix multiply(matrix a, matrix b) {
    matrix c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c.mat[i][j] = (a.mat[i][0] * b.mat[0][j] + a.mat[i][1] * b.mat[1][j]) % k;
        }
    }
    return c;
}

matrix matrixPow(matrix a, ll n) {
    matrix ret;
    ret.mat[0][0] = ret.mat[1][1] = 1;
    ret.mat[0][1] = ret.mat[1][0] = 0;
    while (n > 0) {
        if ((n & 1) == 1) {
            ret = multiply(ret, a);
        }
        n >>= 1;
        a = multiply(a, a);
    }
    return ret;
}

ll fib(ll n) {
    matrix ret;
    ret.mat[1][1] = 0;
    ret.mat[0][0] = ret.mat[0][1] = ret.mat[1][0] = 1;
    matrix res = matrixPow(ret, n);
    return res.mat[0][0];
}

int main() {
    ll m;
    cin >> m >> k;
    cout << (2 % k * fib(m - 1)) % k;
    return 0;
}
子任务 #1
Accepted
得分：30
测试点 #1
Accepted
得分：100
用时：2 ms
内存：268 KiB

输入文件（small1.in） 

1 74

答案文件（small1.out） 

2

用户输出 

2

系统信息 

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

输入文件（small2.in） 

2 69

答案文件（small2.out） 

2

用户输出 

2

系统信息 

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

输入文件（small3.in） 

3 4

答案文件（small3.out） 

0

用户输出 

0

系统信息 

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

输入文件（small4.in） 

4 18

答案文件（small4.out） 

6

用户输出 

6

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small5.in） 

5 99

答案文件（small5.out） 

10

用户输出 

10

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：2 ms
内存：344 KiB

输入文件（small6.in） 

6 29

答案文件（small6.out） 

16

用户输出 

16

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small7.in） 

7 43

答案文件（small7.out） 

26

用户输出 

26

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small8.in） 

8 40

答案文件（small8.out） 

2

用户输出 

2

系统信息 

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

输入文件（small9.in） 

9 52

答案文件（small9.out） 

16

用户输出 

16

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small10.in） 

10 53

答案文件（small10.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small11.in） 

11 37

答案文件（small11.out） 

30

用户输出 

30

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small12.in） 

12 45

答案文件（small12.out） 

18

用户输出 

18

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small13.in） 

13 5

答案文件（small13.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small14.in） 

14 53

答案文件（small14.out） 

12

用户输出 

12

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small15.in） 

15 51

答案文件（small15.out） 

47

用户输出 

47

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small16.in） 

16 26

答案文件（small16.out） 

24

用户输出 

24

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：2 ms
内存：280 KiB

输入文件（small17.in） 

17 70

答案文件（small17.out） 

44

用户输出 

44

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small18.in） 

18 36

答案文件（small18.out） 

20

用户输出 

20

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（small19.in） 

19 64

答案文件（small19.out） 

42

用户输出 

42

系统信息 

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

输入文件（small20.in） 

20 89

答案文件（small20.out） 

2

用户输出 

2

系统信息 

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

输入文件（big1.in） 

18446744073709551615 7994

答案文件（big1.out） 

5770

用户输出 

5770

系统信息 

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

输入文件（big2.in） 

18446744073709551614 29078

答案文件（big2.out） 

27662

用户输出 

27662

系统信息 

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

输入文件（big3.in） 

18446744073709551613 19605

答案文件（big3.out） 

8791

用户输出 

8791

系统信息 

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

输入文件（big4.in） 

18446744073709551612 12114

答案文件（big4.out） 

6732

用户输出 

6732

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：2 ms
内存：320 KiB

输入文件（big5.in） 

18446744073709551611 11803

答案文件（big5.out） 

1454

用户输出 

1454

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big6.in） 

18446744073709551610 30259

答案文件（big6.out） 

3790

用户输出 

3790

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big7.in） 

18446744073709551609 25670

答案文件（big7.out） 

68

用户输出 

68

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：2 ms
内存：344 KiB

输入文件（big8.in） 

18446744073709551608 19432

答案文件（big8.out） 

11690

用户输出 

11690

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big9.in） 

18446744073709551607 12450

答案文件（big9.out） 

26

用户输出 

26

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big10.in） 

18446744073709551606 23556

答案文件（big10.out） 

16

用户输出 

16

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big11.in） 

18446744073709551605 2015

答案文件（big11.out） 

10

用户输出 

10

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big12.in） 

18446744073709551604 2613

答案文件（big12.out） 

2151

用户输出 

2151

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big13.in） 

18446744073709551603 432

答案文件（big13.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big14.in） 

18446744073709551602 12087

答案文件（big14.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：2 ms
内存：284 KiB

输入文件（big15.in） 

18446744073709551601 31850

答案文件（big15.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big16.in） 

18446744073709551600 7791

答案文件（big16.out） 

1617

用户输出 

1617

系统信息 

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

输入文件（big17.in） 

18446744073709551599 15029

答案文件（big17.out） 

10509

用户输出 

10509

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（big18.in） 

18446744073709551598 16723

答案文件（big18.out） 

4380

用户输出 

4380

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：2 ms
内存：356 KiB

输入文件（big19.in） 

18446744073709551597 13276

答案文件（big19.out） 

2560

用户输出 

2560

系统信息 

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

输入文件（big20.in） 

18446744073709551596 16130

答案文件（big20.out） 

6434

用户输出 

6434

系统信息 

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

输入文件（random1.in） 

4464892338285178880 21466

答案文件（random1.out） 

1938

用户输出 

1938

系统信息 

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

输入文件（random2.in） 

4427736507453402112 13663

答案文件（random2.out） 

10705

用户输出 

10705

系统信息 

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

输入文件（random3.in） 

6999370374719408128 21187

答案文件（random3.out） 

9350

用户输出 

9350

系统信息 

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

输入文件（random4.in） 

18053230047173007360 9514

答案文件（random4.out） 

8076

用户输出 

8076

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random5.in） 

14866836069781237760 9298

答案文件（random5.out） 

7210

用户输出 

7210

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random6.in） 

2715753453522595328 1776

答案文件（random6.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：2 ms
内存：308 KiB

输入文件（random7.in） 

3252261132048099840 25387

答案文件（random7.out） 

16089

用户输出 

16089

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random8.in） 

1921969794843727104 6047

答案文件（random8.out） 

5065

用户输出 

5065

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random9.in） 

16761783442201856000 27092

答案文件（random9.out） 

9362

用户输出 

9362

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random10.in） 

6339009926754648064 27913

答案文件（random10.out） 

9370

用户输出 

9370

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：2 ms
内存：276 KiB

输入文件（random11.in） 

610256373055243264 7367

答案文件（random11.out） 

4198

用户输出 

4198

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：2 ms
内存：312 KiB

输入文件（random12.in） 

7087193247594517504 12437

答案文件（random12.out） 

4041

用户输出 

4041

系统信息 

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

输入文件（random13.in） 

8136563985025304576 6853

答案文件（random13.out） 

4361

用户输出 

4361

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random14.in） 

4821813501123762176 29237

答案文件（random14.out） 

11702

用户输出 

11702

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random15.in） 

10441914397996910592 18286

答案文件（random15.out） 

13980

用户输出 

13980

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random16.in） 

16686345846270672896 10136

答案文件（random16.out） 

1442

用户输出 

1442

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random17.in） 

501040749095172032 25615

答案文件（random17.out） 

24628

用户输出 

24628

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：2 ms
内存：380 KiB

输入文件（random18.in） 

3320380155239690240 11168

答案文件（random18.out） 

6954

用户输出 

6954

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：2 ms
内存：248 KiB

输入文件（random19.in） 

4927651322280944640 10939

答案文件（random19.out） 

5562

用户输出 

5562

系统信息 

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

输入文件（random20.in） 

16261305660240498688 21014

答案文件（random20.out） 

5250

用户输出 

5250

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.