题目
题目
根据题意推式子。
a
0
=
1
a_0=1
a0=1
a
1
=
1
×
k
n
=
k
a_1=1\times \displaystyle \frac{k}{n}=k
a1=1×nk=k
a
2
=
(
1
+
k
)
k
2
a_2=\displaystyle \frac{(1+k)k}{2}
a2=2(1+k)k
a
3
=
(
1
+
k
+
(
1
+
k
)
k
2
)
k
3
=
(
1
+
k
)
(
2
+
k
)
k
6
a_3=(1+k+\displaystyle \frac{(1+k)k}{2})\displaystyle \frac{k}{3}=\displaystyle \frac{(1+k)(2+k)k}{6}
a3=(1+k+2(1+k)k)3k=6(1+k)(2+k)k
…
…
……
……
a
n
=
(
1
+
k
)
(
2
+
k
)
(
3
+
k
)
…
(
n
−
1
+
k
)
k
n
!
=
(
n
−
1
+
k
)
!
(
k
−
1
)
!
n
!
a_n=\displaystyle \frac{(1+k)(2+k)(3+k)…(n-1+k)k}{n!}=\displaystyle \frac{(n-1+k)!}{(k-1)!n!}
an=n!(1+k)(2+k)(3+k)…(n−1+k)k=(k−1)!n!(n−1+k)!
所以先预处理阶乘，然后逆元一下就好了。
思路
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int mod=1e9+7;
long long ycl[10000011];
int n,k,T;
long long ksm(long long x,long long y)
{
long long ans=1;
while(y!=0)
{
if(y&1)
ans=(ans*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return ans%mod;
}
int main()
{
scanf("%d",&T);
ycl[0]=1,ycl[1]=1;
for(int i=2; i<=10000010; i++)
ycl[i]=(ycl[i-1]*i)%mod;
while(T--)
{
scanf("%d%d",&n,&k);
long long a=((ycl[n+k-1]*ksm(ycl[k-1],mod-2))%mod)*ksm(ycl[n],mod-2)%mod;
printf("%d\n",a);
}
return 0;
}