CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#16765 #1068. marble的神秘数列 Accepted 100 24 ms 288 K C / 1.4 K C192022211917 2024-03-16 17:34:07
显示原始代码 
#include <stdio.h>

#define MOD 1000000007


typedef struct {
    long long mat[3][3];
} Matrix;

Matrix matrix_multiply(Matrix a, Matrix b) {
    Matrix result;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            result.mat[i][j] = 0;
            for (int k = 0; k < 3; k++) {
                result.mat[i][j] += a.mat[i][k] * b.mat[k][j];
                result.mat[i][j] %= MOD;
            }
        }
    }
    return result;
}

Matrix matrix_power(Matrix m, long long p) {
    Matrix result = { { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } } };
    while (p) {
        if (p % 2) {
            result = matrix_multiply(result, m);
        }
        m = matrix_multiply(m, m);
        p /= 2;
    }
    return result;
}

long long calculate_nth_term(long long n) {
    if (n <= 3) {
        return 1;
    }
    Matrix T = { { { 3, 2, 6 }, { 1, 0, 0 }, { 0, 1, 0 } } };
    Matrix T_n_minus_3 = matrix_power(T, n - 3);
    long long initial_vector[3] = { 1, 1, 1 };
    long long result = 0;
    for (int i = 0; i < 3; i++) {
        result += T_n_minus_3.mat[0][i] * initial_vector[i];
        result %= MOD;
    }
    return result;
}

int main() {
    int group;
    scanf("%d", &group);
    while (group > 0) {
        long long n;
        scanf("%lld", &n);
        printf("%lld\n", calculate_nth_term(n));
        group--;
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：3 ms
内存：288 KiB

输入文件（1.in） 

10
11
17
19
11
13
14
17
13
19
19

答案文件（1.out） 

139801
496049801
566111912
139801
2132201
8327311
496049801
2132201
566111912
566111912

用户输出 

139801
496049801
566111912
139801
2132201
8327311
496049801
2132201
566111912
566111912

系统信息 

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

输入文件（2.in） 

1
1000000000000

答案文件（2.out） 

766558950

用户输出 

766558950

系统信息 

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

输入文件（3.in） 

200
107
109
102
104
101
101
106
103
101
102
107
108
106
104
109
109
100
104
102

<905 bytes omitted>

答案文件（3.out） 

278955700
205147008
394967193
653501850
867217024
867217024
938991160
220088454
867217024
3
<2100 bytes omitted>

用户输出 

278955700
205147008
394967193
653501850
867217024
867217024
938991160
220088454
867217024
394967193
278955700
337762899
93899116
<1872 bytes omitted>

系统信息 

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

输入文件（4.in） 

200
100000000000
100000000001
100000000002
100000000002
100000000002
100000000003
10000000000
<2705 bytes omitted>

答案文件（4.out） 

633333609
837070975
105869815
105869815
105869815
791753014
81629173
68233424
110361915
105
<2038 bytes omitted>

用户输出 

633333609
837070975
105869815
105869815
105869815
791753014
81629173
68233424
110361915
105869815
609424473
81629173
68233424
74
<1810 bytes omitted>

系统信息 

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

输入文件（5.in） 

2000
100000004856
100000006023
100000005478
100000002179
100000002702
100000008791
1000000096
<27906 bytes omitted>

答案文件（5.out） 

788342402
673152542
900221201
556210152
622627458
620137684
908500589
608503598
862354892
6
<21655 bytes omitted>

用户输出 

788342402
673152542
900221201
556210152
622627458
620137684
908500589
608503598
862354892
628707532
30858809
271008719
769897208
<19627 bytes omitted>

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.