题解 | #加密#

C 题
一个线性递推，但由于n数值过大，无法进行继续，我们只要给n取余100019即可！！！

成立的理由大致如下：

递推100019次，而且还是一个和式，那么一定是100019的倍数！

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int P = 100019;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n; n%=P;
    vector <vector <int>> f(n+5,vector <int> (10));
    for(int i=1;i<=9;++i) f[1][i]=i;
    for(int i=2;i<=n;++i){
        for(int j=1;j<=9;++j){
            f[i][j]=(f[i][j-1]+f[i-1][j])%P;
        }
    }
    cout<<f[n][9]<<'\n';
    return 0;
}