2021牛客OI赛前集训营-提高组（第三场）T2交替

2021牛客OI赛前集训营-提高组（第三场）

题目大意

一个长度为$n$的数组$a$，每秒都会变成一个长度为$n-1$的新数组$a^{\prime }$，其变化规则如下

• 如果当前数组$a$的大小$n$为偶数，则对于新数组$a^{\prime }$的每一个位置$i(1\le i<n)$，$a_i^{\prime }=a_i+a_{i+1}$
• 如果当前数组$a$的大小$n$为奇数，则对于新数组$a^{\prime }$的每一个位置$i(1\le i<n)$，$a_i^{\prime }=a_i-a_{i+1}$

最终数组经过$n-1$秒后变为一个数字，求这个数字对$10^9+7$取模后的结果。

题解

通过打表可以发现，当$n$为偶数时，$a_i$对答案的贡献为$(-1{)}^t\times C_{n/2-1}^t$，其中$t=\lfloor \frac{i-1}{2}\rfloor$。

如果$n$为偶数，则直接用上面的规律来求即可。如果$n$为奇数，那么操作一次，将$n$变为偶数，再用上面的规律来求即可。

当然，考场上可以直接用打表发现的规律，但学习要严谨，所以下面给出证明。

用多项式$a_{1}x+a_2{x}^2+\cdots +a_n{x}^n$表示当前的状态，用$x^i$的系数表示当前第$i$个位置的值。

• 对于长度为偶数变为奇数的操作，相当于原来的多项式乘上$(1+\frac{1}{x})$
• 对于长度为奇数变为偶数的操作，相当于原来的多项式乘上$(1-\frac{1}{x})$

那么$n$每减去2，则多项式乘上$(1-\frac{1}{x^2})$。

对于偶数的$n$，多项式要乘上$(1-\frac{1}{x^2}{)}^{n/2-1}(1+\frac{1}{x})=(1-C_{n/2-1}^1\frac{1}{x^2}+C_{n/2-1}^2\frac{1}{x^4}-\cdots )(1+\frac{1}{x})$。最后的答案就是$x$的系数。

我们考虑如何求$x$的系数。对于最初多项式中的$x^i$，

• 如果$i$是奇数，则$x_i$可以和$(-1{)}^t{C}_{n/2-1}^t\frac{1}{x^{i-1}}$相乘来得到$x$的项
• 如果$i$是偶数，则$x_i$可以和$(-1{)}^t{C}_{n/2-1}^t\frac{1}{x^{i-2}}\times \frac{1}{x}$相乘来得到$x$的项

其中$t=\lfloor \frac{i-1}{2}\rfloor$。

那么就可以得到开头的结论。

时间复杂度为$O(n)$。

code

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=0,a[100005],jc[100005],ny[100005];
long long mod=1000000007;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
long long C(int x,int y){return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
int main()
{scanf("%d",&n);jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;ny[n]=mi(jc[n],mod-2);for(int i=n-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}if(n==1){printf("%d",(a[1]%mod+mod)%mod);return 0;}if(n%2==1){--n;for(int i=1;i<=n;i++){a[i]=(a[i]-a[i+1]+mod)%mod;}}for(int i=1;i<=n;i++){int x=(n-1)/2,y=(i-1)/2;if(y&1) ans=(ans-C(x,y)*a[i]%mod+mod)%mod;else ans=(ans+C(x,y)*a[i]%mod+mod)%mod;}printf("%lld",ans);return 0;
}