XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#100282 #1029. 寒域爷的兔子 Accepted 100 279 ms 464 K C++ 17 (Clang) / 832 B Dytchem 2023-07-11 18:15:30
显示原始代码 
#include <iostream>

using namespace std;
typedef unsigned long long ll;

ll k;

struct mat {
    ll a11, a12, a21, a22;
};

void sq(mat &m) {
    ll a11 = m.a11;
    ll a12 = m.a12;
    ll a21 = m.a21;
    ll a22 = m.a22;
    m.a11 = (a11 * a11 + a12 * a21) % k;
    m.a12 = (a11 * a12 + a12 * a22) % k;
    m.a21 = (a21 * a11 + a22 * a21) % k;
    m.a22 = (a21 * a12 + a22 * a22) % k;
}

int main() {
    ll m;
    cin >> m >> k;

    if (m == 1 || m == 2) {
        cout << 2 % k;
        return 0;
    }

    m -= 2;
    // cout << m << endl;

    mat a;
    a.a11 = a.a12 = a.a21 = 1;
    a.a22 = 0;

    ll a1 = 2, a2 = 2;
    for (ll i = 0; m != 0; ++i) {
        ll t1 = a1, t2 = a2;
        if (m & 1) {
            a1 = (a.a11 * t1 + a.a12 * t2) % k;
            a2 = (a.a21 * t1 + a.a22 * t2) % k;
        }
        sq(a);
        m >>= 1;
        // cout << a1 << ' ';
    }
    cout << a1;
}
子任务 #1
Accepted
得分：30
测试点 #1
Accepted
得分：100
用时：4 ms
内存：256 KiB

输入文件（small1.in） 

1 74

答案文件（small1.out） 

2

用户输出 

2

系统信息 

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

输入文件（small2.in） 

2 69

答案文件（small2.out） 

2

用户输出 

2

系统信息 

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

输入文件（small3.in） 

3 4

答案文件（small3.out） 

0

用户输出 

0

系统信息 

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

输入文件（small4.in） 

4 18

答案文件（small4.out） 

6

用户输出 

6

系统信息 

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

输入文件（small5.in） 

5 99

答案文件（small5.out） 

10

用户输出 

10

系统信息 

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

输入文件（small6.in） 

6 29

答案文件（small6.out） 

16

用户输出 

16

系统信息 

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

输入文件（small7.in） 

7 43

答案文件（small7.out） 

26

用户输出 

26

系统信息 

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

输入文件（small8.in） 

8 40

答案文件（small8.out） 

2

用户输出 

2

系统信息 

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

输入文件（small9.in） 

9 52

答案文件（small9.out） 

16

用户输出 

16

系统信息 

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

输入文件（small10.in） 

10 53

答案文件（small10.out） 

4

用户输出 

4

系统信息 

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

输入文件（small11.in） 

11 37

答案文件（small11.out） 

30

用户输出 

30

系统信息 

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

输入文件（small12.in） 

12 45

答案文件（small12.out） 

18

用户输出 

18

系统信息 

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

输入文件（small13.in） 

13 5

答案文件（small13.out） 

1

用户输出 

1

系统信息 

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

输入文件（small14.in） 

14 53

答案文件（small14.out） 

12

用户输出 

12

系统信息 

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

输入文件（small15.in） 

15 51

答案文件（small15.out） 

47

用户输出 

47

系统信息 

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

输入文件（small16.in） 

16 26

答案文件（small16.out） 

24

用户输出 

24

系统信息 

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

输入文件（small17.in） 

17 70

答案文件（small17.out） 

44

用户输出 

44

系统信息 

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

输入文件（small18.in） 

18 36

答案文件（small18.out） 

20

用户输出 

20

系统信息 

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

输入文件（small19.in） 

19 64

答案文件（small19.out） 

42

用户输出 

42

系统信息 

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

输入文件（small20.in） 

20 89

答案文件（small20.out） 

2

用户输出 

2

系统信息 

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

输入文件（big1.in） 

18446744073709551615 7994

答案文件（big1.out） 

5770

用户输出 

5770

系统信息 

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

输入文件（big2.in） 

18446744073709551614 29078

答案文件（big2.out） 

27662

用户输出 

27662

系统信息 

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

输入文件（big3.in） 

18446744073709551613 19605

答案文件（big3.out） 

8791

用户输出 

8791

系统信息 

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

输入文件（big4.in） 

18446744073709551612 12114

答案文件（big4.out） 

6732

用户输出 

6732

系统信息 

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

输入文件（big5.in） 

18446744073709551611 11803

答案文件（big5.out） 

