Submission #56414

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
string s;
int memo[300][300][2];
void dp(int l, int r){
if(l == r){
if(s[l] == '0'){
memo[l][l][0] = 1;
memo[l][l][1] = 0;
}else{
memo[l][l][0] = 0;
memo[l][l][1] = 1;
}
return;
}
if(memo[l][r][0] != -1) return;
int ans0 = 0;
int ans1 = 0;
for(int i = l;i <= r;i++){
if(!(s[i] == '0' || s[i] == '1')){
dp(l, i-1);
dp(i+1, r);
if(s[i] == '|'){
ans0 += memo[l][i-1][0] * memo[i+1][r][0] % MOD;
ans0 %= MOD;
ans1 += memo[l][i-1][0] * memo[i+1][r][1] % MOD;
ans1 %= MOD;
ans1 += memo[l][i-1][1] * memo[i+1][r][0] % MOD;
ans1 %= MOD;
ans1 += memo[l][i-1][1] * memo[i+1][r][1] % MOD;
ans1 %= MOD;
}else if(s[i] == '&'){
ans0 += memo[l][i-1][0] * memo[i+1][r][0] % MOD;
ans0 %= MOD;
ans0 += memo[l][i-1][0] * memo[i+1][r][1] % MOD;
ans0 %= MOD;
ans0 += memo[l][i-1][1] * memo[i+1][r][0] % MOD;
ans0 %= MOD;
ans1 += memo[l][i-1][1] * memo[i+1][r][1] % MOD;
ans1 %= MOD;
}else{
ans0 += memo[l][i-1][0] * memo[i+1][r][0] % MOD;
ans0 %= MOD;
ans1 += memo[l][i-1][0] * memo[i+1][r][1] % MOD;
ans1 %= MOD;
ans1 += memo[l][i-1][1] * memo[i+1][r][0] % MOD;
ans1 %= MOD;
ans0 += memo[l][i-1][1] * memo[i+1][r][1] % MOD;
ans0 %= MOD;
}
}
}
memo[l][r][0] = ans0;
memo[l][r][1] = ans1;
return;
}
signed main(){
cin >> s;
memset(memo, -1, sizeof(memo));
dp(0, s.size()-1);
cout << memo[0][s.size()-1][1] << endl;
return 0;
}

ステータス

項目 データ
問題 0570 - 1
ユーザー名 ei1719
投稿日時 2019-11-13 18:45:48
言語 C++14
状態 Accepted
得点 1
ソースコード長 2091 Byte
最大実行時間 50 ms
最大メモリ使用量 1880 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00.in AC 50 ms 1880 KB
1
01.in AC 31 ms 1856 KB
1
02.in AC 25 ms 1832 KB
1
03.in AC 24 ms 1808 KB
1
04.in AC 26 ms 1776 KB
1