姬路瑞希

先对

k=1

的情况打个表，然后发现很多情况都不超过

3

次就能够得到答案。

考虑

k

很大的情况，容易发现不同的段之间的影响在于字符 L 和字符 R 的个数之差，如果这俩相等答案就是原序列的答案乘个

k

就可以了。

如果有差异，我们假设 R 的个数更多，那么假设到很后面很后面，这个时候字符 L 左边的 R 的个数是一定比 L 的个数要多的，而他被扭成 R 之后就再也没有人能够把他变成 L 了，所以除了最左边一部分的点，别的点就是 L 全部变成 R，这个就是总变化次数。

然后这样显然是不对的，为啥嘞，因为在最右边有一些边界情况可能是一个 R 变成了 L，我们要把这些情况都加上，考虑一个 R 如果要变成 L，那肯定是在第一轮变，而且对于位置相同的 R 肯定是变一段后缀，因为越往前就会有越多积淀的 L 在那里候着，直接二分这个东西就可以了。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
string S,T;
int suf[1000005];
int pre[1000005];
const int inf=1e18;
int all=0;
int solve(string T){
    int cntL=0;
    for(int i=0;i<T.size();i++){
        if(T[i]=='L')cntL++;
    }
    int ans=0;
    int neta=0;
    while(true){
        pre[0]=(T[0]=='R');
        for(int i=1;i<T.size();i++){
            pre[i]=pre[i-1]+(T[i]=='R');
        }
        suf[T.size()]=0;
        for(int i=T.size()-1;i>=0;i--){
            suf[i]=suf[i+1]+(T[i]=='L');
        }
        bool flg=false;
        for(int i=0;i<T.size();i++){
            if(T[i]=='L'){
                if(pre[i]>i-pre[i]){
                    T[i]='R';
                    ans++;
                    flg=true;
                }
            }
            else{
                if(suf[i]>T.size()-i-1-suf[i]){//
                    T[i]='L';
                    ans++;
                    neta++;
                    flg=true;
                }
            }
        }
        if(!flg)break;
    }
    for(int i=0;i<T.size();i++)if(T[i]=='L')all++;
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    cin>>S;
    int cntL=0,cntR=0;
    for(int i=0;i<n;i++){
        if(S[i]=='L')cntL++;
        else cntR++;
    }
    if(cntL==cntR){
        int tmp=solve(S);
        if(inf/k<tmp){
            puts("-1");
            return 0;
        }
        printf("%lld\n",tmp*k%998244353);
        return 0;
    }
    if(cntL>cntR){
        int st=0,ed=n-1;
        while(st<ed)swap(S[st++],S[ed--]);
        for(int i=0;i<n;i++){
            if(S[i]=='L')S[i]='R';
            else S[i]='L';
        }
        swap(cntL,cntR);
    }
    pre[0]=(S[0]=='R');
    for(int i=1;i<n;i++){
        pre[i]=pre[i-1]+(S[i]=='R');
    }
    suf[n]=0;
    for(int i=n;i>=1;i--){
        suf[i-1]=suf[i]+(S[i-1]=='L');
    }
    int neta=0;
    for(int i=0;i<n;i++){
        if(S[i]=='L')continue;
        int lt=0,rt=k+1;
        while(lt+1<rt){
            int mid=lt+rt>>1;
            int id=(mid-1)*n+i;
            int num=(k-mid)*cntL+suf[i];
            int need=n*k-1-id;
            if(num*2>need){
                rt=mid;
            }
            else{
                lt=mid;
            }
        }
        neta+=(k-rt+1);
    }
    int ans=cntL*k+2*neta;
    solve(S);
    printf("%lld\n",(ans-all)%998244353);
    return 0;
}

文章操作

相关推荐

评论

姬路瑞希