【题解】大括号

神仙(dp)题

可以观察得到就是最后肯定只剩下一种网友在走，所以我们对于两种网友分开(dp)。统计答案怎么办？可以知道一定存在一个分界线使得从此以后只剩下一种网友，我们可以通过枚举这个分界线来统计答案。

考虑从左向右(dp)向左的人，可以方便我们优化转移。设(dp(i,j))表示考虑前(i)个人，并且存在剩下(j)是强制在后面的相遇中死去。考虑如何转移：

当前(i)是一个(L):
- 免费得到一个向左走的人。所以转移是(dp(i,j)=dp(i-1,j+1))。新来的可以直接去死了(大雾)
当前(i)是一个(R)
- 枚举这个(R)会战胜多少个人，然后强制再死去(因为我们(dp)是向左的人，最后一定只有向左的人，所以不能有活着的大括号换行派)。所以转移是
[dp(i,j)=P(l win)dp(i-1,j)Sigma_k P(r win)^kdp(i-1,j+k) ]

这里有个越来越大的次方和(Sigma)，可以考虑前缀和优化。

最后统计答案，先枚举分界点(一定是一个(L)一个(R)的地方)，然后再把(dp1(?,1)dp2(?,1) Sigma)起来，因为我们知道这样最后就是(1v1)一定可以分出高下了。

右边同理。

考虑初始状态:

可以假装一个超级(dalao)在左边可以屠戮所有右边来的人，所以就是(dp(0,i)=P(i))，(实际上你是把概率直接提到最前面来了。)

#include<bits/stdc++.h>
using namespace std;  typedef long long ll;
template < class ccf > inline ccf qr(ccf ret){      ret=0;
      register char c=getchar();
      while(not isdigit(c)) c=getchar();
      while(isdigit(c)) ret=ret*10+c-48,c=getchar();
      return ret;
}inline int qr(){return qr(1);}
const int maxn=5e3+5;
int dp1[2][maxn];
int dp2[2][maxn];
int temp1[maxn];
int temp2[maxn];
int inv10,invlr;
int l,r;
bool data[maxn];
const ll mod=666623333;

inline char qrqr(){
      register char c=getchar();
      while(c!='R'&&c!='L')c=getchar();
      return c;
}

inline int Pow(int x,const int&p){register int ret=1;
      for(register int t=p;t;t>>=1,x=1ll*x*x%mod)
	    if(t&1) ret=1ll*ret*x%mod;
      return ret;
}

int main(){
#ifndef ONLINE_JUDGE
      freopen("letter.in","r",stdin);
      freopen("letter.out","w",stdout);
#endif
      int n=qr();l=qr();r=qr();
      inv10=Pow(1e5,mod-2LL);
      //cout<<inv10<<endl;
      invlr=Pow(l+r,mod-2LL);
      l=1ll*l*invlr%mod;
      r=1ll*r*invlr%mod;
      for(register int t=1;t<=n;++t)      
	    data[t]=(qrqr()=='L');
      bool now=1,last=0;
      for(register int t=1;t<=n;++t)
	    dp1[last][t]=1ll*qr(1)*inv10%mod;
      for(register int t=1;t<=n;++t)
	    dp2[last][t]=1ll*qr(1)*inv10%mod;
#define dp dp1
      for(register int T=1;T<=n;++T,swap(now,last)){
	    if(data[T]){
		  temp1[T+1]=dp[last][1];
		  for(register int t=1;t< n;++t)
			dp[now][t]=dp[last][t+1];
	    }
	    else
		  for(register int t=1,s=0;t<=n;++t)
			s=dp[now][t]=(1ll*s*r+1ll*dp[last][t]*l)%mod;
      }
#undef dp
      
#define dp dp2
      now=1,last=0;
      for(register int T=n;T;--T,swap(now,last)){
	    if(not data[T]){
		  temp2[T]=dp[last][1];
		  for(register int t=1;t< n;++t)
			dp[now][t]=dp[last][t+1];
	    }
	    else
		  for(register int t=1,s=0;t<=n;++t)
			s=dp[now][t]=(1ll*s*l+1ll*dp[last][t]*r)%mod;
      }
#undef dp
      int ans=0;
      for(register int t=1;t<=n;++t)
	    ans=(ans+1ll*temp1[t]*temp2[t])%mod;
       cout<<ans<<endl;
      return 0;
}

【题解】大括号

【题解】大括号

相关推荐