202006-4 1246

思路：

这道题一开始还是暴力，得了32分。讲真的也是通过这道题了解到了矩阵快速幂这个算法，感觉在dp算法中非常好用，感谢CSP。

这里我只考虑S = 2的情况，看上一步有哪一个数能够到这一步来，然后每一次迭代就可以了，这就是递推，也是矩阵快速幂的用处。

代码：

#include 
#include 
#include 
#include 
using namespace std;
const int N = 14; 
const int mod = 998244353;
typedef long long ll;
vector<int> ver = {1, 2, 4, 6, 16, 26, 41, 42, 44, 46, 61, 62, 64, 66};
int idx[100];//离散化
vectorint>> g = {
{2}, {4}, {1,6,16}, {6,4,64}, {26}, {46}, {62}, {64}, {61}, {66}, {42}, {44}, {41}, {46} };
int tr[N][N];//转移矩阵 
int n;
string s;
void init(){
    memset(idx, -1, sizeof(idx));//初始化
    for(int i = 0;i){
//        int num = ver[i];
        idx[ver[i]] = i;//离散化
    }
    //得到转移矩阵
    for(int i = 0;i){
        for(auto t:g[i]){
            int num = t;
            int b = idx[t];
            tr[idx[t]][i]++;//如果t可以由i转过来，那么第n次的t的个数由第n - 1次的i的个数决定 
        }
    }
}
int res[N][N];
void mul(int c[][N], int a[][N], int b[][N]){
    int tmp[N][N];
    memset(tmp, 0, sizeof(tmp));
    for(int i = 0;i){
        for(int j = 0;j){
            for(int k = 0;k){
                tmp[i][j] = (tmp[i][j] + (ll)a[i][k] * b[k][j])%mod;
            }
        }
    }
    memcpy(c, tmp, sizeof(tmp));
}
int qmi(int k, int id){
    int w[N][N];
    memcpy(w, tr, sizeof(w));
    res[0][0] = 1;
    while(k){
        if(k & 1)mul(res, w, res);
        mul(w,w,w);
        k>>=1;
    }
    return res[idx[id]][0];
}
int main(){
    cin>>n;
    cin>>s;
    init();
    cout<endl;

}