XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#100639 #1029. 寒域爷的兔子 Accepted 100 268 ms 384 K C++ 11 / 952 B 2203714902 2023-08-08 17:30:50
显示原始代码 
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull M, K;

struct Matrix {
    ull a[3][3];
    Matrix() { memset(a, 0, sizeof a); }
    Matrix operator*(const Matrix &b) const {
        Matrix res;
        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
                for (int k = 1; k <= 2; k++) res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % K;
        return res;
    }
};
Matrix ans, base;

void init() {
    base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
    ans.a[1][1] = ans.a[1][2] = 1;
}

void qpow(ull n) {
    while (n) {
        if (n & 1)
            ans = ans * base;
        base = base * base;
        n >>= 1;
    }
}

int main() {
    cin >> M >> K;
    init();
    if (M <= 2) {
        cout << 2 % K;
        return 0;
    }
    qpow(M - 2);
    cout << ans.a[1][1] * 2 % K;
    return 0;
}
子任务 #1
Accepted
得分：30
测试点 #1
Accepted
得分：100
用时：3 ms
内存：276 KiB

输入文件（small1.in） 

1 74

答案文件（small1.out） 

2

用户输出 

2

系统信息 

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

输入文件（small2.in） 

2 69

答案文件（small2.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：4 ms
内存：308 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
用时：5 ms
内存：324 KiB

输入文件（small5.in） 

5 99

答案文件（small5.out） 

10

用户输出 

10

系统信息 

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

输入文件（small6.in） 

6 29

答案文件（small6.out） 

16

用户输出 

16

系统信息 

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

输入文件（small7.in） 

7 43

答案文件（small7.out） 

26

用户输出 

26

系统信息 

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

输入文件（small8.in） 

8 40

答案文件（small8.out） 

2

用户输出 

2

系统信息 

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

输入文件（small9.in） 

9 52

答案文件（small9.out） 

16

用户输出 

16

系统信息 

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

输入文件（small10.in） 

10 53

答案文件（small10.out） 

4

用户输出 

4

系统信息 

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

输入文件（small11.in） 

11 37

答案文件（small11.out） 

30

用户输出 

30

系统信息 

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

输入文件（small12.in） 

12 45

答案文件（small12.out） 

18

用户输出 

18

系统信息 

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

输入文件（small13.in） 

13 5

答案文件（small13.out） 

1

用户输出 

1

系统信息 

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

输入文件（small14.in） 

14 53

答案文件（small14.out） 

12

用户输出 

12

系统信息 

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

输入文件（small15.in） 

15 51

答案文件（small15.out） 

47

用户输出 

47

系统信息 

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

输入文件（small16.in） 

16 26

答案文件（small16.out） 

24

用户输出 

24

系统信息 

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

输入文件（small17.in） 

17 70

答案文件（small17.out） 

44

用户输出 

44

系统信息 

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

输入文件（small18.in） 

18 36

答案文件（small18.out） 

20

用户输出 

20

系统信息 

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

输入文件（small19.in） 

19 64

答案文件（small19.out） 

42

用户输出 

42

系统信息 

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

输入文件（small20.in） 

20 89

答案文件（small20.out） 

2

用户输出 

2

系统信息 

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

输入文件（big1.in） 

18446744073709551615 7994

答案文件（big1.out） 

5770

用户输出 

5770

系统信息 

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

输入文件（big2.in） 

18446744073709551614 29078

答案文件（big2.out） 

27662

用户输出 

27662

系统信息 

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

输入文件（big3.in） 

18446744073709551613 19605

答案文件（big3.out） 

8791

用户输出 

8791

系统信息 

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

输入文件（big4.in） 

18446744073709551612 12114

答案文件（big4.out） 

6732

用户输出 

6732

系统信息 

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

输入文件（big5.in） 

18446744073709551611 11803

答案文件（big5.out） 

1454

用户输出 

1454

系统信息 

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

输入文件（big6.in） 

18446744073709551610 30259

答案文件（big6.out） 

3790

用户输出 

3790

