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

全部评论

相关推荐

10-25 12:05
已编辑
湖南科技大学 Java
若梦难了:我有你这简历,已经大厂乱杀了
点赞 评论 收藏
分享
11-08 13:58
门头沟学院 Java
程序员小白条:竟然是蓝桥杯人才doge,还要花钱申领的offer,这么好的公司哪里去找
点赞 评论 收藏
分享
希望各位大哥分享一下自己的看法,对于机器人行业确实不太了解
绝顶但不聪明:如果是机器人相关岗位,优先优必选(专门***器人的),其他岗位选小米
投递小米集团等公司10个岗位 > 牛客解忧铺 牛客在线求职答疑中心
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务