<commit_before>---
layout: post
title: BZOJ2326/HNOI2011/数学作业
tags: [OI,矩阵]
category: OI
---

构造一个单位矩阵

然后构造下面这个矩阵

$$
\left(\begin{array}{ccc}10 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)
$$

然后往后面加一位数，就相当于将这个矩阵乘了一次

这样做完了1~9，下面处理10~99

构造下面这个矩阵

$$
\left(\begin{array}{ccc}100 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)
$$

这样做完了10~99，下面处理100~999

构造下面这个矩阵

$$
\left(\begin{array}{ccc}1000 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)
$$

……以此类推，共乘n次，最后加上快速幂即可

4ms AC

AC-Code：

{% highlight c++ %}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long N,MOD;
struct Mat{
    long long A[3][3];
}S[20],ans;
Mat operator * (Mat a,Mat b)
{
    Mat ret;
    ret.A[0][0]=(a.A[0][0]*b.A[0][0]+a.A[0][1]*b.A[1][0]+a.A[0][2]*b.A[2][0])%MOD;
    ret.A[0][1]=(a.A[0][0]*b.A[0][1]+a.A[0][1]*b.A[1][1]+a.A[0][2]*b.A[2][1])%MOD;
    ret.A[0][2]=(a.A[0][0]*b.A[0][2]+a.A[0][1]*b.A[1][2]+a.A[0][2]*b.A[2][2])%MOD;
     
    ret.A[1][0]=(a.A[1][0]*b.A[0][0]+a.A[1][1]*b.A[1][0]+a.A[1][2]*b.A[2][0])%MOD;
    ret.A[1][1]=(a.A[1][0]*b.A[0][1]+a.A[1][1]*b.A[1][1]+a.A[1][2]*b.A[2][1])%MOD;
    ret.A[1][2]=(a.A[1][0]*b.A[0][2]+a.A[1][1]*b.A[1][2]+a.A[1][2]*b.A[2][2])%MOD;
     
    ret.A[2][0]=(a.A[2][0]*b.A[0][0]+a.A[2][1]*b.A[1][0]+a.A[2][2]*b.A[2][0])%MOD;
    ret.A[2][1]=(a.A[2][0]*b.A[0][1]+a.A[2][1]*b.A[1][1]+a.A[2][2]*b.A[2][1])%MOD;
    ret.A[2][2]=(a.A[2][0]*b.A[0][2]+a.A[2][1]*b.A[1][2]+a.A[2][2]*b.A[2][2])%MOD;
    return ret;
}
void init()
{
    S[1].A[0][0]=10%MOD;
    S[1].A[1][0]=1;
    S[1].A[1][1]=1;
    S[1].A[2][0]=1;
    S[1].A[2][1]=1;
    S[1].A[2][2]=1;
    ans.A[0][0]=1;
    ans.A[1][1]=1;
    ans.A[2][2]=1;
    for (int i=2;i<20;i++)
    {
        S[i]=S[i-1];
        S[i].A[0][0]*=10;
        S[i].A[0][0]%=MOD;
    }
}
Mat Ksm(Mat a,long long k)
{
    Mat ret;
    ret.A[0][0]=ret.A[1][1]=ret.A[2][2]=1;
    if (k==0)
        return ret;
    if (k==1)
        return a;
    if (k%2==0)
    {
        ret=Ksm(a,k/2);
        return ret*ret;
    }else
    {
        ret=Ksm(a,k-1);
        return ret*a;
    }
}
int main()
{
    long long begin=1,i,nn,len=0,k=1;
    scanf("%lld%lld",&N,&MOD);
    init();
    nn=N;
    while (nn)
    {
        nn/=10;
        len++;
    }
    for (i=1;i<len;i++)
    {
        ans=ans*Ksm(S[i],k*9);
        k*=10;
    }
    //cerr<<k<<"-"<<len<<endl;
    ans=ans*Ksm(S[len],N-k+1);
    printf("%lld\n",ans.A[2][0]);
    return 0;
}
{% endhighlight %}<commit_msg>201301202158<commit_after>---
layout: post
title: BZOJ2326/HNOI2011/数学作业
tags: [OI,矩阵]
category: OI
---

