标签：数学，贪心
题目
不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是1~N。1~N可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为“基”。国王1希望“基”越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你输出它mod 10007 的结果。
任务：给定N，求三角形1~N的基的最大值 再去 mod 10007。
输入：一个整数N
输出：一个整数，表示1~N构成的三角形的最大的“基”
输入输出样例 输入样例#1： 复制
4
输出样例#1： 复制
24
说明
数据：
20% 0<=N<=100
50% 0<=N<=3000
100% 0<=N<=1000000
样例解释：
1 3 4 2
4 7 6
11 13 24 是N=4的时候的最大值，当然还有别的构成形式。
PS：它叫做三角圣地，其实它就是个三角形~
本题数据已经更新（我更新的）
分析
思路：观察发现越大的数排在中间位置对答案越有利，所以就可以贪心了 而不同位置对答案有不同的贡献次数 拿样例举例 1 3 4 2 那么第一个位置1对答案贡献1次 第二个位置3对答案贡献3次 第三个位置4对答案贡献3次 第四个位置2对答案贡献1次
不难发现这个贡献次数为杨辉三角（就是组合数）
我们可以O(n^2)求出组合数对10007的取模
$ ans=\sum_{i=1}^n C(n,i)*i$
当然答案要取模，在计算的过程中防止负数的出现，要加入判断
O(n^2)求组合数就可以获得50分了
但是觉得这题太水了点，于是加强了下数据范围。
N<=1000000
快速求出组合数，模数也那么小，当然是Lucas定理了！
套个lucas定理的板子就可以了，不知道Lucas的出门右转百度
这题数据出锅了，自己真的zz，爆了long long
此题感谢@BFSBFSBFSBFS @siyuan 的交流和支持
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()//快速读入
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int p=10007;
ll fac[p],inv[p],n;//注意要用long long否则会爆掉
ll ans;
void work()
{
fac[0]=fac[1]=inv[0]=inv[1]=1;
rep(i,2,p-1)fac[i]=fac[i-1]*i%p; //阶乘预处理
rep(i,2,p-1)inv[i]=(p-p/i)*inv[p%i]%p;
rep(i,1,p-1)inv[i]=inv[i-1]*inv[i]%p; //逆元预处理
}
ll C(ll n,ll m)
{
if(n<m)return 0; //舍去组合数无意义的情况
if(n<p&&m<p)return fac[n]*inv[m]%p*inv[n-m]%p;
return C(n/p,m/p)*C(n%p,m%p)%p;
}
int main()
{
//freopen("data20.in","r",stdin);
//freopen("data20.ans","w",stdout);
work(); //预处理出乘法逆元和阶乘
n=read();
rep(i,1,n){
if(i%2==0){ans=(ans+((ll)(i*C(n-1,n-i/2)))%p)%p;if(ans<0)ans+=p;}
else{ans=(ans+((ll)(C(n-1,(i+1)/2-1)*i))%p)%p;if(ans<0)ans+=p;}//这个数本身*这个数贡献的次数，将其累加到答案中去
}
cout<<ans<<endl;
return 0;
}
