816D.Karen and Test 杨辉三角 规律 组合

LINK

题意：给出n个数，每个数对间进行加或减，结果作为下一层的数，问最后的值为多少

思路：首先我们发现很像杨辉三角，然后考虑如何计算每个数对结果的贡献值，找规律可以发现当数的个数为偶数时，其所在层表达式即为二项式定理，且其中的数下标差都为2，故倒数第二层就是将第一层的数分为系数相同的两组，最后相减或相加。注意取模问题，使用逆元。注意n<=2的特殊情况

/** @Date    : 2017-07-01 13:43:26
  * @FileName: 816D 组合 杨辉三角.cpp
  * @Platform: Windows
  * @Author  : Lweleth ([e-mail])
  * @Link    : https://github.com/
  * @Version : $Id$
  */
#include <bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 2e5+20;
const double eps = 1e-8;
const LL mod = 1e9 + 7;

int n;
LL a[N];
LL fac[N], Inv[N];
LL fpow(LL a, int n)
{
	LL res = 1;
	while(n > 0)
	{
		if(n & 1)
			res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
void init()
{
	fac[1] = Inv[1] = 1;
	for(LL i = 2; i <= n; i++)
	{
		fac[i] = fac[i - 1] * i % mod;
		Inv[i] = (mod - mod / i) * Inv[mod % i] % mod;
	}
	for(int i = 2; i <= n; i++)
	{
		Inv[i] = (Inv[i] * Inv[i - 1]) % mod;
	}
}

LL C(LL n, LL k)
{
	if(k == 0 || n == k)
		return 1LL;
	else return (fac[n] * Inv[k] % mod) * Inv[n - k] % mod;
}

int main()
{
	while(cin >> n)
	{
		init();
		MMF(a);
		LL ans = 0;
		for(int i = 0; i < n; i++) scanf("%lld", a + i);

		if(n % 2)
		{
			n--;
			LL f = 1;
			for(int i = 0; i < n; i++)
			{
				a[i] = (a[i] + a[i + 1] * f) % mod;
				f *= -1;
			}
		}
		for(int i = 0; i < n; i+=2)
		{
			ans = (ans + (a[i] + a[i + 1]*(n%4?1:-1) ) * C(n/2 - 1, i/2) % mod) % mod;
			//printf("%lld~%lld\n", a[i]*C(n/2 - 1, i/2), a[i+1]*C(n/2 - 1, i/2));
		}
		if(ans < 0)
			ans = (ans + mod) % mod;
		if(n <= 2)//小于2的特殊情况
			printf("%lld\n", (a[0] + a[1]) % mod);
		else
			printf("%lld\n", ans % mod);

	}
    return 0;
}