HDU 5496——Beauty of Sequence——————【考虑局部】
Beauty of Sequence
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 384 Accepted Submission(s): 168
Now you are given a sequence A of n integers {a1,a2,...,an}. You need find the summation of the beauty of all the sub-sequence of A. As the answer may be very large, print it modulo 109+7.
Note: In mathematics, a sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example {1,3,2} is a sub-sequence of {1,4,3,5,2,1}.
The first line contains an integer n (1≤n≤105), indicating the size of the sequence. The following line contains n integers a1,a2,...,an, denoting the sequence(1≤ai≤109).
The sum of values n for all the test cases does not exceed 2000000.
#include<bits/stdc++.h>
using namespace std;
typedef long long INT;
const int mod=1e9+7;
const int maxn=1e5+200;
INT a[maxn];
INT pow2[maxn];
map<int,INT>coun;
int main(){
int T,n;
scanf("%d",&T);
pow2[0]=1;
for(int i=1;i<=maxn-100;i++){
pow2[i]=pow2[i-1]*2%mod;
}
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
}
coun.clear();
coun[0]=1;
INT ans=0;
for(int i=1;i<=n;i++){
INT pre=coun[a[i]];
INT tpre=pow2[i-1]-pre; //i-1
tpre=(tpre%mod+mod)%mod;
INT tmp=a[i]*tpre%mod*pow2[n-i]%mod;
ans=(ans+tmp)%mod;
pre=pow2[i-1]+pre;
coun[a[i]]=pre;
}
printf("%I64d\n",ans);
}
return 0;
}
最新文章
- 多预览小图焦点轮播插件lrtk
- tarjan讲解(用codevs1332(tarjan的裸题)讲解)
- Git和Github简单教程(转)
- C#中获取当前时间:System.DateTime.Now.ToString()用法
- PARSEC-3.0编译错误
- 配置tomcat解压版
- Shell编程基础教程4--控制流结构
- 谈mvc开发中gzip压缩的应用
- hbase基本操作
- listview实现点击条目上的箭头展开隐藏菜单。
- Java集合框架(三)
- 再写FFT模板
- 漫谈Linux标准的文件系统(Ext2/Ext3/Ext4)
- Lumen框架—升级改造之路-开篇
- iis正确安装了,但是还是无法访问,这是iis和.net安装顺序问题,记录一下
- Stream、FileStream、MemoryStream的区别
- 拓普微小尺寸TFT液晶屏-高性价比
- 15款基于 jQuery模态对话框
- JavaScript 之 function函数及参数arguments
- 【PyQt5-Qt Designer】日历(QCalendarWidget)
热门文章
- ng2 样式控制之style绑定和class绑定
- 转载:IntelliJ IDEA 2016.2 配置Tomcat 运行Web项目
- C#自定义控件 绘制框
- 任务调度TimerTask&;Quartz的 Java 实现方法与比较
- C++中栈结构建立和操作
- 具体问题:Spring 事务的隔离性,并说说每个隔离性的区别
- 2017Java学习路线图,内附完整Java自学视频教程+工具经验+面试
- 阶段2-新手上路\项目-移动物体监控系统\Sprint3-移动监控主系统设计与开发
- 7.30实习培训日志-SQL优化
- return 、break和continue的区别和作用