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分题解。