0还是1

NC54340. 0还是1

描述

给出一个长度为n的操作序列。每个位置为“&”,“|”,“^”中的一个。&表示按位与，|表示按位或，^表示按位异或。
定义一个长度为n+1的01数列(即该数列只包含0和1)是合法的，当且仅当将该操作序列插入这个长度为n+1的数列后，运算结果为1。
具体的讲，如果给出的操作序列为“&|^”,将其插入到序列1010中进行运算:1&0|1^0=1。所以1010就是操作序列“&|^”的一个合法序列。

这里的运算不考虑运算符之间的优先级，即全部为自左向右依次进行运算。

现在你需要统计对于一个给定的操作序列，有多少个合法序列。
由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的结果。

点击下载大样例

输入描述

第一行一个正整数n,表示给出的操作序列的长度。
第二行一个长度为n的字符串，表示给出的操作序列。

输出描述

一行一个整数，表示答案对取模后的结果。

示例1

输入:

3
&|^

输出:

说明:

合法的01序列有:
0001
0010
0101
0110
1001
1010
1100
1110

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 142ms, 内存消耗: 9336K, 提交时间: 2020-01-15 13:18:49

#include<bits/stdc++.h>
const int mod=1e9+7;
int n,l=1,r=1;
char s[10000005];
int main(){
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;++i){
        if(s[i]=='|')
            r=(r*2%mod+l)%mod;
        if(s[i]=='&')
            l=(l*2%mod+r)%mod;
        if(s[i]=='^')
            l=(l+r)%mod,r=l;
    }
    printf("%d",r);
}

C++11(clang++ 3.9) 解法, 执行用时: 130ms, 内存消耗: 18188K, 提交时间: 2020-02-25 16:23:20

#include<bits/stdc++.h>
const int mod=1e9+7;
int n,l=1,r=1;
char s[10000005];
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;++i)
	{
		if(s[i]=='|')
		r=(r*2%mod+l)%mod;
		if(s[i]=='&')
		l=(l*2%mod+r)%mod;
		if(s[i]=='^')
		l=(l+r)%mod,r=l;
	}
	printf("%d",r);
}