| 比赛 |
寒假集训4 |
评测结果 |
MMMMMMMMMM |
| 题目名称 |
bitset(位集) |
最终得分 |
0 |
| 用户昵称 |
FakeNews |
运行时间 |
0.009 s |
| 代码语言 |
C++ |
内存使用 |
1.37 MiB |
| 提交时间 |
2026-02-28 12:27:10 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define maxn 10000005
#define ll long long
int n,m,q;
int x,y,z;
int l,r;
ll a=1,b;
ll mod;
int ans,tot=0;
vector<int>p[maxn];
int c[maxn];
int solve(int l,int r){
int sum=0;
for(int i=1;i<=m;i++){
int u=p[i][r]-p[i][l-1];
if(u==0||u==r-l+1){
sum++;
}
}
return sum;
}
struct node{
int x,y;
friend bool operator<(node u,node v){
if(u.x==v.x){
return u.y<v.y;
}
return u.x<v.x;
}
};
map<node,int>num;
void col(int u,int k){
for(int i=u,j=k;i<=q;i++,j++){
tot+=c[j];
if(j==u-1){
j=0;
}
}
}
int main(){
freopen("bitset.in","r",stdin);
freopen("bitset.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
mod=n;
b=n;
for(int i=1;i<=m;i++){
p[i].push_back(0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char x;
cin>>x;
if(x=='1'){
p[j].push_back(p[j][i-1]+1);
}
else{
p[j].push_back(p[j][i-1]);
}
}
}
cin>>q;
cin>>x>>y>>z;
x%=mod,y%=mod,z%=mod;
for(int i=1;i<=q;i++){
if(i>1){
a=((a*x)%mod+(ans*y)%mod+z)%mod+1;
b=((b*y)%mod+(ans*z)%mod+x)%mod+1;
}
l=min(a,b),r=max(a,b);
if(num[{l,r}]){
col(i,num[{l,r}]);
cout<<tot;
return 0;
}
num[{l,r}]=i;
ans=solve(l,r);
c[i]=ans;
tot+=ans;
}
cout<<tot;
return 0;
}