一道基础 dp 题远古 IOI 题。

用 $dp_{i,x,y}$ 表示考虑完了前 $i$ 位，以当前位结尾的后缀中 L 的个数减 P 的个数最大为 $x$，P 的个数减 L 的个数最大为 $y$，剩下的位有多少种合法的构造方案，由题意得 $0\le x,y<3$。直接暴力转移即可。

花园的序号 $=$ 字典序小于这个花园的个数 $+1$。考虑如何统计字典序小于这个花园的个数，可以枚举第一个不同的位，暴力求和即可。

代码：

#include<bits/stdc++.h>
#define mxn 1000003
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
int n,m,x,y,ans,f[mxn][3][3];
char s[mxn];
signed main(){
	scanf("%d%d%s",&n,&m,s+1);
	rept(i,0,3)rept(j,0,3)f[n][i][j]=1;
	drep(i,n-1,1){
		rept(x,0,3){
			rept(y,0,3){
				if(x!=2)f[i][x][y]=f[i+1][x+1][max(y-1,0)];
				if(y!=2)f[i][x][y]=(f[i][x][y]+f[i+1][max(x-1,0)][y+1])%m;
			}
		}
	}
	rep(i,1,n){
		if(s[i]=='L'){
			x++,y=max(y-1,0);
			if(x>2)break;
		}else{
			if(x!=2)ans=(ans+f[i][x+1][max(y-1,0)])%m;
			x=max(x-1,0),y++;
			if(y>2)break;
		}
	}
	cout<<(ans+1)%m;
	return 0;
}