牛客练习赛80 C-不降数

题目见链接。

令f[i][j]表示长度为i的数字，最高位为j的不降数有多少种。

其他=0;
f[1][1→9]=1;
f[i][j]=Σf[i-1][1→j];

n的数据范围小一些可以用前缀和慢慢加，10^8就只能用矩阵快速幂加速了。
构造A矩阵(9,9)第一行全1，其余全0；B矩阵(9,9)上三角区域内全1，其余全0；
令Ans=AB^n,所求答案即为Ans[1][9]

#include<bits/stdc++.h>
#define P 100019
#define ll long long
using namespace std;
struct Mat
{
    ll m[10][10];
}a,f;
Mat mulmy(Mat a,Mat b)
{
    Mat c;
    int i,j,k;
    memset(c.m,0,sizeof(c.m));
    for(i=1;i<10;++i)
           for(j=1;j<10;++j)
            for(k=1;k<10;++k)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%P;
    return c;
}
Mat qmimy(Mat s,long long b)
{
    Mat ans;
    //register int i,j,k;
    memset(ans.m,0,sizeof(ans.m));
    for(int i=1;i<10;++i)
    {
        ans.m[i][i]=1;
    }
    while(b)
    {
        if(b&1) ans=mulmy(ans,s);
        s=mulmy(s,s);
        b>>=1;
    }
    return ans;
} 
int  main()
{
    memset(f.m,0,sizeof(f.m));
    memset(a.m,0,sizeof(a.m));
    for(int i=1;i<10;++i)
    {
        for(int j=i;j<10;++j)
        {
            f.m[i][j]=1;
        }
    }
    for(int i=1;i<10;++i)
    {
        a.m[1][i]=1;
    }
    long long n;
    cin>>n;
    f=qmimy(f,n);
    a=mulmy(a,f);
    cout<<a.m[1][9];
    return 0;
}