题目描述
一个长度为 \(n\) 的数组\(A\)，每秒都会变成一个长度为 \(n − 1\) 新数组 \(A'\)，其变化规
则如下：
-
若当前数组 \(A\) 的长度 \(n\) 为偶数，则对于新数组 \(A'\) 的每一个位置 \(i(1 ≤ i < n)\)来说，\(A'[i]=A[i]+A[i+1]\)
-
若当前数组 \(A\) 的长度 \(n\) 为奇数，则对于新数组 \(A'\) 的每一个位置 \(i(1 ≤ i < n)\)来说，\(A'[i]=A[i]-A[i+1]\)
最终数组经过 \(n − 1\) 秒的时间变成一个数字。求这个数字对 \(10^9 + 7\)取模后的结果。
输入格式
第一行输入一个正整数\(n\)，表示数组的长度。
接下来每行输入\(n\)个正整数，表示数组中的每一个元素。
输出格式
输出一行一个整数表示答案。
样例
输入样例1
3
1 6 8
输出样例1
1000000000
样例解释1
第一秒的时候进行第二种变化，即 \(A\)数组由 \([1, 6, 8]\) 变为\([-5, -2]\)，然后第二秒的时候，由于此时数组长度为 \(2\)，所以进行第一种变化，即数组变为 \([-7]\)，最终输出这个数字对\(10^9 + 7\)取模后的结果，所以输出 \(1000000000\)。
数据范围
对于 \(40\%\) 的数据，满足 \(n ≤ 1000\)。
对于 \(100\%\) 的数据，满足 \(1 ≤ n ≤ 10^5，1 ≤ ai ≤ 10^9\)。
题目简化
对于一个长度为\(n\)的数组\(A\)，反复进行以下操作，直到\(n=1\)。
- 如果\(n\equiv 0\pmod 2\),则\(A_i\gets A_i+A_{i+1}\)
- 如果\(n\equiv 1\pmod 2\),则\(A_i\gets A_i-A_{i+1}\)
- \(n\gets n-1\)
最后输出 \(A_1\)
题解
这道题我用的是打表找规律，先来看看奇数。
当 \(n=1\) 时，得
当 \(n=3\) 时，得
当 \(n=5\) 时，得
这时候我们初步发现规律，再来一组？当\(n=7\)时，得
观察系数，列出一个表格：
从数字来看：杨辉三角，从符号来看：奇正偶负。
用式子来表达规律：\(ans=\sum\limits_{i=0}^n(-1)^{i+1}C_k^{\frac {i+1} 2 }A_i\)且\(i\equiv1\pmod 2\)
偶数可以暴力转换为奇数，最终预处理之后就可以 \(O(n)\)完成。
打表找规律是信息学竞赛的一种常见手段，非常好用，建议多多使用。
证明
接下来是严谨的证明,使用数学归纳法。
打表已知前几项符合我们的假设，接下来我们假设对于长度小于等于 \(x-2\) 且为奇数的数组全部符合这一设想。
对于一个长度为\(x\)的数组，我们进行运算。
由于长度小于等于 \(x-2\) 且为奇数的数组全部符合这一设想，所以设\(k=\frac {x-3} 2\)，则原式可写成：
那么对于一个奇数\(i\),\(A_i\)会在哪里出现呢？显然是\(C_k^{\frac {i-1} 2 } (A_i-A_{i+2})\)和 \(C_k^{\frac {i+1} 2 } (A_{i+2}-A_{i+4})\)
\(A_i\)的系数为\((-1)^{i+1}(C_k^{\frac {i-1} 2 }+C_k^{\frac {i+1} 2 } )=(-1)^{i+1}C_{k+1}^{\frac {i+1} 2 }\)，由此，证明完毕。
代码
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,a[100005],inv[100005],fac[100005],ans;
long long C(long long n,long long m)
{
if(n<m)return 0;
if(n==m||m==0)return 1;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
long long ksm(long long x,long long y)
{
long long ans=1;
while(y)
{
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
int main()
{
fac[0]=1;
for(int i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
inv[100000]=ksm(fac[100000],mod-2);
for(int i=99999;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
if(n%2==0)
{
for(int i=1;i<n;i++)a[i]=(a[i]+a[i+1])%mod;
n--;
}
long long k=(n-1)/2,t=1;
for(int i=1;i<=n;i+=2)
ans=((ans+t*C(k,(i+1)/2-1)%mod*a[i]%mod)%mod+mod)%mod;
t*=-1;
}
printf("%lld",ans);
}