非常厉害的一道题。
考虑无解是什么情况？ R 的个数超过 \(2^{n-1}\)
先考虑如何判定。从前往后考虑，如果遇到一个 B，那么如果后面有 R，就选最靠前的 R，否则选最靠后的一个 B.如果遇到 R，就选最靠后的一个 B。
但是这个判定很繁琐。我们考虑求出一个合法序列，使得他的 B 尽量靠后。设长度为 \(2^i\) 的 B 尽量靠后的串为 \(t_i\)，那么 \(t_0=\)R，考虑从 \(t_{i-1}\) 扩展到 \(t_i\).
遍历 \(t_{i-1}\)，那么遇到一个 R 的时候，他匹配的是最远的 B,\(t_i\) 增加 R。遇到一个 B 的时候，他匹配最近的 R，所以增加 BR，剩下的用 B 补全即可。
然后有一个结论.考虑原串中前 \(2^{n-1}\) 个，设第 \(i\) 个 B 在 \(g_i\) 出， \(t_n\) 第 \(i\) 个 B 在 \(h_i\) 处。当且仅当 \(\forall i,g_i\le h_i\)，串合法。
感性理解一下，如果原串有个 B 在 \(t_n\) 的 B 的后面，那么他就匹配不到 R
所以最终答案就是原串的 B 和 \(t_n\) 的 B 的位置差加起来就行了。
// LUOGU_RID: 139274680
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,k,g[N],c;
long long ans;
char s[N],t[19][N];
int main()
{
scanf("%d%s",&n,s+1);
for(int i=1;s[i];i++)
if(s[i]=='R')
++c;
if(c>(1<<n-1))
return puts("-1"),0;
t[0][1]='R';
for(int i=1;i<=n;i++)
{
m=0;
for(int j=1;j<=(1<<i-1);j++)
{
if(t[i-1][j]=='B')
t[i][++m]='B',t[i][++m]='R';
else
t[i][++m]='R';
}
while(m<(1<<i))
t[i][++m]='B';
}
m=0;
for(int i=1;i<=(1<<n);i++)
if(t[n][i]=='B')
g[++m]=i;
for(int i=1;i<=(1<<n);i++)
{
if(s[i]=='B')
{
++k;
if(k>m)
break;
ans+=max(i-g[k],0);
}
}
printf("%lld",ans);
}