系统信息 

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

输入文件（big7.in） 

18446744073709551609 25670

答案文件（big7.out） 

68

用户输出 

68

系统信息 

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

输入文件（big8.in） 

18446744073709551608 19432

答案文件（big8.out） 

11690

用户输出 

11690

系统信息 

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

输入文件（big9.in） 

18446744073709551607 12450

答案文件（big9.out） 

26

用户输出 

26

系统信息 

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

输入文件（big10.in） 

18446744073709551606 23556

答案文件（big10.out） 

16

用户输出 

16

系统信息 

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

输入文件（big11.in） 

18446744073709551605 2015

答案文件（big11.out） 

10

用户输出 

10

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：4 ms
内存：344 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
用时：4 ms
内存：252 KiB

输入文件（big14.in） 

18446744073709551602 12087

答案文件（big14.out） 

2

用户输出 

2

系统信息 

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

输入文件（big15.in） 

18446744073709551601 31850

答案文件（big15.out） 

2

用户输出 

2

系统信息 

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

输入文件（big16.in） 

18446744073709551600 7791

答案文件（big16.out） 

1617

用户输出 

1617

系统信息 

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

输入文件（big17.in） 

18446744073709551599 15029

答案文件（big17.out） 

10509

用户输出 

10509

系统信息 

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

输入文件（big18.in） 

18446744073709551598 16723

答案文件（big18.out） 

4380

用户输出 

4380

系统信息 

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

输入文件（big19.in） 

18446744073709551597 13276

答案文件（big19.out） 

2560

用户输出 

2560

系统信息 

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

输入文件（big20.in） 

18446744073709551596 16130

答案文件（big20.out） 

6434

用户输出 

6434

系统信息 

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

输入文件（random1.in） 

4464892338285178880 21466

答案文件（random1.out） 

1938

用户输出 

1938

系统信息 

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

输入文件（random2.in） 

4427736507453402112 13663

答案文件（random2.out） 

10705

用户输出 

10705

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：4 ms
内存：328 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
用时：3 ms
内存：340 KiB

输入文件（random5.in） 

14866836069781237760 9298

答案文件（random5.out） 

7210

用户输出 

7210

系统信息 

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

输入文件（random6.in） 

2715753453522595328 1776

答案文件（random6.out） 

666

用户输出 

666

系统信息 

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

输入文件（random7.in） 

3252261132048099840 25387

答案文件（random7.out） 

16089

用户输出 

16089

系统信息 

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

输入文件（random8.in） 

1921969794843727104 6047

答案文件（random8.out） 

5065

用户输出 

5065

系统信息 

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

输入文件（random9.in） 

16761783442201856000 27092

答案文件（random9.out） 

9362

用户输出 

9362

系统信息 

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

输入文件（random10.in） 

6339009926754648064 27913

答案文件（random10.out） 

9370

用户输出 

9370

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：5 ms
内存：328 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
用时：8 ms
内存：256 KiB

输入文件（random13.in） 

8136563985025304576 6853

答案文件（random13.out） 

4361

用户输出 

4361

系统信息 

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

输入文件（random14.in） 

4821813501123762176 29237

答案文件（random14.out） 

11702

用户输出 

11702

系统信息 

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

输入文件（random15.in） 

10441914397996910592 18286

答案文件（random15.out） 

13980

用户输出 

13980

系统信息 

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

输入文件（random16.in） 

16686345846270672896 10136

答案文件（random16.out） 

1442

用户输出 

1442

系统信息 

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

输入文件（random17.in） 

501040749095172032 25615

答案文件（random17.out） 

24628

用户输出 

24628

系统信息 

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

输入文件（random18.in） 

3320380155239690240 11168

答案文件（random18.out） 

6954

用户输出 

6954

系统信息 

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

输入文件（random19.in） 

4927651322280944640 10939

答案文件（random19.out） 

5562

用户输出 

5562

系统信息 

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

输入文件（random20.in） 

16261305660240498688 21014

答案文件（random20.out） 

5250

用户输出 

5250

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号