传送门: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;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 解题思路 并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
### Codeforces Round 961 (Div. 2) A题解析 #### 题目背景 Codeforces Round 961 (Div. 2) 是一场针对中级水平程序员的编程竞赛,通常会包含几个不同难度级别的题目。A题作为入门级题目,旨在测试参赛者的基础算法...
codeforces round 961 (div. 2)
### Codeforces Round 961 (Div. 2):深度解析与实战技巧 #### 引言 Codeforces 是一个国际知名的在线编程竞赛平台,它汇聚了来自世界各地的编程爱好者和专业人士。每一轮比赛都旨在测试参赛者的算法思维、编程...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
Codeforces 19 E Fairy 是一道关于图论和二分图的编程竞赛题目。本题要求求解在给定的无向图中,通过删除一条边使得剩余的图成为一个二分图。首先,我们需要理解二分图的概念。二分图是指图中的节点可以分为两个互不...
标题中的"Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系"指的是一场编程竞赛中的问题,涉及到树结构的查询和深度优先搜索(DFS)来判断节点间的祖先关系。这个问题的目标是设计算法来确定在...
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
解决问题的方法教育Codeforces回合101 - 2/6 常规托架顺序-接受红色和蓝色-接受Codeforces回合#686(Div.3) 2/6 特殊排列-接受唯一出价拍卖-接受序列转换-接受编号成序列-接受Codeforces回合#685(分区2) 2/7 减...
题目“Anu Has a Function”源自Codeforces Round #618 (Div. 2)的一道竞赛编程问题,主要涉及进制转换、位运算和贪心算法。问题要求定义一个函数f(x, y) = (x | y) - y,并对数组进行排序,以最大化最后的结果。 ...
codeforces round 962 (div. 3)tion-ma笔记
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
Codeforces Round 962 (Div. 3) 是一场编程竞赛,其中包含了多个编程题目,每个题目都有其独特的挑战和解题思路。以下是对该竞赛中部分题目的简要介绍及解题思路概述: A题: Legs 题意: 一只鸡有2条腿,一头奶牛有...
### Codeforces Round #627 (Div. 3) D. Pair of Topics(二分,思维) #### 题目背景与概述 本题目来自Codeforces Round #627 (Div. 3),编号为D的题目“Pair of Topics”,这是一道结合了二分搜索与逻辑思维的...
Codeforces提供了一系列服务给所有的用户,包括但不限于:参加每周大约一次的2小时短时竞赛(称为"Codeforces Rounds");解决以往竞赛中的问题作为训练;使用“Polygon”创建和测试问题;通过内部公共博客实现一种...