这是本文档旧的修订版！

题解

J. Subsequence Sum Queries

题意

给定一个长度为 $n$ 的序列，接下来 $q$ 个询问，每次询问区间 $[l,r]$ 有多少个子序列满足元素之和整除 $m$。

题解

考虑分治处理询问。设当前维护区间为 $[lef,rig]$，$mid=\frac {lef+rig}2$。对 $[l,r]\in [lef,mid],[mid+1,rig]$ 的询问直接递归到左右区间处理。

对于跨 $\text{mid}$ 的询问，提前 $O\left((rig-lef)m\right)$ 处理出区间 $[i,mid](lef\le i\le mid),[mid+1,j](mid+1\le j\le rig)$ 的答案。

然后对每个询问相当于背包合并，时间复杂度 $O(qm^2)$。于是总时间复杂度 $O(nm\log n+qm^2)$。

查看代码

const int MAXN=2e5+5,MAXM=20,mod=1e9+7;
int ans[MAXN],a[MAXN],m;
struct query{
	int lef,rig,id;
};
int s[MAXN][MAXM],temp[MAXM<<1];
void solve(int lef,int rig,vector<query> b){
	int mid=lef+rig>>1;
	if(lef==rig){
		_for(i,0,b.size())
		ans[b[i].id]=1+(a[mid]==0);
		return;
	}
	mem(s[mid],0);
	s[mid][0]++;
	s[mid][a[mid]]++;
	for(int i=mid-1;i>=lef;i--){
		_for(j,0,m)
		s[i][(a[i]+j)%m]=(s[i+1][(a[i]+j)%m]+s[i+1][j])%mod;
	}
	mem(s[mid+1],0);
	s[mid+1][0]++;
	s[mid+1][a[mid+1]]++;
	for(int i=mid+2;i<=rig;i++){
		_for(j,0,m)
		s[i][(a[i]+j)%m]=(s[i-1][(a[i]+j)%m]+s[i-1][j])%mod;
	}
	vector<query>b1,b2;
	_for(i,0,b.size()){
		if(b[i].rig<=mid)
		b1.push_back(b[i]);
		else if(b[i].lef>mid)
		b2.push_back(b[i]);
		else{
			mem(temp,0);
			_for(j,0,m)_for(k,0,m)
			temp[j+k]=(temp[j+k]+1LL*s[b[i].lef][j]*s[b[i].rig][k])%mod;
			ans[b[i].id]=(temp[0]+temp[m])%mod;
		}
	}
	solve(lef,mid,b1);
	solve(mid+1,rig,b2);
}
int main()
{
	int n=read_int();
	m=read_int();
	_rep(i,1,n)a[i]=read_LL()%m;
	int q=read_int();
	vector<query> b;
	_for(i,0,q){
		int l=read_int(),r=read_int();
		b.push_back(query{l,r,i});
	}
	solve(1,n,b);
	_for(i,0,q)
	enter(ans[i]);
	return 0;
}

赛后总结

jxm：开局一个多小时后就罚坐了，疯狂写假题，下次一定先确认思路没问题再写题。

CVBB ACM Team

目录

题解

J. Subsequence Sum Queries

题意

题解

赛后总结

CVBB ACM Team

用户工具

站点工具

目录

题解

J. Subsequence Sum Queries

题意

题解

赛后总结

页面工具