【luoguP2675】《瞿葩的数字游戏》T3-三角圣地

题目背景

国王1带大家到了数字王国的中心：三角圣地。

题目描述

不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是1~N。1~N可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为“基”。国王1希望“基”越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你输出它mod 10007 的结果。

任务：给定N，求三角形1~N的基的最大值再去 mod 10007。

输入格式

一个整数N

输出格式

一个整数，表示1~N构成的三角形的最大的“基”

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

输出 #2复制

说明/提示

数据：

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：它叫做三角圣地，其实它就是个三角形~

本题数据已经更新，目前全部正确无误！

不要面向数据编程！

思想：比如样例4，：1 2 3 4

　　　　　　 1 3 4 2

　　　　　　 4 7 6

　　　　　　 11 13

此时价值最大，可以发现，其实是满足组合数的关系：贡献分别为：

　　　　　　1 3 3 1

　　也就是n-1行，注意组合数从第0行开始，我一开始挂在这里了。

　　可以用卢卡斯定理，线性求阶乘逆元。

　　注意模数

线性求逆元：

#define mod 100007

for(int i=1;i<=mod-1;i++)inv[i]=(p-p/i)*inv[p%i]%mod;

　线性求阶乘逆元：

#define mod 100007

for(int i=1;i<=mod-1;i++)inv[i]=(p-p/i)*inv[p%i]%mod;

for(int i=1;i<=mod-1;i++)inv[i]=inv[i]*inv[i-1]%mod;

代码：

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define int long long

using namespace std;

const int N = 1000000;

const int p = 10007;

int inv[N],c[N],ans,n;

int read()

{

	int x=0,f=1;

	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;

}

void work()

{

	c[0]=c[1]=inv[1]=inv[0]=1;

	for(int i=2;i<=p-1;i++)c[i]=c[i-1]*i%p;

	for(int i=2;i<=p-1;i++)inv[i]=(p-p/i)*inv[p%i]%p;

	for(int i=1;i<=p-1;i++)inv[i]=inv[i-1]*inv[i]%p;

}

int C(int n,int m)

{

	if(n<m)return 0;

	if(n<p && m<p)

	{

		return c[n] *inv[m] %p * inv[n-m] %p;

	}

	return C(n/p,m/p)*C(n%p,m%p)%p;

}

signed main()

{

	work();

	n=read();

	for(int i=1;i<=n;i++)

	{

		if(i%2==0)

		{

			ans += (C(n-1,n-i/2)%p*i%p);//自己代数可行

			ans%=p;

			while(ans<0) ans+=p;

		}

		else

		{

			ans += (C(n-1,(i+1)/2-1)%p*i%p)%p;//自己代数找，分奇偶

			ans%=p;

			while(ans<0) ans+=p;

		}

	}

	printf("%lld\n",ans);

	return 0;

}

-----yi-----lin

巴特西