传送门:http://codeforces.com/contest/266/problem/E
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid(x,y) (x+y)>>1
#define mod 1000000007
typedef long long LL;
const int MAXN = 100010;
const int MAXK = 7;
LL val[MAXN<<2][MAXK],flag[MAXN<<2],Sum[MAXN][MAXK],Comb[MAXK][MAXK],A[MAXN];
LL pow_mod(LL a,LL p){
if(p==0)return 1;
LL b = pow_mod(a,p/2);
if(p%2){
return (((b*b)%mod)*a)%mod;
}else{
return (b*b)%mod;
}
}
LL getComb(LL m,LL n){
LL up=1,down=1;
for(int i=0;i<n;i++){
up = up*(m-i);
down = down*(i+1);
}
return up/down;
}
void preprocess(){
for(int i=1;i<MAXN;i++){
for(int j=0;j<MAXK;j++){
Sum[i][j] = (Sum[i-1][j]+pow_mod(i,j))%mod;
}
}
for(int i=0;i<MAXK;i++){
for(int j=0;j<=i;j++){
Comb[i][j] = getComb(i,j)%mod;
}
}
}
void PushUp(int rt){
for(int i=0;i<MAXK;i++){
val[rt][i] = (val[rt<<1][i]+val[rt<<1|1][i])%mod;
}
}
void PushDown(int l,int r,int rt){
if(flag[rt]==-1)return;
if(l==r){
flag[rt] = -1;
return;
}
int m = mid(l,r);
for(int i=0;i<MAXK;i++){
LL tmp = (Sum[m][i]-Sum[l-1][i])%mod;
if(tmp<0)tmp+=mod;
val[rt<<1][i] = (tmp*flag[rt])%mod;
tmp = (Sum[r][i]-Sum[m][i])%mod;
if(tmp<0)tmp+=mod;
val[rt<<1|1][i] = (tmp*flag[rt])%mod;
}
flag[rt<<1] = flag[rt<<1|1] = flag[rt];
flag[rt] = -1;
}
void build(int l,int r,int rt){
flag[rt] = -1;
if(l==r){
for(int i=0;i<MAXK;i++){
val[rt][i] = (A[l]*pow_mod(l,i))%mod;
}
return;
}
int m = mid(l,r);
build(lson);
build(rson);
PushUp(rt);
}
void update(int L,int R,int v,int l,int r,int rt){
if(l>=L&&r<=R){
flag[rt] = v;
for(int i=0;i<MAXK;i++){
LL tmp = (Sum[r][i]-Sum[l-1][i])%mod;
if(tmp<0)tmp+=mod;
val[rt][i] = (tmp*flag[rt])%mod;
}
return;
}
PushDown(l,r,rt);
int m = mid(l,r);
if(m>=L)update(L,R,v,lson);
if(m<R)update(L,R,v,rson);
PushUp(rt);
}
LL query(int L,int R,int k,int l,int r,int rt){
if(l>=L&&r<=R){
return val[rt][k];
}
PushDown(l,r,rt);
int m = mid(l,r);
LL ret = 0;
if(m>=L) ret = (ret+query(L,R,k,lson))%mod;
if(m<R) ret = (ret+query(L,R,k,rson))%mod;
return ret;
}
int main(){
int n,m;
char op;
int l,r;
LL x;
preprocess();
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++){
scanf("%I64d",&A[i]);
}
build(1,n,1);
while(m--){
getchar();
scanf("%c%d%d%I64d",&op,&l,&r,&x);
if(op=='=')update(l,r,x,1,n,1);
else{
LL res = 0,tmp = 1;
for(int i=x;i>=0;i--){
res += ((((query(l,r,i,1,n,1))*Comb[x][i])%mod)*tmp)%mod;
res = (res+mod)%mod;//1-l可能为负数,所以此操作能保证res每一步的正确性
tmp = (tmp*(1-l))%mod;
}
printf("%I64d\n",res);
}
}
}
return 0;
}
分享到:
相关推荐
tornado-6.4.1-cp38-abi3-musllinux_1_2_i686.whl
tornado-6.1-cp36-cp36m-manylinux2014_aarch64.whl
基于java的ssm停车位短租系统程序答辩PPT.pptx
tornado-6.4b1-cp38-abi3-musllinux_1_1_x86_64.whl
基于java的招生管理系统答辩PPT.pptx
本压缩包资源说明,你现在往下拉可以看到压缩包内容目录 我是批量上传的基于SpringBoot+Vue的项目,所以描述都一样;有源码有数据库脚本,系统都是测试过可运行的,看文件名即可区分项目~ |Java|SpringBoot|Vue|前后端分离| 开发语言:Java 框架:SpringBoot,Vue JDK版本:JDK1.8 数据库:MySQL 5.7+(推荐5.7,8.0也可以) 数据库工具:Navicat 开发软件: idea/eclipse(推荐idea) Maven包:Maven3.3.9+ 系统环境:Windows/Mac
基于java的农机电招平台答辩PPT.pptx
jdk23 甲骨文官方安装包
基于java的机场网上订票系统答辩PPT.pptx
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
基于java的网上书店销售管理系统答辩PPT.pptx
tornado-6.3.3-cp38-abi3-win32.whl
【作品名称】:基于 Jsp+Sqlserver 实现的超市信息管理系统 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】: 系统功能: (1)系统分两种身份:管理员和员工,选择不同的身份进入不同的功能操作界面! (2)商品信息管理:管理员可以添加和维护商品信息,员工只能对商品信息进行查询 (3)员工信息管理:管理员登陆系统后可以可以添加和维护超市员工(收银员)的信息 (4)商品进货管理:管理员登陆系统后可以添加商品进货信息,可以对商品进货信息进行查询和统计,添加商品进进货退货信息,对商品进货退货信息进行查询和统计 (5)商品销售管理:员工(收银员)登陆系统后可以对商品进行销售,可以按时间查询自己的销售业绩;管理员登陆系统后可以按照时间等条件对销售信息进行查询,可以根据小票号登记顾客退货信息,查询顾客退货信息,可以查看员 【资源声明】:本资源作为“参考资料”而不是“定制需求”,代码只能作为参考,不能完全复制照搬。需要有一定的基础看懂代码,自行调试代码并解决报错,能自行添加功能修改代码。
tornado-6.3.2-cp38-abi3-musllinux_1_1_i686.whl
基于java的热带水果商城答辩PPT.pptx
java awt、Swing实现中国象棋可联机版本采用面向对象思想 采用面向对象的思路,实现中国象棋可联机版本,适合初学者,以及对面向对象有更深层次理解的开发者或者同学。 使用原生的java awt、Swing进行窗口式开发 将素材文件夹放在D:\Game路径下 两个工程直接导入Eclipse,即可运行, ps:一个工程运行两次也可以,需要注意端口号,代码默认如果连接的端口号是3003,则监听3004端口,相反同理。联机前需要确保两台计算机同时处于局域网或外网
web前端设计与开发(详细整理)(包含html讲解,css讲解,移动web讲解),合适学习前端的人员进行基础学习,一秒变高手
分析所需的数据和代码都在这里
Listening Exercise 3 Part 2.mp3
链表 删除链表中的重复元素,链表基础