Reincarnation

正因为梦易碎，才格外美好。

P4247 [清华集训2012] 序列操作

发表于 分类于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

到底是谁想出来的线段树套组合数学？

题目简介

题目名称：序列操作
题目来源：清华集训

评测链接：https://www.luogu.com.cn/problem/P4247

形式化题意：给定一个长度为 的序列，维护 次操作：

  • 对区间 执行 ；
  • 对区间 执行 ；
  • 查询区间 中选择 个数相乘的方案的和，对 取模。

数据范围：

考虑第三个阴间询问，但是 ，所以盲猜又是一个暴力维护。

我们维护 表示区间 中选出 个数的方案和。那么这个可以 合并：。

好，现在解决了阴间询问，发现修改变得更阴间了。

但第二个操作似乎好维护，对于每种方案相当于乘上了 ，那只需要维护所有奇数答案即可，时间复杂度 。

然后考虑怎么区间加，来根据多项式找规律：

然后你发现这就是个二项式展开，得到：

但这样是 的，显然吃不消。

考虑当前区间长度 ，我们对 进行修改，然后我们考虑对于 中的 在 中被计算的次数，从而能够一步从 贡献到 。

这是一个经典的组合问题，从 个数中选 个，其中 个指定，那么相当于从 个选 个，所以答案是 。

那么得到：

预处理组合数得到 的转移。

总时间复杂度 。

细节不是很多，注意函数初始化，组合数预处理区间，以及合并时 的调用等等。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
// ----- Eternally question-----
// Problem: P4247 [清华集训2012] 序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4247
// Memory Limit: 250 MB
// Time Limit: 6000 ms
// Written by: Eternity
// Time: 2023-09-20 09:59:12
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e4+10,MAXC=25;
const int Mod=19940417;
template<class T>
inline T modu(T x){ return (x%Mod+Mod)%Mod; }
int N,Q,val[MAXN];
ll C[MAXN][MAXC],tmp[MAXC];
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r,rev;
	ll add,val[MAXC];
	inline int len(){ return r-l+1; }
}Tr[MAXN<<2];
inline void pushUp(int p)
{
	std::memset(Tr[p].val,0,sizeof(Tr[p].val));
	for(int i=0;i<=Tr[ls].len();++i)
		for(int j=0;i+j<=20&&j<=Tr[rs].len();++j)
		{
			Tr[p].val[i+j]+=Tr[ls].val[i]*Tr[rs].val[j];
			Tr[p].val[i+j]=modu(Tr[p].val[i+j]);
		}
}
inline Segment merge(Segment p,Segment q)
{
	Segment ret;
	std::memset(ret.val,0,sizeof(ret.val));
	ret.l=p.l,ret.r=q.r;
	for(int i=0;i<=20&&i<=p.len();++i)
		for(int j=0;i+j<=20&&j<=q.len();++j)
		{
			ret.val[i+j]+=p.val[i]*q.val[j];
			ret.val[i+j]=modu(ret.val[i+j]);
		}
	return ret;
}
inline void add(int p,ll v)
{
	if(!p||!v) return ;
	for(int i=1;i<=20;++i) tmp[i]=modu(tmp[i-1]*v);
	for(int i=std::min(20,Tr[p].len());i;--i)
		for(int j=0;j<i;++j)
		{
			Tr[p].val[i]+=Tr[p].val[j]*tmp[i-j]%Mod*C[Tr[p].len()-j][i-j]%Mod;
			Tr[p].val[i]=modu(Tr[p].val[i]);
		}
	Tr[p].add=modu(Tr[p].add+v);
}
inline void rev(int p)
{
	if(!p) return ;
	for(int i=1;i<=20&&i<=Tr[p].len();++i)
	{
		Tr[p].val[i]=(i&1)?-Tr[p].val[i]:Tr[p].val[i];
		Tr[p].val[i]=modu(Tr[p].val[i]);
	}
	Tr[p].add=modu(-Tr[p].add);
	Tr[p].rev^=1;
}
inline void pushDown(int p)
{
	if(Tr[p].rev)
	{
		rev(ls),rev(rs);
		Tr[p].rev=0;
	}
	if(Tr[p].add)
	{
		add(ls,Tr[p].add),add(rs,Tr[p].add);
		Tr[p].add=0;
	}
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r)
	{
		Tr[p].val[0]=1,Tr[p].val[1]=modu(val[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyAdd(int p,int l,int r,ll v)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return add(p,v);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyAdd(ls,l,r,v);
	if(mid<r) modifyAdd(rs,l,r,v);
	pushUp(p);
}
void modifyRev(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return rev(p);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyRev(ls,l,r);
	if(mid<r) modifyRev(rs,l,r);
	pushUp(p);
}
Segment queryBin(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p];
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(r<=mid) return queryBin(ls,l,r);
	if(mid<l) return queryBin(rs,l,r);
	return merge(queryBin(ls,l,r),queryBin(rs,l,r));
}
char Opt[5];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q),tmp[0]=1;
	for(int i=1;i<=N;++i) read(val[i]);
	C[0][0]=1,Tr[0].val[0]=1;
	for(int i=1;i<=N;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=20&&j<=i;++j)
		{
			C[i][j]=C[i-1][j]+C[i-1][j-1];
			C[i][j]=modu(C[i][j]);
		}
	}
	build(1,1,N);
	for(int ql,qr,qc;Q--;)
	{
		scanf("%s",Opt),read(ql,qr);
		if(Opt[0]=='I') read(qc),modifyAdd(1,ql,qr,modu(qc));
		else if(Opt[0]=='R') modifyRev(1,ql,qr);
		else read(qc),write(modu(queryBin(1,ql,qr).val[qc]),'\n');
	}
	return 0;
}
/*

*/
相关文章