解题思路
正解:找规律+快速幂
暴力代码 过8个数据
找规律
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <string>
using namespace std;
typedef long long LL;
const int MOD=998244353;
string num[6][4];
string f[2][4];
string pat;
int n;
LL search(string current)
{
LL cnt=0;
for(int i=0;i<current.size();i++)
{
if(current[i]==pat[0])
{
int j=i,k=0;
while(current[j]==pat[k]&&k<pat.size())
{
j++,k++;
}
if(k==pat.size())
cnt++;
}
cnt=cnt%MOD;
}
return cnt;
}
int main()
{
cin>>n;
cin>>pat;
num[1][0]="2";
num[2][0]="4";
num[3][0]="1",num[3][1]="6";
num[4][0]="2",num[4][1]="6",num[4][2]="4";
num[5][0]="4",num[5][1]="6",num[5][2]="4",num[5][3]="16";
if(n<=5)
{
string current;
for(auto t:num[n])
current+=t;
cout<<search(current);
}
else
{
f[0][0]="2",f[0][1]="6",f[0][2]="4",f[0][3]="";
f[1][0]="4",f[1][1]="6",f[1][2]="4",f[1][3]="16";
for(int i=5;i<n;i++)
{
string temp;
for(int j=0;j<4;j++)
temp+=f[0][j];
for(int j=0;j<4;j++)
f[0][j]=f[1][j];
f[1][0]=f[1][3],f[1][1]=f[1][1]+f[1][2],f[1][2]=f[1][3],f[1][3]=temp;
}
string a;
for(auto t:f[1])
a+=t;
cout<<search(a);
}
return 0;
}
矩阵乘法+快速幂(过24个点)
思路:枚举所有可能出现的一位数和两位数的转移情况,这一层的个数由上一层个数决定
复习矩阵乘法+快速幂
为什么矩阵乘法要有static int tmp[N][N]
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N=14,MOD=998244353;
int n;
string S;
int ids[100];
int tr[N][N];
vector<int> vers{
1,2,4,6,16,26,41,42,44,46,61,62,64,66
};
vector<vector<int>> g{
{2},{4},{1,6,16},{64,6,4},{26},{46},{62},{64},{61},{66},{42},
{44},{41},{46}
};
void init()
{
memset(ids,-1,sizeof ids);
for(int i=0;i<N;i++)
ids[vers[i]]=i;
for(int i=0;i<N;i++)
for(auto t:g[i])
{
tr[i][ids[t]]=1;
}
}
void mul(int c[][N], int a[][N], int b[][N])
{
static int tmp[N][N];
memset(tmp, 0, sizeof tmp);
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
for (int k = 0; k < N; k ++ )
tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % MOD;
memcpy(c, tmp, sizeof tmp);
}
LL qmi(int k,int id)
{
if(id==-1)
return 0;
int res[N][N]={0},w[N][N];
memcpy(w,tr,sizeof w);
res[0][0]=1;
while(k)
{
if(k&1)
mul(res,res,w);
mul(w,w,w);
k>>=1;
}
return res[0][id];
}
int main()
{
cin>>n>>S;
init();
cout<<qmi(n,ids[stoi(S)]);
return 0;
}
AC代码