比赛 寒假集训4 评测结果 AAAAAAAAAA
题目名称 bitset(位集) 最终得分 100
用户昵称 xuyuqing 运行时间 3.129 s
代码语言 C++ 内存使用 36.54 MiB
提交时间 2026-02-28 09:50:06
显示代码纯文本

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector> 

using namespace std;

int n;
int m;
vector<vector<char>> nums;
vector<vector<int>> magic;
int k;
long long x;
long long y;
long long z;
long long a;
long long b;
long long res;

long long solve (int a, int b) {
    long long ans = 0;
    int l = min (a, b);
    int r = max (a, b);
    ans = upper_bound (magic[r].begin() + 1, magic[r].end(), l) - magic[r].begin() - 1;
    return ans;
}

int main () {
    
    freopen ("bitset.in", "r", stdin);
    freopen ("bitset.out", "w", stdout);
    
    cin >> n >> m;
    nums.resize(n + 1);
    magic.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        nums[i].resize(m + 1);
        magic[i].resize(m + 1);
    }
    
    string str;
    for (int i = 1; i <= n; i++) {
        cin >> str;
        for (int j = 1; j <= m; j++) {
            nums[i][j] = str[j - 1] - '0';
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (nums[i][j] == nums[i - 1][j]) {
                magic[i][j] = magic[i - 1][j] + 1;
            }
            else {
                magic[i][j] = 1;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            magic[i][j] = i - magic[i][j] + 1;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        sort (magic[i].begin(), magic[i].end());
    }
    
    cin >> k >> x >> y >> z;
    
    a = 1;
    b = n;
    for (int i = 1; i <= k; i++) {
        long long ans = solve (a, b);
        res += ans;
        a = (((a * x % n + ans * y % n) % n) + z % n) % n + 1;
        b = (((b * y % n + ans * z % n) % n) + x % n) % n + 1;
    }
    
    cout << res << endl;
    
    return 0;
}