题目背景
国王1带大家到了数字王国的中心：三角圣地。
题目描述
不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是1~N。1~N可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为“基”。国王1希望“基”越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你输出它mod 10007 的结果。
任务：给定N，求三角形1~N的基的最大值 再去 mod 10007。
输入输出格式
输入格式：
一个整数N
输出格式：
一个整数，表示1~N构成的三角形的最大的“基”
思路：
其实这道题大家画个图就会发现，1~n个数在他们自己位置上的权值是杨辉三角形第n行
由于可以交换位置，所以将最大的放在中间即可
于是开始算了
一开始，我用的递推组合数直接求一行杨辉三角形
50分？？
哦，1000000太大了，递推会出锅
好吧，Lucas来一发
还是50分？？
好吧，TLE出锅了
怎么办呢？
看来只能预处理阶乘了。。。
心累。。
递推版：
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,p,t,ans[1000010],ny[1000010],out;
void qny()
{
ny[1]=1;
for(register int a=2;a<=n;a++)
{
ny[a]=(p-(p/a))*ny[p%a]%p;
}
}
int main()
{
scanf("%d",&n);
p=10007;
qny();
m=(n+1)/2;
ans[0]=1;
for(register int i=1;i<=m-1;i++)
{
ans[i]=ans[i-1]*(n-i)*ny[i]%p;
}
for(register int i=2;i<=n;i+=2)
{
long long ltt=i+i-1;
ltt%=p;
ltt*=ans[i/2-1];
ltt%=p;
out+=ltt;
out%=p;
}
if(n%2==1)
{
long long ltt=n*ans[m-1]%p;
out+=ltt;
out%=p;
}
cout<<out;
}
Lucas朴素版：
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#define rii register int i
using namespace std;
unsigned long long n,m,p,t,ny[100010],out;
void qny()
{
ny[1]=1;
for(register int a=2;a<=p;a++)
{
ny[a]=(p-(p/a))*ny[p%a]%p;
}
}
int zhs(int q,int x)
{
if(q==0)
{
return 1;
}
long long ltt=1;
for(register int a=1;a<=q;a++)
{
ltt*=ny[a];
ltt%=p;
}
for(register int a=1;a<=q;a++)
{
ltt*=(x-a+1);
ltt%=p;
}
return ltt;
}
long long lucas(int s,int t)
{
if(t==0)
{
return 1;
}
else
{
return (lucas(s/p,t/p)*zhs(s%p,t%p))%p;
}
}
int main()
{
scanf("%d",&n);
p=10007;
qny();
for(rii=1;i<=n;i+=2)
{
if(i==n)
{
out+=lucas(i/2,n-1)*(i);
}
else
{
out+=lucas(i/2,n-1)*(i*2+1);
}
out%=p;
}
cout<<out;
}
正解：
#include<iostream>
#include<cstring>
#define rii register int i
using namespace std;
int p=10007;
long long jc[10010],ny[10010],n,ans;
void ycl()
{
jc[0]=1;
jc[1]=1;
ny[0]=1;
ny[1]=1;
for(rii=2;i<=p-1;i++)
{
jc[i]=jc[i-1]*i%p;
}
for(rii=2;i<=p-1;i++)
{
ny[i]=(p-p/i)*ny[p%i]%p;
}
for(rii=1;i<=p-1;i++)
{
ny[i]=ny[i-1]*ny[i]%p;
}
}
long long lucas(long long h,long long j)
{
if(h<j)
{
return 0;
}
if(h<p&&j<p)
{
return jc[h]*ny[j]%p*ny[h-j]%p;
}
return lucas(h/p,j/p)*lucas(h%p,j%p)%p;
}
int main()
{
ycl();
cin>>n;
for(rii=1;i<=n;i++)
{
if(i%2==0)
{
ans=(ans+(i*lucas(n-1,n-i/2))%p)%p;
if(ans<0)
{
ans+=p;
}
}
else
{
ans=(ans+(lucas(n-1,(i+1)/2-1)*i)%p)%p;
if(ans<0)
{
ans+=p;
}
}
}
cout<<ans;
}