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);
}

全部评论

相关推荐

争当牛马还争不上
码农索隆:1.把简历改哈 2.猛投,狠投 3.把基础打牢 这样你在有机会的时候,才能抓住
点赞 评论 收藏
分享
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务