比赛 寒假集训4 评测结果 AAAAAAAAAA
题目名称 bitset(位集) 最终得分 100
用户昵称 小福鑫 运行时间 1.450 s
代码语言 C++ 内存使用 38.58 MiB
提交时间 2026-02-28 10:42:14
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,x,y,z,sum;
signed 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;
    int**pos=new int*[n+2];
    for(int i=0;i<=n+1;i++){
        pos[i]=new int[m+2]();
    }
    string*s=new string[n+2];
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    for(int j=0;j<m;++j){
        pos[n][j]=n;
    }
    for(int i=n-1;i;--i){
        for(int j=0;j<m;++j){
            pos[i][j]=(s[i][j]==s[i+1][j])?pos[i+1][j]:i;
        }
    }
    for(int i=1;i<=n;++i){
        sort(pos[i],pos[i]+m);
    }
    cin>>q>>x>>y>>z;
    int a=1,b=n,ans=0;
    for(int i=1;i<=q;i++){
        if(i>1){
            a=(a*x+ans*y+z)%n+1;
            b=(b*y+ans*z+x)%n+1;
        }
        int l=min(a,b),r=max(a,b);
        ans=pos[l]+m-lower_bound(pos[l],pos[l]+m,r);
        sum+=ans;
    }
    cout<<sum;
}