题解 | #加密#_牛客博客

只有C题，快速幂+除法取模+公式法
由于本方法为公式法，如果你是因为被卡时间而做不对的话，可以看一下；如果完全不会做这个题，就看官方题解吧！
如果你能正确的打表，就会发下如下事实：
当最后一位为 $i$ 时，

$i=1$ ，只有 $1$ 种情况（全1）

$i=2$ ，有 $\frac{n}{1}$ 种

$i=3$ ，有 $\frac{n*(n+1)}{1*2}$ 种

$i=4$ ，有 $\frac{n*(n+1)*(n+2)}{1*2*3}$ 种
一直求到 $i=9$ 就够了。
那么结果就是全加起来呗
因为这里面有除法，所以还需要具备除法取模的知识

$\frac{a}{b}\mod c = a*b^{c-2}\mod c$

又因为c很大，所以还要求快速幂的知识。。这里就不讲了

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ll;
typedef pair<int, int> pii;
#define _rp(i, a, b) for (int i = a; i < b; i++)
void PP() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
}
const int N = 1e8 + 2;
const ll mod = 100019;
void check() {}
// int a[N][10];
int n, m;
ll now[10];
inline int MOD(int a) {
    if (a < mod)
        return a;
    else
        return a % mod;
}
ll get_pow(ll x, ll n) {
    ll ans = 1;
    while (n) {
        if (n & 1) {
            ans = ans * x % mod;
        }
        x = x * x % mod;
        n >>= 1;
    }
    return (ans + mod) % mod;
}
int main() {
    void PP();
    ll n;
    cin >> n;
    if (n == 1) {
        cout << 9;
        return 0;
    }
    if (n == 2) {
        cout << 45;
        return 0;
    }
    now[1] = 1;
    _rp(i, 2, 10) {
        // 原来应该长这样
        // now[i] = (now[i - 1] * ((n + i - 2)/ (i - 1)) % mod) % mod ;
        now[i] = now[i - 1] * (n + i - 2) % mod * get_pow(i - 1, mod - 2) % mod;
        now[i] %= mod;
    }
    cout << accumulate(now + 1, now + 10, 0) % mod;
    return 0;
}