| 比赛 |
寒假集训4 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
bitset(位集) |
最终得分 |
100 |
| 用户昵称 |
dbk |
运行时间 |
1.208 s |
| 代码语言 |
C++ |
内存使用 |
27.42 MiB |
| 提交时间 |
2026-02-28 09:02:25 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
long long n, m, k, l, r, x, y, z, q, a, b, key, total;
long long ans;
char str[100010];
unordered_map<long long, int> ha;
int **sum;
int main(){
freopen("bitset.in", "r", stdin);
freopen("bitset.out", "w", stdout);
scanf("%lld%lld", &n, &m);
sum = new int*[n + 10];
for(int i = 0; i <= n + 9; i++){
sum[i] = new int[m + 10]();
}
for(int i = 1;i <= n;i++){
scanf("%s", str);
for(int j = 0;j < m;j++){
sum[i][j + 1] = (str[j] - '0');
sum[i][j + 1] += sum[i - 1][j + 1];
}
}
scanf("%lld%lld%lld%lld", &k, &x, &y, &z);
for(int i = 1;i <= k;i++){
if(i == 1){
l = 1, r = n;
a = 1, b = r;
}
else{
l = ((a * x + q * y + z) % n + 1);
r = ((b * y + q * z + x) % n + 1);
a = l, b = r;
}
if(l > r) swap(l, r);
long long key = l * n + r;
auto it = ha.find(key);
if(it != ha.end()){
q = it->second;
ans += q;
continue ;
}
q = 0;
long long len = r - l + 1;
for(int j = 1;j <= m;j++){
total = sum[r][j] - sum[l - 1][j];
if(total == len || total == 0) q++;
}
ha[key] = q;
ans += q;
}
printf("%lld\n", ans);
for(int i = 0; i <= n + 9; i++){
delete[] sum[i];
}
delete[] sum;
return 0;
}