题解 | #不降数#

可以根据 f(1) ---- f(2)发现加速矩阵
然后可以根据矩阵快速幂写

代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 100019;

struct matrix
{
    ll a[9][9];
};
//这里的mul和pow还有matrix要结合起来用,矩阵快速幂,题目中是有mod的
matrix mul(matrix x, matrix y) {//矩阵乘法
    matrix c;
    for (int i = 0; i<9; i++)
    {
        for (int j = 0; j<9; j++)
        {
            c.a[i][j] = 0;
            for (int k = 0; k<9; k++)
                c.a[i][j] = (c.a[i][j] % mod + ((x.a[i][k] % mod) * (y.a[k][j] % mod)) % mod) % mod;//这里需要mod
        }
    }
    return c;
}
ll pow(matrix x, ll n) {//快速幂
    matrix ans;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(i==j) ans.a[i][j]=1;
            else ans.a[i][j]=0;
        }
    }
    while (n)
    {
        if (n & 1)
            ans = mul(ans, x);
        x = mul(x, x);
        n >>= 1;
    }
    matrix ab;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(j==0) ab.a[i][j]=9-i;
            else ab.a[i][j]=0;
        }
    }
    ab = mul(ab,ans);
    ll dd = 0;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(i==j) dd=(dd+ab.a[i][j])%mod;
         }
        //cout<<endl;
    }
    return (dd)%mod;
}

int main() {
    ll n, t;
    matrix base;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(j>=i) base.a[i][j]=1;
            else base.a[i][j]=0;
        } 
    }
    cin>>n;
    cout << pow(base, n-1) << endl;
    return 0;
}