【找规律】【递推】【二项式定理】Codeforces Round #419 (Div. 1) B. Karen and Test

打个表出来看看，其实很明显。

推荐打这俩组

11

1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 10000000000

 

12

1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 10000000000 100000000000

 

 

打出表来看出来，n为偶数时，每隔两行，对原序列的奇数项分配的权重形成二项展开式。

n为奇数时，每隔四行，形成二项展开式。

 

所以只需要求出接近最后的某一行中的二项式系数即可。（有个O（n）的递推式可以直接求杨辉三角某一行的值）

最后距离答案已经不超过四行了，暴一下就行了。

 

#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 1000000007ll
typedef long long ll;
ll n,nn;
ll a[200010],C[200010],b[10],c[10];
ll Quick_Pow(ll a,ll p)
{
    if(!p) return 1;
    ll ans=Quick_Pow(a,p>>1);
    ans=ans*ans%MOD;
    if((p&1)==1) ans=(a%MOD*ans)%MOD;
    return ans;
}
int main(){
	scanf("%I64d",&n);
	for(ll i=1ll;i<=n;++i){
		scanf("%I64d",&a[i]);
	}
	int tmp=0;
	if(!(n&1ll)){
		nn=n/2ll-1ll;
		tmp=2;
	}
	else{
		nn=n;
		++tmp;
		while((nn-1ll)%4ll!=0ll){
			--nn;
			++tmp;
		}
		nn/=2ll;
	}
	C[0]=1;
	for(ll i=1ll;i<=nn;++i){
		C[i]=((C[i-1]*(nn-(i-1ll)))%MOD*Quick_Pow(i,MOD-2ll))%MOD;
	}
	for(int i=1;i<=tmp;++i){
		for(int j=i,k=0;j<=n;j+=2,++k){
			b[i]=(b[i]+(a[j]%MOD*C[k])%MOD)%MOD;
		}
	}
	ll sum=0;
	for(ll i=n;i>(ll)tmp;--i){
		sum+=(i-1ll);
	}
	bool op=(sum%2ll==0 ? 1 : 0);
	for(int i=tmp;i>1;--i){
		for(int j=1;j<i;++j){
			if(op){
				c[j]=b[j]+b[j+1];
			}
			else{
				c[j]=b[j]-b[j+1];
			}
			op^=1;
		}
		memcpy(b,c,sizeof(c));
	}
	printf("%I64d\n",(b[1]+MOD)%MOD);
	return 0;
}