构造一个单位矩阵

然后构造下面这个矩阵

$$
\left(\begin{array}{ccc}10 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)
$$

然后往后面加一位数，就相当于将这个矩阵乘了一次

这样做完了1~9，下面处理10~99

构造下面这个矩阵

$$
\left(\begin{array}{ccc}100 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)
$$

这样做完了10~99，下面处理100~999

构造下面这个矩阵

$$
\left(\begin{array}{ccc}1000 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)
$$

……以此类推，共乘n次，最后加上快速幂即可

4ms AC

AC-Code：

{% highlight c++ %}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long N,MOD;
struct Mat{
    long long A[3][3];
}S[20],ans;
Mat operator * (Mat a,Mat b)
{
    Mat ret;
    ret.A[0][0]=(a.A[0][0]*b.A[0][0]+a.A[0][1]*b.A[1][0]+a.A[0][2]*b.A[2][0])%MOD;
    ret.A[0][1]=(a.A[0][0]*b.A[0][1]+a.A[0][1]*b.A[1][1]+a.A[0][2]*b.A[2][1])%MOD;
    ret.A[0][2]=(a.A[0][0]*b.A[0][2]+a.A[0][1]*b.A[1][2]+a.A[0][2]*b.A[2][2])%MOD;
     
    ret.A[1][0]=(a.A[1][0]*b.A[0][0]+a.A[1][1]*b.A[1][0]+a.A[1][2]*b.A[2][0])%MOD;
    ret.A[1][1]=(a.A[1][0]*b.A[0][1]+a.A[1][1]*b.A[1][1]+a.A[1][2]*b.A[2][1])%MOD;
    ret.A[1][2]=(a.A[1][0]*b.A[0][2]+a.A[1][1]*b.A[1][2]+a.A[1][2]*b.A[2][2])%MOD;
     
    ret.A[2][0]=(a.A[2][0]*b.A[0][0]+a.A[2][1]*b.A[1][0]+a.A[2][2]*b.A[2][0])%MOD;
    ret.A[2][1]=(a.A[2][0]*b.A[0][1]+a.A[2][1]*b.A[1][1]+a.A[2][2]*b.A[2][1])%MOD;
    ret.A[2][2]=(a.A[2][0]*b.A[0][2]+a.A[2][1]*b.A[1][2]+a.A[2][2]*b.A[2][2])%MOD;
    return ret;
}
void init()
{
    S[1].A[0][0]=10%MOD;
    S[1].A[1][0]=1;
    S[1].A[1][1]=1;
    S[1].A[2][0]=1;
    S[1].A[2][1]=1;
    S[1].A[2][2]=1;
    ans.A[0][0]=1;
    ans.A[1][1]=1;
    ans.A[2][2]=1;
    for (int i=2;i<20;i++)
    {
        S[i]=S[i-1];
        S[i].A[0][0]*=10;
        S[i].A[0][0]%=MOD;
    }
}
Mat Ksm(Mat a,long long k)
{
    Mat ret;
    ret.A[0][0]=ret.A[1][1]=ret.A[2][2]=1;
    if (k==0)
        return ret;
    if (k==1)
        return a;
    if (k%2==0)
    {
        ret=Ksm(a,k/2);
        return ret*ret;
    }else
    {
        ret=Ksm(a,k-1);
        return ret*a;
    }
}
int main()
{
    long long begin=1,i,nn,len=0,k=1;
    scanf("%lld%lld",&N,&MOD);
    init();
    nn=N;
    while (nn)
    {
        nn/=10;
        len++;
    }
    for (i=1;i<len;i++)
    {
        ans=ans*Ksm(S[i],k*9);
        k*=10;
    }
    ans=ans*Ksm(S[len],N-k+1);
    printf("%lld\n",ans.A[2][0]);
    return 0;
}
{% endhighlight %}
{'fraction_non_alphanumeric': 0.3334679047234558, 'fraction_numerical': 0.1065805409769883, 'mean_word_length': 2.92319873317498, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4024993', 'n_tokens_mistral': 3060, 'n_tokens_neox': 2990, 'n_words': 301}