当前位置: 首页 > news >正文

邢台市建设局官方网站友情链接交换平台

邢台市建设局官方网站,友情链接交换平台,广州网站建设怎样做,绵阳 网站建设2021牛客OI赛前集训营-提高组(第三场) 题目大意 一个长度为nnn的数组aaa,每秒都会变成一个长度为n−1n-1n−1的新数组a′aa′,其变化规则如下 如果当前数组aaa的大小nnn为偶数,则对于新数组a′aa′的每一个位置i(1≤…

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

题目大意

一个长度为nnn的数组aaa,每秒都会变成一个长度为n−1n-1n1的新数组a′a'a,其变化规则如下

  • 如果当前数组aaa的大小nnn为偶数,则对于新数组a′a'a的每一个位置i(1≤i<n)i(1\leq i<n)i(1i<n)ai′=ai+ai+1a'_i=a_i+a_{i+1}ai=ai+ai+1
  • 如果当前数组aaa的大小nnn为奇数,则对于新数组a′a'a的每一个位置i(1≤i<n)i(1\leq i<n)i(1i<n)ai′=ai−ai+1a'_i=a_i-a_{i+1}ai=aiai+1

最终数组经过n−1n-1n1秒后变为一个数字,求这个数字对109+710^9+7109+7取模后的结果。


题解

通过打表可以发现,当nnn为偶数时,aia_iai对答案的贡献为(−1)t×Cn/2−1t(-1)^t\times C_{n/2-1}^{t}(1)t×Cn/21t,其中t=⌊i−12⌋t=\lfloor\dfrac{i-1}{2}\rfloort=2i1

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

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

用多项式a1x+a2x2+⋯+anxna_1x+a_2x^2+\cdots+a_nx^na1x+a2x2++anxn表示当前的状态,用xix^ixi的系数表示当前第iii个位置的值。

  • 对于长度为偶数变为奇数的操作,相当于原来的多项式乘上(1+1x)(1+\dfrac 1x)(1+x1)
  • 对于长度为奇数变为偶数的操作,相当于原来的多项式乘上(1−1x)(1-\dfrac 1x)(1x1)

那么nnn每减去2,则多项式乘上(1−1x2)(1-\dfrac{1}{x^2})(1x21)

对于偶数的nnn,多项式要乘上(1−1x2)n/2−1(1+1x)=(1−Cn/2−111x2+Cn/2−121x4−⋯)(1+1x)(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)(1x21)n/21(1+x1)=(1Cn/211x21+Cn/212x41)(1+x1)。最后的答案就是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/21txi11相乘来得到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/21txi21×x1相乘来得到xxx的项

其中t=⌊i−12⌋t=\lfloor\dfrac{i-1}{2}\rfloort=2i1

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

时间复杂度为O(n)O(n)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;
}
http://www.15wanjia.com/news/18441.html

相关文章:

  • 苏州建站公司选苏州聚尚网络百度百科官网
  • 杭州做网站的优质公司哪家好自己的产品怎么推广
  • 中国人民解放军战略支援部队seo培训资料
  • asp.net 如何设置网站首页seo点击排名源码
  • 个人网站设计的意义佛山百度seo点击软件
  • 西昌手机网站建设成都彩钢顶防水网上接单平台
  • 如何查找做网站的服务商新媒体运营培训课程
  • 宿迁公司做网站重庆seowhy整站优化
  • 做网站前端用什么刚刚发生了一件大事
  • 建设网站公司哪家技术好达内教育
  • 什么是企业网站源码人民日报今天新闻
  • 廊坊高端品牌网站建设中国十大电商平台有哪些
  • 购物网站制作例子今日国际新闻头条新闻
  • 一个服务器可以备案几个网站吗白酒最有效的推广方式
  • 淘宝网站SEO怎么做google play谷歌商店
  • 上海网站设计工作室seo推广营销公司
  • 做网站的细节广告推广媒体
  • 哪家公司做网站不错营销培训课程有哪些
  • 网站做地域屏蔽seo整站优化吧
  • 关停网站的申请厦门网络推广外包多少钱
  • 做网站什么字体比较好看免费的网络推广渠道
  • wordpress多用户模版北京企业网站seo平台
  • 坡头手机网站建设快速排名刷
  • 成都市分类信息网站开发代运营竞价公司
  • 简单网站seo关键词排名价格
  • 南通做网站的公司有哪些今日国内新闻摘抄十条
  • 免费推广方法有哪些百度seo排名优化公司推荐
  • asp.net门户网站项目怎么做开电商需要多少钱
  • 临夏城乡建设局网站枸橼酸西地那非片的作用及功效
  • 班级网站制作教程定制网站开发