牛客练习赛 80

不降数
这个题很有意思哇 有很多的解法emm
记录一下做题过程qwq
如果n的范围小一点，可以直接用数位dp过掉，但是n太大会mle.
于是写了一个线性dp递推+滚动数组，复杂度是1e10的emmm
dp[i, j]表示第i位以j结尾的数的个数。
可以留着对拍：

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

const int mod = 100019;

ll dp[2][15], n;

int main(){
    for(int i = 1; i <= 9; ++ i)    dp[1][i] = 1;
    cin >> n;
    for(int i = 2; i <= n; ++ i){
        int nxt = i % 2;
        for(int j = 1; j <= 9; ++ j)    dp[nxt][j] = 0;
        for(int j = 1; j <= 9; ++ j)
            for(int k = j, f = 0; k <= 9; ++ k)
                dp[nxt][k] = (dp[nxt][k] + dp[nxt ^ 1][j]) % mod;
    }
    ll ans = 0;
    for(int i = 1; i <= 9; ++ i)
        ans = (ans + dp[n % 2][i]) % mod;
    cout << ans;
    return 0;
}

后来发现可以省掉一维， 从9开始倒着推，利用前缀和的思想：

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

const int mod = 100019;

ll dp[2][15], n, last;

int main(){
    for(int i = 1; i <= 9; ++ i) dp[1][i] = 1;
    last = 9;
    cin >> n;
    for(int i = 2; i <= n; ++ i){
        ll now = 0;
        int nxt = i % 2;
        for(int j = 9; j >= 1; -- j){
            dp[nxt][j] = (last - dp[nxt ^ 1][j + 1] + mod) % mod;
            last = (last + mod - dp[nxt ^ 1][j + 1]) % mod;
            now = (now + dp[nxt][j]) % mod;
        }
        last = now;
    }
    ll ans = 0;
    for(int i = 1; i <= 9; ++ i)
        ans = (ans + dp[n % 2][i]) % mod;
    cout << ans;
    return 0;
}

1e9的复杂度依然过不了qwq
但是利用这个dp打出表，可以发现（OIES）答案是C（n, 8）, 于是qwq

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

const int mod = 100019;

ll ksm(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1)    res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main(){
    ll n;
    cin >> n;
    n = n + 8;
    ll ans = 1;
    for(ll i = n; i >= n - 7; -- i)    ans = ans * i % mod;
    for(int i = 2; i <= 8; ++ i)
    ans = ans * ksm(i, mod - 2) % mod;
    cout << ans;
}

但是！其实是可以线性dp过的，只需要一开始把n %= mod即可。

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

const int mod = 100019;

ll dp[2][15], n;

int main(){
    for(int i = 1; i <= 9; ++ i)    dp[1][i] = 1;
    cin >> n;
    n %= mod;        //zhi
    for(int i = 2; i <= n; ++ i){
        int nxt = i % 2;
        for(int j = 1; j <= 9; ++ j)    dp[nxt][j] = 0;
        for(int j = 1; j <= 9; ++ j)
            for(int k = j, f = 0; k <= 9; ++ k)
                dp[nxt][k] = (dp[nxt][k] + dp[nxt ^ 1][j]) % mod;
    }
    ll ans = 0;
    for(int i = 1; i <= 9; ++ i)
        ans = (ans + dp[n % 2][i]) % mod;
    cout << ans;
    return 0;
}

理由： 递推100019次，而且还是一个和式，那么一定是100019的倍数！拖延症等着再补？
另外，线性dp可以使用矩阵快速幂优化，也可以直接做：
拖延症等着再补？

答案是C(n, 8)的原因：
拖延症等着再补？