比赛 寒假集训4 评测结果 MMMMMMMMMM
题目名称 bitset(位集) 最终得分 0
用户昵称 PXCZM 运行时间 0.008 s
代码语言 C++ 内存使用 1.32 MiB
提交时间 2026-02-28 11:42:58
显示代码纯文本
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,x,y,z,l,r,u,v;
vector<bool>a[10000010];
vector<int>b[10000010];
ll ans,sum;
ll d[1010][1010];
int main()
{
    freopen("bitset.in","r",stdin);
    freopen("bitset.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            char tmp;cin>>tmp;
            a[i].push_back(tmp-'0');
            if(i==1) b[i].push_back(1);
            else b[i].push_back((a[i][j]==a[i-1][j]?b[i-1][j]+1:1));
        }
    if(n<=1000)
    {
        for(int i=1;i<=n;i++)
            for(int j=0;j<m;j++)
                d[i][b[i][j]]++;
        for(int i=1;i<=n;i++)
            for(int j=n;j>0;j--)
                d[i][j]+=d[i][j+1];
    }
    else
    {
        for(int i=1;i<=n;i++)
            sort(b[i].begin(),b[i].end());
    }
    u=l=1;v=r=n;
    cin>>k>>x>>y>>z;
    while(k--)
    {
        if(n<=1000) ans=d[r][r-l+1];
        else ans=m-(lower_bound(b[r].begin(),b[r].end(),r-l+1)-b[r].begin());
        sum+=ans;
        u=(u*x+ans*y+z)%n+1;
        v=(v*y+ans*z+x)%n+1;
        l=min(u,v);
        r=max(u,v);
    }
    cout<<sum;
    return 0;
}