越城区建设和交通运输局网站,广州建筑信息平台,网站设计专业公司,个人自助网站2021牛客OI赛前集训营-提高组#xff08;第三场#xff09;
题目大意
一个长度为nnn的数组aaa#xff0c;每秒都会变成一个长度为n−1n-1n−1的新数组a′aa′#xff0c;其变化规则如下
如果当前数组aaa的大小nnn为偶数#xff0c;则对于新数组a′aa′的每一个位置i(1≤…2021牛客OI赛前集训营-提高组第三场
题目大意
一个长度为nnn的数组aaa每秒都会变成一个长度为n−1n-1n−1的新数组a′aa′其变化规则如下
如果当前数组aaa的大小nnn为偶数则对于新数组a′aa′的每一个位置i(1≤in)i(1\leq in)i(1≤in)ai′aiai1a_ia_ia_{i1}ai′aiai1如果当前数组aaa的大小nnn为奇数则对于新数组a′aa′的每一个位置i(1≤in)i(1\leq in)i(1≤in)ai′ai−ai1a_ia_i-a_{i1}ai′ai−ai1
最终数组经过n−1n-1n−1秒后变为一个数字求这个数字对109710^971097取模后的结果。 题解
通过打表可以发现当nnn为偶数时aia_iai对答案的贡献为(−1)t×Cn/2−1t(-1)^t\times C_{n/2-1}^{t}(−1)t×Cn/2−1t其中t⌊i−12⌋t\lfloor\dfrac{i-1}{2}\rfloort⌊2i−1⌋。
如果nnn为偶数则直接用上面的规律来求即可。如果nnn为奇数那么操作一次将nnn变为偶数再用上面的规律来求即可。
当然考场上可以直接用打表发现的规律但学习要严谨所以下面给出证明。
用多项式a1xa2x2⋯anxna_1xa_2x^2\cdotsa_nx^na1xa2x2⋯anxn表示当前的状态用xix^ixi的系数表示当前第iii个位置的值。
对于长度为偶数变为奇数的操作相当于原来的多项式乘上(11x)(1\dfrac 1x)(1x1)对于长度为奇数变为偶数的操作相当于原来的多项式乘上(1−1x)(1-\dfrac 1x)(1−x1)
那么nnn每减去2则多项式乘上(1−1x2)(1-\dfrac{1}{x^2})(1−x21)。
对于偶数的nnn多项式要乘上(1−1x2)n/2−1(11x)(1−Cn/2−111x2Cn/2−121x4−⋯)(11x)(1-\dfrac{1}{x^2})^{n/2-1}(1\dfrac 1x)(1-C_{n/2-1}^1\dfrac{1}{x^2}C_{n/2-1}^2\dfrac{1}{x^4}-\cdots)(1\dfrac 1x)(1−x21)n/2−1(1x1)(1−Cn/2−11x21Cn/2−12x41−⋯)(1x1)。最后的答案就是xxx的系数。
我们考虑如何求xxx的系数。对于最初多项式中的xix^ixi
如果iii是奇数则xix_ixi可以和(−1)tCn/2−1t1xi−1(-1)^tC_{n/2-1}^{t}\dfrac{1}{x^{i-1}}(−1)tCn/2−1txi−11相乘来得到xxx的项如果iii是偶数则xix_ixi可以和(−1)tCn/2−1t1xi−2×1x(-1)^tC_{n/2-1}^{t}\dfrac{1}{x^{i-2}}\times \dfrac 1x(−1)tCn/2−1txi−21×x1相乘来得到xxx的项
其中t⌊i−12⌋t\lfloor\dfrac{i-1}{2}\rfloort⌊2i−1⌋。
那么就可以得到开头的结论。
时间复杂度为O(n)O(n)O(n)。
code
#includebits/stdc.h
using namespace std;
int n;
long long ans0,a[100005],jc[100005],ny[100005];
long long mod1000000007;
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*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 i1;in;i) jc[i]jc[i-1]*i%mod;ny[n]mi(jc[n],mod-2);for(int in-1;i0;i--) ny[i]ny[i1]*(i1)%mod;for(int i1;in;i){scanf(%lld,a[i]);}if(n1){printf(%d,(a[1]%modmod)%mod);return 0;}if(n%21){--n;for(int i1;in;i){a[i](a[i]-a[i1]mod)%mod;}}for(int i1;in;i){int x(n-1)/2,y(i-1)/2;if(y1) ans(ans-C(x,y)*a[i]%modmod)%mod;else ans(ansC(x,y)*a[i]%modmod)%mod;}printf(%lld,ans);return 0;
}
