自动搬运

查看原文

来自洛谷，原作者为

	buowen123 生活将我反复捶打，我变成可可爱爱的年糕～ | 根据抽屉原理，必然存在关注 >= 粉丝的人，也存在关注 <= 粉丝的人 | 似乎是 INFP-T | 粉关比 >= 1 的都是大神

搬运于2025-08-24 22:54:09，当前版本为作者最后更新于2024-07-21 15:37:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

• 给你一个长度为 $n$ 的序列 $a$，要求维护区间加区间积，对 $2^{20}$ 取模。
• $1 \le n,q \le 2 \times 10^5$，保证任意时刻 $a$ 中的数均为奇数。

题目解决

区间加区间积看着就不是很可做，但是有一条特殊的性质：$a_i$ 恒为奇数。

设 $a_i=x_i+1$，于是 $2|x_i$。那么 $\prod_{i=l}^r a_i=\prod_{i=l}^r (x_i+1)$。

由于答案对 $2^{20}$ 取模，将原式展开，每一项都是不超过 $19$ 个 $x_i$ 的乘积。

那么我们可以线段树维护，对区间 $[l,r]$ 维护 $s_i$，其中 $s_i$ 表示在 $[l,r]$ 中选择 $i$ 个 $x$ 所得乘积之和，即 $\sum_{|S|=i}\prod_{p\in S}x_p$。

• 如何 pushup？

你在左儿子里边取 $j$ 个数相乘，右儿子里边取 $i-j$ 个数相乘，她们的乘积就等价于在整个区间内选 $i$ 个数相乘。

• 如何 pushdown/更新？

考虑你有 $k$ 个数并已知她们的 $f$ 值，对所有数加上 $v$ 之后 $f$ 的变化。

考虑 $f_{i}$ 的变化。考虑展开式

$$(x_1+v)(x_2+v)\dots(x_i+v)-x_1x_2\dots x_i\\=v^i+(x_1+x_2+\dots x_i)v^{i-1}+\dots +(x_1x_2\dots x_{i-1}+x_1x_2\dots x_{i-2}x_i+\dots x_2x_3\dots x_i)v $$

可以发现，在 $x_1$ 到 $x_i$ 中选 $j$ 个数相乘，将这些乘积求和，会为 $f_i'$ 带来 $C_{k-j}^{i-j} \times v^{i-j}$ 的贡献，所以

$$f_i'=\sum f_j\times C_{k-j}^{i-j} \times v^{i-j}$$

组合数是因为，你可以在未选择的 $k-j$ 个数中，再任选 $i-j$ 个数不计算乘积。

这么做时间复杂度是 $O(n \log n a^2)$，其中 $a=20$，卡常之后可以通过。

一些卡常技巧：

• 将 $v$ 取模 $2^{20}$，然后 $v^{i-j}$ 可以预处理。
• 将 int 改为 unsigned，可以减少取模次数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+3;
int n,q;
#define gc getchar
inline int read(){
	int x=0;
	char c=gc();
	while(c<48) c=gc();
	while(c>47) x=(x<<1)+(x<<3)+(c^48),c=gc();
	return x; 
}
unsigned a[maxn],c[maxn][21],pw[(1<<20)+5][20];
namespace Segtree{
	#define ls (pos<<1)
	#define rs (pos<<1|1)
	unsigned g[20];
	struct Seg{
		int l,r;
		unsigned f[20],add; 
		inline void upd(unsigned x){
			add+=x; x&=1048575;
			for(int i=0;i<20;i++){
				g[i]=0;
				for(int j=0;j<=min(i,r-l+1);j++)
					g[i]+=c[r-l+1-j][i-j]*f[j]*pw[x][i-j];
			}
			for(int i=0;i<20;i++) f[i]=g[i];
		}
	}tr[maxn<<2];
	#define mid ((tr[pos].l+tr[pos].r)>>1)
	inline void push_u(int pos){
		for(int i=0;i<20;i++){
			tr[pos].f[i]=0;
			for(int j=0;j<=i;j++){
				tr[pos].f[i]+=tr[ls].f[j]*tr[rs].f[i-j];
			}
		}
	}
	inline void push_d(int pos){
		if(tr[pos].add){ 
			tr[ls].upd(tr[pos].add);
			tr[rs].upd(tr[pos].add);
			tr[pos].add=0;
		}
	}
	void build(int pos,int l,int r){
		tr[pos].l=l,tr[pos].r=r;
		if(l==r){
			tr[pos].f[0]=1,tr[pos].f[1]=a[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_u(pos);
	}
	void up_add(int pos,int l,int r,unsigned x){
		if(l<=tr[pos].l&&tr[pos].r<=r){
			tr[pos].upd(x);
			return;
		}
		push_d(pos);
		if(l<=mid) up_add(ls,l,r,x);
		if(mid<r) up_add(rs,l,r,x);
		push_u(pos);
	}
	unsigned qry(int pos,int l,int r){
		if(l<=tr[pos].l&&tr[pos].r<=r){
			unsigned cur=0;
			for(int i=0;i<20;i++)
				cur+=tr[pos].f[i];
			return cur;
		}
		unsigned cur=1;
		push_d(pos);
 		if(l<=mid) cur*=qry(ls,l,r);
		if(mid<r) cur*=qry(rs,l,r);
		return cur;
	}
}using namespace Segtree;
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	double T=clock();
	n=read(),q=read();
	for(int i=1;i<=n;i++)
		a[i]=read()-1;
	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];
	}
	for(unsigned i=0;i<(1<<20);i++){
		pw[i][0]=1;
		for(int j=1;j<20;j++)
			pw[i][j]=pw[i][j-1]*i;
	}
	build(1,1,n);
	int op,l,r;
	unsigned x;
	for(int i=1;i<=q;i++){
		op=read(),l=read(),r=read();
		if(op==1){
			x=read();
			up_add(1,l,r,x);
		}
		else printf("%u\n",qry(1,l,r)&1048575);
	}
//	cerr<<clock()-T<<" ms\n";
	return 0;
}

如果有错误与不合理之处，欢迎大家批评指正。