XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#22803 #1029. 寒域爷的兔子 Accepted 100 136 ms 360 K C++ / 1.4 K 机类910-尚锦奥 2020-02-14 20:45:03
显示原始代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#define lson node << 1
#define rson node << 1 | 1
using namespace std;
#define ll unsigned long long
const ll maxn = 5e5 + 10;
ll read() {
    char c = getchar();
    ll x = 0;
    ll flag = 1;
    while (c < '0' || c > '9') {
        if (c == '-')
            flag = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - 48;
        c = getchar();
    }
    x *= flag;
    return x;
}
struct node {
    ll p[4][4];
};
ll n, mod;
node cheng(node x, node y, int a, int b, int c) {
    node d;
    memset(&d, 0, sizeof(node));
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= c; j++) {
            for (int k = 1; k <= b; k++) {
                (d.p[i][j] += x.p[i][k] % mod * y.p[k][j] % mod) %= mod;
            }
        }
    }
    return d;
}
node pow4(node a, ll b) {
    b -= 1;
    node base = a, r;
    memset(r.p, 0, sizeof(r.p));
    for (int i = 1; i <= 3; i++) r.p[i][i] = 1;
    while (b > 0) {
        if (b & 1LL)
            r = cheng(r, base, 3, 3, 3);
        base = cheng(base, base, 3, 3, 3);
        b >>= 1LL;
    }
    return r;
}
int main() {
    n = read(), mod = read();
    node a, b, c;
    memset(&a, 0, sizeof(node));
    memset(&b, 0, sizeof(node));
    memset(&c, 0, sizeof(node));
    a.p[1][1] = 2;
    a.p[2][1] = 2;
    a.p[3][1] = 0;
    b.p[1][1] = 1;
    b.p[1][2] = 1;
    b.p[2][1] = 1;
    b.p[3][2] = 1;
    c = pow4(b, n);
    a = cheng(c, a, 3, 3, 1);
    printf("%lld", (a.p[2][1] + mod) % mod);
    return 0;
}
子任务 #1
Accepted
得分：30
测试点 #1
Accepted
得分：100
用时：3 ms
内存：352 KiB

输入文件（small1.in） 

1 74

答案文件（small1.out） 

2

用户输出 

2

系统信息 

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

输入文件（small2.in） 

2 69

答案文件（small2.out） 

2

用户输出 

2

系统信息 

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

输入文件（small3.in） 

3 4

答案文件（small3.out） 

0

用户输出 

0

系统信息 

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

输入文件（small4.in） 

4 18

答案文件（small4.out） 

6

用户输出 

6

系统信息 

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

输入文件（small5.in） 

5 99

答案文件（small5.out） 

10

用户输出 

10

系统信息 

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

输入文件（small6.in） 

6 29

答案文件（small6.out） 

16

用户输出 

16

系统信息 

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

输入文件（small7.in） 

7 43

答案文件（small7.out） 

26

用户输出 

26

系统信息 

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

输入文件（small8.in） 

8 40

答案文件（small8.out） 

2

用户输出 

2

系统信息 

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

输入文件（small9.in） 

9 52

答案文件（small9.out） 

16

用户输出 

16

系统信息 

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

输入文件（small10.in） 

10 53

答案文件（small10.out） 

4

用户输出 

4

系统信息 

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

输入文件（small11.in） 

11 37

答案文件（small11.out） 

30

用户输出 

30

系统信息 

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

输入文件（small12.in） 

12 45

答案文件（small12.out） 

18

用户输出 

18

系统信息 

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

输入文件（small13.in） 

13 5

答案文件（small13.out） 

1

用户输出 

1

系统信息 

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

输入文件（small14.in） 

14 53

答案文件（small14.out） 

12

用户输出 

12

系统信息 

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

输入文件（small15.in） 

15 51

答案文件（small15.out） 

47

用户输出 

47

系统信息 

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

输入文件（small16.in） 

16 26

答案文件（small16.out） 

24

用户输出 

24

系统信息 

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

输入文件（small17.in） 

17 70

答案文件（small17.out） 

44

用户输出 

44

系统信息 

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

输入文件（small18.in） 

18 36

答案文件（small18.out） 

20

用户输出 

20

系统信息 

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

输入文件（small19.in） 

19 64

答案文件（small19.out） 

42

用户输出 

42

系统信息 

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

输入文件（small20.in） 

20 89

答案文件（small20.out） 

2

用户输出 

2

系统信息 

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

输入文件（big1.in） 

18446744073709551615 7994

答案文件（big1.out） 

5770

用户输出 

5770

系统信息 

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

输入文件（big2.in） 

18446744073709551614 29078

答案文件（big2.out） 

27662

用户输出 

27662

系统信息 

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

输入文件（big3.in） 

18446744073709551613 19605

答案文件（big3.out） 

8791

