为什么洛谷办理的如此之好
查看原帖
为什么洛谷办理的如此之好
616733
Lysea楼主2024/10/22 17:51

因为总有热心的大佬帮助他人。

求问,本题这种哈希写法为什么不对?

#include<bits/stdc++.h>
#define int long long
#define N 2000005
#define INF 1e18
using namespace std;
const int M=1e9+7,base=131;
int n,m,l[N],c[N],b[N],a[N];
int val[N],s[N],cnt,ans,len;
map<int,int>mp;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>l[i];
	for(int i=1;i<=m;i++) cin>>c[i];
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	sort(a+1,a+n+1);
	int tot=unique(a+1,a+n+1)-(a+1);
	val[0]=1;
	for(int i=1;i<=tot;i++){
		val[i]=val[i-1]%M*base%M;
	}
	for(int i=1;i<=m;i++){
		c[i]=lower_bound(a+1,a+tot+1,c[i])-a;
		cnt+=l[i]*val[c[i]],len+=c[i];
	}
	for(int r=1,l=1;r<=n;r++){
		b[r]=lower_bound(a+1,a+tot+1,b[r])-a;
		s[r]=s[r-1]+val[b[r]];
		mp[s[r]]++,ans+=mp[s[r]-cnt];
	}
	cout<<ans;
	return 0;
}
2024/10/22 17:51
加载中...