[ARC150E] Weathercock

[ARC150E] Weathercock

下面的叙述中，数组均为 \(1\)-index。

考虑 \(k=1\)。

首先考虑将 \(L\) 记为 \(-1\)，\(R\) 记为 \(1\)，求出前缀和数组 \(s\)。

显然，对于一个位置为 \(x\) 的人，其转向条件：

• \(s_x = L\) 时，\(s_{x-1} > 0\)，即 \(s_x \geq 0\)

• \(s_x = R\) 时，\(s_n - s_x < 0\)，即 \(s_x > s_n\)

接下来我们钦定 \(s_n \geq 0\)，若否，则可以通过以下过程取反 \(s_n\)：

• 将 \(s\) 中的 \(L\) 变 \(R\)，\(R\) 变 \(L\)，再将 \(s\) 翻转。

显然这个过程相当于连人带头翻转序列，答案不变，且此时 \(s_n\) 必然取反。

接下来考虑模拟一次操作的过程，我们需要画出折线图。

我们以 \(LRRRLRRLRLRRRLRRLLRLLL\) 为例，其折线图如下：

对于一段向右下的线，其右端点 \(\geq 0\) 即可转向。

对于一段向右上的线，其左端点 \(\geq s_n\) 即可转向。

首先考虑 \(\geq s_n\) 的部分，本质上就是对 \(s_n\) 以上的部分转向：

容易观察出此时 \(s_n\) 是 \(s\) 的最大值，同时最后一个人接下来必然一直面向右边。

接下来的修改，只会把一些向右下的线向上翻转，而这不会改变 \(s_n\) 最大值的地位。

也就是说，在第一次操作之后的所有操作中，不存在 \(\geq s_n\) 转向的情况。

同时，可以发现在所有操作中，\(s_n \geq 0\) 的性质仍然保持。

接下来我们的每次操作就简单了，需要把两条线中间向右下的斜线翻转。

操作进行 \(+\infty\) 轮，每条向右下的线最多只会被翻转一次，只需要判断是否会被翻转即可。

首先我们容易观察到，如果当前线段在本轮可以被翻转，则以后的轮次均可以被翻转。

同时，此时我们只需要考虑 \(\geq 0\) 的性质，因此我们得到如下结论：

• 从第一段 \(\geq 0\) 的线开始，后面的所有线都会变成右上方向

接下来考虑 \(k \geq 1\)，分两种情况考虑。

• \(s_n = 0\)，此时不会出现第二种变换，答案容易计算。

• \(s_n > 0\)，首先第一种变换翻转的部分可以确定，第一段 \(\geq 0\) 的线必然在第一部分

至此本题结束，细节见代码。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,s_n;
char s[200010];
int height[200010];
void solve1(){
	int pos=0;
	for(int i=1;i<=n;i++){
		int new_pos=pos;
		if(s[i]=='L'){
			new_pos--;
		} 
		else{
			new_pos++;
		}
		height[i]=min(pos,new_pos);
		pos=new_pos;
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(height[i]>=s_n){
			ans+=k;
		}
	}
	printf("%lld\n",ans%998244353);
}
int cnt[200010];
void solve2(){
	int pos=0;
	long long ans=0;
	for(int i=1;i<=n;i++){
		int new_pos=pos;
		if(s[i]=='L'){
			ans+=k;
			new_pos--;
		} 
		else{
			new_pos++;
		}
		height[i]=min(pos,new_pos);
		pos=new_pos;
		if(height[i]>=s_n){
			cnt[height[i]]++;
		}
	}
	for(int i=0;i<n;i++){
		long long tot=min(k,i/s_n);
		ans+=tot*cnt[i];
	}
	for(int i=1;i<=n;i++){
		if(height[i]>=0){
			break;
		}
		if(s[i]=='L'){
			ans--;
		}
	}
	printf("%lld",ans%998244353);
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		cin>>s[i];
		if(s[i]=='L'){
			s_n--;
		}
		else{
			s_n++;
		}
	}
	if(s_n<0){
		reverse(s+1,s+n+1);
		for(int i=1;i<=n;i++){
			if(s[i]=='L'){
				s[i]='R';
			}
			else{
				s[i]='L';
			}
		}
		s_n*=-1;
	}
	if(s_n==0){
		solve1();
	}
	else{
		solve2();
	}
	return 0;
}