1454

用户输出 

1454

系统信息 

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

输入文件（big6.in） 

18446744073709551610 30259

答案文件（big6.out） 

3790

用户输出 

3790

系统信息 

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

输入文件（big7.in） 

18446744073709551609 25670

答案文件（big7.out） 

68

用户输出 

68

系统信息 

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

输入文件（big8.in） 

18446744073709551608 19432

答案文件（big8.out） 

11690

用户输出 

11690

系统信息 

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

输入文件（big9.in） 

18446744073709551607 12450

答案文件（big9.out） 

26

用户输出 

26

系统信息 

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

输入文件（big10.in） 

18446744073709551606 23556

答案文件（big10.out） 

16

用户输出 

16

系统信息 

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

输入文件（big11.in） 

18446744073709551605 2015

答案文件（big11.out） 

10

用户输出 

10

系统信息 

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

输入文件（big12.in） 

18446744073709551604 2613

答案文件（big12.out） 

2151

用户输出 

2151

系统信息 

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

输入文件（big13.in） 

18446744073709551603 432

答案文件（big13.out） 

4

用户输出 

4

系统信息 

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

输入文件（big14.in） 

18446744073709551602 12087

答案文件（big14.out） 

2

用户输出 

2

系统信息 

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

输入文件（big15.in） 

18446744073709551601 31850

答案文件（big15.out） 

2

用户输出 

2

系统信息 

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

输入文件（big16.in） 

18446744073709551600 7791

答案文件（big16.out） 

1617

用户输出 

1617

系统信息 

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

输入文件（big17.in） 

18446744073709551599 15029

答案文件（big17.out） 

10509

用户输出 

10509

系统信息 

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

输入文件（big18.in） 

18446744073709551598 16723

答案文件（big18.out） 

4380

用户输出 

4380

系统信息 

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

输入文件（big19.in） 

18446744073709551597 13276

答案文件（big19.out） 

2560

用户输出 

2560

系统信息 

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

输入文件（big20.in） 

18446744073709551596 16130

答案文件（big20.out） 

6434

用户输出 

6434

系统信息 

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

输入文件（random1.in） 

4464892338285178880 21466

答案文件（random1.out） 

1938

用户输出 

1938

系统信息 

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

输入文件（random2.in） 

4427736507453402112 13663

答案文件（random2.out） 

10705

用户输出 

10705

系统信息 

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

输入文件（random3.in） 

6999370374719408128 21187

答案文件（random3.out） 

9350

用户输出 

9350

系统信息 

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

输入文件（random4.in） 

18053230047173007360 9514

答案文件（random4.out） 

8076

用户输出 

8076

系统信息 

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

输入文件（random5.in） 

14866836069781237760 9298

答案文件（random5.out） 

7210

用户输出 

7210

系统信息 

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

输入文件（random6.in） 

2715753453522595328 1776

答案文件（random6.out） 

666

用户输出 

666

系统信息 

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

输入文件（random7.in） 

3252261132048099840 25387

答案文件（random7.out） 

16089

用户输出 

16089

系统信息 

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

输入文件（random8.in） 

1921969794843727104 6047

答案文件（random8.out） 

5065

用户输出 

5065

系统信息 

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

输入文件（random9.in） 

16761783442201856000 27092

答案文件（random9.out） 

9362

用户输出 

9362

系统信息 

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

输入文件（random10.in） 

6339009926754648064 27913

答案文件（random10.out） 

9370

用户输出 

9370

系统信息 

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

输入文件（random13.in） 

8136563985025304576 6853

答案文件（random13.out） 

4361

用户输出 

4361

系统信息 

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

输入文件（random14.in） 

4821813501123762176 29237

答案文件（random14.out） 

11702

用户输出 

11702

系统信息 

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

输入文件（random15.in） 

10441914397996910592 18286

答案文件（random15.out） 

13980

用户输出 

13980

系统信息 

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

输入文件（random16.in） 

16686345846270672896 10136

答案文件（random16.out） 

1442

用户输出 

1442

系统信息 

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

输入文件（random17.in） 

501040749095172032 25615

答案文件（random17.out） 

24628

用户输出 

24628

系统信息 

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

输入文件（random18.in） 

3320380155239690240 11168

答案文件（random18.out） 

6954

用户输出 

6954

系统信息 

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

输入文件（random19.in） 

4927651322280944640 10939

答案文件（random19.out） 

5562

用户输出 

5562

系统信息 

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

输入文件（random20.in） 

16261305660240498688 21014

答案文件（random20.out） 

5250

用户输出 

5250

系统信息 

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