不降数（牛客练习赛80）

不降数

• editorial
  与atcoder中该题非常相像，因此我们可以先选出递增的序列。
  序列可能的方案数为(C(9,1) + C(9, 2) + C(9, 3) + ... + C(9, min(n, 9)))，然后我们使用插板法，可以将固定长度的序列扩充成长度为n的序列，给定序列长度为x，则扩充后方案数为(C(n-1, x-1))。
  时间复杂度为(O(log P))

重复组合

• code:

#include<bits/stdc++.h>
using namespace std;
const int MOD = 100019;
typedef long long ll;
ll f[10],finv[10];

ll fast_pow(ll a,ll n)
{
    ll ans = 1;
    while(n)
    {
        if(n&1) ans = (ans * a)%MOD;
        a = (a * a)%MOD;
        n >>= 1;
    }
    return ans;
}
ll C(ll n,ll m)
{
    if(m == 0)  return 1;
    ll ans = 1;
    for(int i = 0;i < m;i++)    ans = ans * (n-i)%MOD;
    return ans*finv[m]%MOD;
}
void init()
{
    f[0]=1;
    for(int i=1;i< 10;i++)
        f[i]=f[i-1]*i%MOD;
    finv[9] = fast_pow(f[9],MOD-2);
    for (int i = 9; i > 0; i--)
        finv[i-1]=finv[i]*i%MOD;
}	

int main(int argc, char const *argv[])
{
    int dig;
    init();
    ll ans = 0;
    scanf("%d", &dig);
    // C(9,1) + C(9, 2) + C(9, 3) + ... + C(9, min(dig, 9));
    for(int i = 1;i <= min(dig, 9);i++)
        ans = (ans + C(9, i)*(C(dig-1, i-1)%MOD)%MOD)%MOD;
    printf("%lld
", ans);
    return 0;
}