题目背景
CCJCCJ 在前往参加 Universe \ OIUniverse OI 的途中。。。
题目描述
有一个神犇 CCJCCJ，他在前往参加 Universe \ OIUniverse OI 的途中发现了一个超星系群。
在这个超星系群，有着一群生物 ccjccj，他们有着神奇的 ccjccj 文化，蕴含文史哲艺等多方面内容，具有悠远的历史。
他们有自己的文学，自己的科学，当然，还有自己的四叶草和幸运数。在 ccjccj 文化中，不断进化是生存的必要条件，于是在这个星系群中，有 kk种数字，一个数是幸运数，当且仅当该数中从高位往低位每个数位上的数字单调不降。
CCJCCJ 想考验这个超星系群，于是有了一个任务：求由 kk 种数字组成的数中 nn 位数的幸运数的个数。
由于 ccjccj 文化中缺少超级计算机，你需要帮助他们解决这个简单的问题。
输入输出格式
输入格式：
第一行一个整数opop，表示该测试点所属SubtaskSubtask的编号。其中op=0op=0表示样例。
第二行两个整数，nn，kk，意义如题目描述中所述。
输出格式：
一行一个整数，答案ansans对1000001910000019取模。
输入输出样例
0
9 9
24310
0
15 24
1257167
说明
数据范围：
Subtask \ 1Subtask 1（10 \%10%）：n \leq 1000n≤1000，k \leq 200k≤200；
Subtask \ 2Subtask 2（40 \%40%）：n \leq 10000n≤10000，k \leq 5000k≤5000；
Subtask \ 3Subtask 3（40 \%40%）：n \leq 10000000n≤10000000，k \leq 10000000k≤10000000；
Subtask \ 4Subtask 4（10 \%10%）：n \leq 10^{18}n≤1018，k \leq 10^{18}k≤1018；
Subtask \ 5Subtask 5（0 \%0%）：n \leq 10^{100000}n≤10100000，k \leq 10^{100000}k≤10100000。
题解Here!
从$k$个数中任选若干个，求单调不降序列的个数。
单调不降有点烦，我们将选出来的序列中每一位$i$上的数都加上$i$。
即：原数列为${a_i}$，新数列为${b_i=a_i+i}$。
于是变成：
从$n+k-1$个数中任选若干个，求单调上升序列的个数。
于是这个题的答案就是：$$Ans=C_{n+k-1}^n$$
直接$Lucas$即可。
附代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 10000050
#define MOD 10000019LL
using namespace std;
long long n,k;
long long fact[MAXN],inv[MAXN];
inline long long read(){
long long date=0;char c=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date;
}
long long mexp(long long a,long long b,long long c){
long long s=1;
while(b){
if(b&1)s=s*a%c;
a=a*a%c;
b>>=1;
}
return s;
}
void make(){
int m=MOD-1;
fact[0]=1;
for(int i=1;i<=m;i++)fact[i]=fact[i-1]*i%MOD;
inv[m]=mexp(fact[m],MOD-2,MOD);
for(int i=m-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%MOD;
}
inline long long C(long long n,long long m){
if(n<m)return 0;
if(m==0||m==n)return 1;
if(m==1||m==n-1)return n;
return fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}
long long Lucas(long long n,long long m){
if(n<m)return 0;
if(m==0||m==n)return 1;
if(m==1||m==n-1)return n;
return Lucas(n/MOD,m/MOD)*C(n%MOD,m%MOD)%MOD;
}
int main(){
int t=read();
make();
n=read();k=read();
printf("%lld\n",Lucas(n+k-1,n));
return 0;
}