正题
题目链接:https://ac.nowcoder.com/acm/contest/20108/B
题目大意
给出一个长度为(n)的序列(a)，每次
- 如果(n)是偶数，则对于所有的(i<n)令新的(a'_i=a'_i+a'_{i+1})
- 如果(n)是奇数，则对于所有的(i<n)令新的(a'_i=a'_i-a'_{i+1})
(1leq nleq 10^5,1leq a_ileq 10^9)
解题思路
对于一个位置它操作(k)次之后肯定可以用后面的若干个数表示，设多项式(f_k(x)=sum_{i=0}^{infty }b_ix^i)有(a'_{p}=sum_{i=0}^nb_i imes a_{p+i})。
那么对于这个多项式如果(n)是奇数那么有(f_k(x)=f_{k-1}(x) imes (1+x))，否则(f_k(x)=f_{k-1}(x) imes (1-x))。
也就是每次((1+x))和((1-x))交替乘(n-1)次，如果(n)是奇数，那么
[f_{n-1}(x)=((1+x)(1-x))^{frac{n-1}{2}}=(1-x^2)^{frac{n-1}{2}}
]
用二项式定理拆开暴力算就好了，
如果(n)是偶数就直接再乘个(1+x)就好了。
时间复杂度：(O(n))
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10,P=1e9+7;
ll n,ans,fac[N],inv[N],f[N];
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
signed main()
{
scanf("%lld",&n);n--;
inv[0]=inv[1]=fac[0]=1;
for(ll i=2;i<=n;i++)inv[i]=P-(P/i)*inv[P%i]%P;
for(ll i=1;i<=n;i++)inv[i]=inv[i-1]*inv[i]%P,fac[i]=fac[i-1]*i%P;
for(ll i=0;i<=n/2;i++)
f[i*2]=(i&1)?(P-C(n/2,i)):(C(n/2,i));
if(n&1){
for(ll i=n;i>=1;i--)
f[i]=f[i]+f[i-1];
}
for(ll i=0,x;i<=n;i++)
scanf("%lld",&x),(ans+=f[i]*x%P)%=P;
printf("%lld
",ans);
return 0;
}