求证明或证伪
查看原帖
求证明或证伪
642173
KarmaticEnding楼主2024/10/28 17:37

如题,现在我有两个序列长均为 nn 的序列:aabb。其中,aa 中的元素和 bb 中的元素均为正整数。

那么问题是:如果存在以下关系式:

i=1nai=i=1nbii=1nai=i=1nbi\sum_{i=1}^{n}a_i=\sum_{i=1}^{n}b_i\\ \prod_{i=1}^{n}a_i=\prod_{i=1}^{n}b_i

是否能够重排 aa,使得 a=ba=b

我在考场上用线段树维护以上做法,被第 5555 个点卡掉了,最后加了一个异或相等才卡过去。

这是加了异或相等的代码,大佬帮忙看看,是我加、乘写丑了,还是结论本身就有问题?

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const int MAXN=2e5+10;
#define ls rt<<1
#define rs (rt<<1)|1
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
struct SegmentTree{
	long long sum[MAXN<<2],mul[MAXN<<2],Xor[MAXN<<2];
	long long a[MAXN];
	inline void pushup(int rt){
		sum[rt]=sum[ls]+sum[rs];
		mul[rt]=mul[ls]*mul[rs]%mod;
		Xor[rt]=Xor[ls]^Xor[rs];
	}
	void build(int l,int r,int rt){
		if(l==r){
			sum[rt]=a[l];
			mul[rt]=a[r];
			Xor[rt]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(lson);
		build(rson);
		pushup(rt);
	}
	long long query(int L,int R,int l,int r,int rt){
		if(L<=l&&r<=R){
			return sum[rt];
		}
		int mid=(l+r)>>1;
		long long res=0;
		if(L<=mid){
			res+=query(L,R,lson);
		}
		if(R>mid){
			res+=query(L,R,rson);
		}
		return res;
	}
	long long Query(int L,int R,int l,int r,int rt){
		if(L<=l&&r<=R){
			return mul[rt];
		}
		int mid=(l+r)>>1;
		long long res=1ll;
		if(L<=mid){
			res*=Query(L,R,lson);
		}
		if(R>mid){
			res*=Query(L,R,rson);
		}
		res%=mod;
		return res;
	}
	long long querX(int L,int R,int l,int r,int rt){
		if(L<=l&&r<=R){
			return Xor[rt];
		}
		int mid=(l+r)>>1;
		long long res=0ll;
		if(L<=mid){
			res^=querX(L,R,lson);
		}
		if(R>mid){
			res^=querX(L,R,rson);
		}
		return res;
	}
}Ta,Tb;
int n,Q;
long long a[MAXN],b[MAXN];
int main(){
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&b[i]);
	}
	for(int i=1;i<=n;++i){
		Ta.a[i]=a[i];
		Tb.a[i]=b[i];
	}
	Ta.build(1,n,1);
	Tb.build(1,n,1);
	int l,r,L,R;
	while(Q--){
		scanf("%d%d%d%d",&l,&r,&L,&R);
		if(r-l!=R-L){
			printf("No");
		}
		else{
			if(Ta.query(l,r,1,n,1)==Tb.query(L,R,1,n,1)&&Ta.Query(l,r,1,n,1)==Tb.Query(L,R,1,n,1)&&Ta.querX(l,r,1,n,1)==Tb.querX(L,R,1,n,1)){
				printf("Yes");
			}
			else{
				printf("No");
			}
		}
		putchar('\n');
	}
	return 0;
}
2024/10/28 17:37
加载中...