CSP 202006-4 1246

48分题解:|S|=1
推导:
1->2
2->4
4->{1,6}
6->{6,4}
则有:
a1’=a4
a2’=a1
a4’=a2+a6
a6’=a4+a6
矩阵快速幂:
$$
\begin{bmatrix}
a_{1}^{\prime} \\
a_{2}^{\prime} \\
a_{4}^{\prime} \\
a_{6}^{\prime}
\end{bmatrix} =
\begin{bmatrix}
a_4 \\
a_1 \\
a_2 + a_6 \\
a_4 + a_6
\end{bmatrix} =
\begin{bmatrix}
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1
\end{bmatrix} *
\begin{bmatrix}
a_1 \\
a_2 \\
a_4 \\
a_6
\end{bmatrix}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

const long long MOD = 998244353;
const int maxtrixN = 4;

struct matrix {
    long long arr[maxtrixN][maxtrixN];
    matrix operator * (const matrix& m2) {
        matrix result;
        long long(&arr)[maxtrixN][maxtrixN] = result.arr;
        const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;
        const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;
        for (int i = 0; i < maxtrixN; i++) {
            for (int j = 0; j < maxtrixN; j++) {
                arr[i][j] = 0;
                for (int k = 0; k < maxtrixN; k++) {
                    arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;
                    arr[i][j] += MOD;
                    arr[i][j] %= MOD;
                }
            }
        }
        return result;
    }
};
const matrix c = { 0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,1 };
matrix quickpow(long long n) {
    if (n == 1)return c;
    matrix half = quickpow(n / 2);
    matrix result = half * half;
    if (n & 1)result = result * c;
    return result;
}
long long getResult(long long n, int index){
    matrix re=quickpow(n);
    return re.arr[index][0] % MOD;
}
int main() {
    ios::sync_with_stdio(false);
    long long n, s;
    cin>>n>>s;
    if(n==0){
        if(s==1){
            cout<<"1";
        }else{
            cout<<"0";
        }
    }else if(s==1){
        cout<<getResult(n, 0);
    }else if(s==2){
        cout<<getResult(n, 1);
    }else if(s==4){
        cout<<getResult(n, 2);
    }else if(s==6){
        cout<<getResult(n, 3);
    }
}

待完善96分题解。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注