Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 678 Solved: 246
[Submit][Status][Discuss]
有一个长度为n的序列,有三个操作1.I a b c表示将[a,b]这一段区间的元素集体增加c,2.R a b表示将[a,b]区间内所有元素变成相反数,3.Q a b c表示询问[a,b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。
第一行两个数n,q表示序列长度和操作个数。
第二行n个非负整数,表示序列。
接下来q行每行输入一个操作I a b c或者 R a b或者Q a b c意义如题目描述。
对于每个询问,输出选出c个数相乘的所有方案的和mod19940417的值。
5 5
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1
40
19940397
样例说明
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为3*4+3*4+4*4=40。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为-2-4-5-4-5=-20。
100%的数据n<=50000,q<=50000,初始序列的元素的绝对值<=109,I a b c中保证[a,b]是一个合法区间,|c|<=109,R a b保证[a,b]是个合法的区间。Q a b c中保证[a,b]是个合法的区间1<=c<=min(b-a+1,20)。
线段树维护区间卷积
我们每个区间维护sum[1~20]分别表示选1~20个数的积的和
然后问题在于合并以及修改
合并非常简单$rt.sum[i]=\sum_{j=1}^{i}ls.sum[j]*rs.sum[i-j]$ (手写小的就可以得到)
至于区间取反,直接对区间的所有奇数$sum$取反,偶数$sum$不变。 因为 偶数里的全是偶数项,负号会抵消
区间修改,问题是下放标记时,我们发现假设我们有三个数a,b,c;我们修改时同时+x,那么他们的变化就是
$(a+x)*(b+x)*(c+x)=abc+x(ab+ac+bc)+x^{2}(a+b+c)+x^{3}$这样我们发现,拓展到之后可以得到$sum[i]=\sum_{j=0}^{i}sum[i-j]*C_{sz-j}^{i}*x^{i-j}$
然后我们就可以利用线段树维护了,特别地$sum[0]=1$,中间过程会爆int;
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN 80010 #define P 19940417 int N,Q,C[MAXN][21]; namespace SegmentTree { struct SumNode{int sum[25];}; struct SegmentTreeNode{int l,r,size,tag; SumNode p; bool rev;}tree[MAXN<<2]; #define ls now<<1 #define rs now<<1|1 inline void Add(int &x,int y) {x+=y; while (x>=P) x-=P; while (x<0) x+=P;} inline SumNode Merge(SegmentTreeNode x,SegmentTreeNode y) { SumNode re; re.sum[0]=1; for (int i=1; i<=20; i++) { re.sum[i]=(x.p.sum[i]+y.p.sum[i])%P; for (int j=1; j<=i-1; j++) Add(re.sum[i],(LL)x.p.sum[j]*y.p.sum[i-j]%P); } return re; } inline void Update(int now) {tree[now].p=Merge(tree[ls],tree[rs]);} inline void rever(int now) { tree[now].rev^=1; if (tree[now].tag) tree[now].tag=(P-tree[now].tag%P)%P; for (int i=1; i<=20; i++) if ((i&1) && tree[now].p.sum[i]) tree[now].p.sum[i]=(P-tree[now].p.sum[i])%P; } inline void change(int now,int D) { Add(tree[now].tag,D); for (int t=D,i=20; i; i--,t=D) { for (int j=i-1; j; j--,t=(LL)t*D%P) Add(tree[now].p.sum[i],(LL)t*tree[now].p.sum[j]%P*C[tree[now].size-j][i-j]%P); Add(tree[now].p.sum[i],(LL)t*C[tree[now].size][i]%P); } } inline void PushDown(int now) { if (tree[now].rev) {rever(ls); rever(rs); tree[now].rev=0;} if (tree[now].tag) {change(ls,tree[now].tag); change(rs,tree[now].tag); tree[now].tag=0;} } inline void BuildTree(int now,int l,int r) { tree[now].l=l; tree[now].r=r; tree[now].size=r-l+1; tree[now].p.sum[0]=1; tree[now].tag=0; tree[now].rev=0; if (l==r) {tree[now].p.sum[1]=(read()+P)%P; return;} int mid=(l+r)>>1; BuildTree(ls,l,mid); BuildTree(rs,mid+1,r); Update(now); } inline void Reverse(int now,int L,int R) { int l=tree[now].l,r=tree[now].r; if (L<=l && R>=r) {rever(now); return;} PushDown(now); int mid=(l+r)>>1; if (L<=mid) Reverse(ls,L,R); if (R>mid) Reverse(rs,L,R); Update(now); } inline void Change(int now,int L,int R,int D) { int l=tree[now].l,r=tree[now].r; if (L<=l && R>=r) {change(now,D); return;} PushDown(now); int mid=(l+r)>>1; if (L<=mid) Change(ls,L,R,D); if (R>mid) Change(rs,L,R,D); Update(now); } inline SegmentTreeNode Query(int now,int L,int R,int D) { int l=tree[now].l,r=tree[now].r; if (L==l && R==r) return tree[now]; PushDown(now); int mid=(l+r)>>1; SegmentTreeNode re; if (R<=mid) return Query(ls,L,R,D); else if (L>mid) return Query(rs,L,R,D); else return re.p=Merge(Query(ls,L,mid,D),Query(rs,mid+1,R,D)),re; } } void GetC() { C[0][0]=1; for (int i=1; i<=N; i++) { C[i][0]=1; for (int j=1; j<=min(i,20); j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P; } } using namespace SegmentTree; int main() { // freopen("sequence.in","r",stdin); // freopen("sequence.out","w",stdout); N=read(),Q=read(); GetC(); SegmentTree::BuildTree(1,1,N); // for (int i=1; i<=N; i++) printf("%I64d ",Query(1,1,N,i).p.sum[i]); puts(""); // puts("============================================"); while (Q--) { char opt[2]; scanf("%s",opt); int x,y,z; switch (opt[0]) { case 'I' : x=read(),y=read(),z=(read()+P)%P; SegmentTree::Change(1,x,y,z); break; case 'Q' : x=read(),y=read(),z=read(); printf("%d\n",SegmentTree::Query(1,x,y,z).p.sum[z]); break; case 'R' : x=read(),y=read(); SegmentTree::Reverse(1,x,y); break; } // puts("============================================"); // for (int i=1; i<=N; i++) printf("%d\n",Query(1,1,N,i).p.sum[i]); puts(""); // printf("%d %d %d\n",x,y,z); // puts("============================================"); } return 0; }
%来%去太鬼畜了
数组少打一个0,BZOJ楞是WA,就是不报RE,小数据妥妥拍不到,纸张
差点搞得自己以后再也不能叫char哥....
本文链接:http://task.lmcjl.com/news/12607.html