1

Fantasy Strange Tree

http://www.nowcoder.com/questionTerminal/4a469dacd347483da0e848ef59aa5a45

include<bits/stdc++.h>

define ll long long

using namespace std;
const int p=1e9+7;
char s[200010],t[200010];
int n,m,i,j,op,k,ans,fac[200010],nt[200010][2],sz[200010],f[200010];
int main(){
scanf("%s",s+1);
scanf("%s",t+1);
n=strlen(s+1);m=strlen(t+1);
j=n;
fac[0]=1;
for(i=1;i<=m;i++)fac[i]=fac[i-1]*2%p;
for(i=m;i;i--){
sz[i]=sz[i+1];
nt[i][0]=nt[i+1][0];nt[i][1]=nt[i+1][1];
f[i]=(f[nt[i][0]]+f[nt[i][1]]+1)%p;
if(t[i]=='L')nt[i][0]=i;
if(t[i]=='R')nt[i][1]=i;
if(t[i]!='U')sz[i]++;
}
ans=(f[nt[1][0]]+f[nt[1][1]]+1)%p;
for(i=1;i<=m;i++){
//printf("%lld\n",ans);
if(t[i]=='U'){
ans=(ans+1)%p;
if(s[j]=='L')op=0;
else op=1;
if(nt[i][op^1]){
//printf("%d %d\n",i,j);
k=nt[i][op^1];
ans=(ans+f[k])%p;
}
j--;
}
if(!j)break;
}
printf("%d",ans);
}

全部评论

相关推荐

昨天 14:22
门头沟学院 Java
大厂 测开 24*16离家近的事业编(大概只有大厂的1/4) 硕士
点赞 评论 收藏
分享
死在JAVA的王小美:哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈,我也是,让我免了一轮,但是硬气拒绝了
点赞 评论 收藏
分享
11-01 08:48
门头沟学院 C++
伤心的候选人在吵架:佬你不要的,能不能拿户口本证明过户给我。。球球了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务