比赛 寒假集训4 评测结果 AAAAAAAAAA
题目名称 bitset(位集) 最终得分 100
用户昵称 梦那边的美好ME 运行时间 1.380 s
代码语言 C++ 内存使用 16.11 MiB
提交时间 2026-02-28 12:57:43
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ui int
#define ll long long

map<pair<ui,ui>,pair<ui,ll> > f;
vector<vector<ui> > a;

ll n,m,k,x,y,z;
ll ans;
bool check1=1,check2;

ll read(){
	ll res=0;
	char c=getchar();
	while (isdigit(c)){
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}

void solve(){
	ui l=1,r=n;
	ll res=0;
	for (register ui i=1;i<=k;i++){
		if (!check2&&i>1){
			l=(l*x+res*y+z)%n+1;
			r=(r*y+res*z+x)%n+1;
		}else{
			check2=0;
		}
		ui al=min(l,r),ar=max(l,r);
		res=0;
		ui rr=0;
		for (register ui j=1;j<=m;j++){
			rr=a[j][ar-1];
			if (al>1) rr-=a[j][al-2];
			if (rr==0||rr==ar-al+1) res++;
		}
		if (check1&&f[{l,r}].first){
			check2=1;
			check1=0;
			ui lth=i-f[{l,r}].first;
			ans+=(ans-f[{l,r}].second)*((k-i+1)/lth);
			i=i+lth*((k-i+1)/lth)-1;
		}else{
			f[{l,r}]={i,ans};
			ans+=res;
		}
	}
}

int main(){
	// freopen("in.in","r",stdin);
	freopen("bitset.in","r",stdin);
	freopen("bitset.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	a.resize(m+100);
	for (register int i=0;i<n;i++){
		for (register int j=1;j<=m;j++){
			char c;
			cin>>c;
			if (i!=0) a[j].push_back(a[j][i-1]+c-'0');
			else a[j].push_back(c-'0');
		}
	}
	cin>>k>>x>>y>>z;
	solve();
	cout<<ans;
	return 0;
}