用户输出 

8791

系统信息 

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

输入文件（big4.in） 

18446744073709551612 12114

答案文件（big4.out） 

6732

用户输出 

6732

系统信息 

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

输入文件（big5.in） 

18446744073709551611 11803

答案文件（big5.out） 

1454

用户输出 

1454

系统信息 

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

输入文件（big6.in） 

18446744073709551610 30259

答案文件（big6.out） 

3790

用户输出 

3790

系统信息 

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

输入文件（big7.in） 

18446744073709551609 25670

答案文件（big7.out） 

68

用户输出 

68

系统信息 

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

输入文件（big8.in） 

18446744073709551608 19432

答案文件（big8.out） 

11690

用户输出 

11690

系统信息 

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

输入文件（big9.in） 

18446744073709551607 12450

答案文件（big9.out） 

26

用户输出 

26

系统信息 

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

输入文件（big10.in） 

18446744073709551606 23556

答案文件（big10.out） 

16

用户输出 

16

系统信息 

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

输入文件（big11.in） 

18446744073709551605 2015

答案文件（big11.out） 

10

用户输出 

10

系统信息 

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

输入文件（big12.in） 

18446744073709551604 2613

答案文件（big12.out） 

2151

用户输出 

2151

系统信息 

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

输入文件（big13.in） 

18446744073709551603 432

答案文件（big13.out） 

4

用户输出 

4

系统信息 

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

输入文件（big14.in） 

18446744073709551602 12087

答案文件（big14.out） 

2

用户输出 

2

系统信息 

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

输入文件（big15.in） 

18446744073709551601 31850

答案文件（big15.out） 

2

用户输出 

2

系统信息 

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

输入文件（big16.in） 

18446744073709551600 7791

答案文件（big16.out） 

1617

用户输出 

1617

系统信息 

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

输入文件（big17.in） 

18446744073709551599 15029

答案文件（big17.out） 

10509

用户输出 

10509

系统信息 

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

输入文件（big20.in） 

18446744073709551596 16130

答案文件（big20.out） 

6434

用户输出 

6434

系统信息 

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

输入文件（random1.in） 

4464892338285178880 21466

答案文件（random1.out） 

1938

用户输出 

1938

系统信息 

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

输入文件（random2.in） 

4427736507453402112 13663

答案文件（random2.out） 

10705

用户输出 

10705

系统信息 

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

输入文件（random3.in） 

6999370374719408128 21187

答案文件（random3.out） 

9350

用户输出 

9350

系统信息 

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

输入文件（random4.in） 

18053230047173007360 9514

答案文件（random4.out） 

8076

用户输出 

8076

系统信息 

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

输入文件（random5.in） 

14866836069781237760 9298

答案文件（random5.out） 

7210

用户输出 

7210

系统信息 

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

输入文件（random6.in） 

2715753453522595328 1776

答案文件（random6.out） 

666

用户输出 

666

系统信息 

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

输入文件（random7.in） 

3252261132048099840 25387

答案文件（random7.out） 

16089

用户输出 

16089

系统信息 

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

输入文件（random8.in） 

1921969794843727104 6047

答案文件（random8.out） 

5065

用户输出 

5065

系统信息 

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

输入文件（random9.in） 

16761783442201856000 27092

答案文件（random9.out） 

9362

用户输出 

9362

系统信息 

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

输入文件（random10.in） 

6339009926754648064 27913

答案文件（random10.out） 

9370

用户输出 

9370

系统信息 

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

输入文件（random11.in） 

610256373055243264 7367

答案文件（random11.out） 

4198

用户输出 

4198

系统信息 

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

输入文件（random12.in） 

7087193247594517504 12437

答案文件（random12.out） 

4041

用户输出 

4041

系统信息 

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

输入文件（random13.in） 

8136563985025304576 6853

答案文件（random13.out） 

4361

用户输出 

4361

系统信息 

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

输入文件（random14.in） 

4821813501123762176 29237

答案文件（random14.out） 

11702

用户输出 

11702

系统信息 

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

输入文件（random15.in） 

10441914397996910592 18286

答案文件（random15.out） 

13980

用户输出 

13980

系统信息 

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

输入文件（random16.in） 

16686345846270672896 10136

答案文件（random16.out） 

1442

用户输出 

1442

系统信息 

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

输入文件（random17.in） 

501040749095172032 25615

答案文件（random17.out） 

24628

用户输出 

24628

系统信息 

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

输入文件（random18.in） 

3320380155239690240 11168

答案文件（random18.out） 

6954

用户输出 

6954

系统信息 

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

输入文件（random19.in） 

4927651322280944640 10939

答案文件（random19.out） 

5562

用户输出 

5562

系统信息 

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

输入文件（random20.in） 

16261305660240498688 21014

答案文件（random20.out） 

5250

用户输出 

5250

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.