[数据结构与算法]CSP 202006-4 1246

2022.2.23 ~ 24 学习 CSP 202006-4 1246

此题参考博客：
CSP 1246，线性代数的知识还可以这么用
ccf 1246 最详细的菜鸟解析
202006-4 CCF CSP认证 1246(digits) 96分 动态规划
第 19 次 CCF CSP 认证 202006-4 1246（digits）

学习矩阵快速幂：
根据线性递推的DP公式如何写出变换矩阵
矩阵快速幂（附模板）
快速幂和矩阵快速幂(取模)算法

暴力求解 28分代码：

#include <bits/stdc++.h>
using namespace std;
int n,s;
const int MAX_NUM=10e8;
map<int,string> cc;

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>s;

    stringstream stmp;
    stmp<<s;
    string ss=stmp.str();
    int l=ss.length();

    cc[1]="2";
    cc[2]="4";
    cc[3]="16";
    cc[4]="264";
    cc[5]="46416";
    int len=1;

    for(int i=6;i<=n;i++)
    {
        cc[i]+=cc[i-3];
        len=cc[i-4].length();
        cc[i]+=cc[i-1].substr(len);
        cc[i]+=cc[i-2];
    }
    long long int sum=0;
    string str=cc[n];
    //cout<<str<<endl;
    while(str.find(ss,0)!=string::npos)
    {
        long long int start=str.find(ss,0);
        sum++;
        sum%=998244353;
        str.erase(0,start+l);
    }
    cout<<sum<<endl;
    return 0;
}

使用矩阵快速幂 96分代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;

struct mat
{
    ll m[15][15];
}unit;

void init()
{
    for(int i=1;i<=14;i++)
    {
        unit.m[i][i]=1;//单位矩阵，任何矩阵与单位矩阵相乘等于本身
    }
}

mat matmul(mat a,mat b)
{
    mat res;
    ll tmp;
    for(int i=1;i<=14;i++)
    {
        for(int j=1;j<=14;j++)
        {
            tmp=0;
            for(int k=1;k<=14;k++)
            {
                tmp=(tmp%mod+((a.m[i][k]%mod)*(b.m[k][j]%mod))%mod)%mod;
            }
            res.m[i][j]=tmp;
        }
    }
    return res;
}

mat quickpow(mat a ,ll n)
{
    init();
    mat res=unit;
    while(n)
    {
        if(n&1)
            res=matmul(res,a);
        a=matmul(a,a);
        n>>=1;
    }
    return res;
}

map<string,int> dp;
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    string s;
    cin>>n>>s;

    dp["1"]=1;         dp["42"]=8;
    dp["2"]=2;         dp["44"]=9;
    dp["4"]=3;         dp["46"]=10;
    dp["6"]=4;         dp["61"]=11;
    dp["16"]=5;        dp["62"]=12;
    dp["26"]=6;        dp["64"]=13;
    dp["41"]=7;        dp["66"]=14;

    mat a=
    {{
        // 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 , 1 , 2 , 3 , 4
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//0
         { 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//1
         { 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//2
         { 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//3
         { 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//4
         { 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//5
         { 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//6
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 },//7
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 },//8
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 },//9
         { 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 },//10
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 },//11
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//12
         { 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 },//13
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 },//14
    }};
    mat res=quickpow(a,n);
    ll sum=0;
    int num=dp[s];
    sum=res.m[num][1]%mod;
    cout<<sum<<endl;
    return 0;
}

关于以上96分代码的结果sum=ans.m[num][1]%mod;的解释：

参考此博客：CSP 1246，线性代数的知识还可以这么用

即sum=ans.m[num][1]%mod;等价于经过n轮变换（即经过n秒）的矩阵乘以另一个表示字符串开始只有1的矩阵：

 mat b=
    {{
        // 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 , 1 , 2 , 3 , 4
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//0
         { 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//1
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//2
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//3
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//4
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//5
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//6
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//7
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//8
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//9
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//10
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//11
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//12
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//13
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//14
    }};

------------------------------------------------假装分割------------------------------------------------

我的分析：

由此写出地推关系如下：

写出变换矩阵

mat a=
    {{
        // 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 , 1 , 2 , 3 , 4
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//0
         { 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//1
         { 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//2
         { 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//3
         { 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//4
         { 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//5
         { 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//6
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 },//7
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 },//8
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 },//9
         { 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 },//10
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 },//11
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 },//12
         { 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 },//13
         { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 },//14
    }};