Submission #23495

ソースコード

?
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
#include<bits/stdc++.h>
#define WARU 1000000007
using namespace std;
int memo[101][101][2],n,a[101];
char c[100];
long long int f(int l,int r,int num);
main(){
memset(memo,-1,sizeof(memo));
while(1){
scanf("%d%c",&a[n],&c[n]);
n++;
if(c[n-1]=='\n')break;
}
cout<<f(0,n-1,1)<<endl;
}
long long int f(int l,int r,int num){
if(memo[l][r][num]!=-1)return memo[l][r][num];
if(r-l==0){
return memo[l][r][num]=(a[l]==num);
}
else if(r-l==1){
int result;
if(c[l]=='&')result=a[l]&a[r];
else if(c[l]=='|')result=a[l]|a[r];
else result=a[l]^a[r];
return memo[l][r][num]=(result==num);
}
else{
long long int tmp,sum=0;
long long int lf,lt,rf,rt;
for(int i=l;i<r;i++){
lf=f(l,i,0);
lt=f(l,i,1);
rf=f(i+1,r,0);
rt=f(i+1,r,1);
if(c[i]=='&'){
if(num==1)tmp=(lt*rt)%WARU;
else tmp=((lt*rf)%WARU+(lf*rt)%WARU+(lf*rf)%WARU)%WARU;
sum=(sum+tmp)%WARU;
}
else if(c[i]=='|'){
if(num==1)tmp=((lt*rf)%WARU+(lf*rt)%WARU+(lt*rt)%WARU)%WARU;
else tmp=(lf*rf)%WARU;
sum=(sum+tmp)%WARU;
}
else{
if(num==1)tmp=((lt*rf)%WARU+(lf*rt)%WARU)%WARU;
else tmp=((lt*rt)%WARU+(lf*rf)%WARU)%WARU;
sum=(sum+tmp)%WARU;
}
}
return memo[l][r][num]=sum;
}
}

ステータス

項目 データ
問題 0570 - 1
ユーザー名 ei1516
投稿日時 2017-07-28 11:26:34
言語 C++11
状態 Accepted
得点 1
ソースコード長 1314 Byte
最大実行時間 45 ms
最大メモリ使用量 644 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00.in AC 45 ms 480 KB
1
01.in AC 28 ms 628 KB
1
02.in AC 16 ms 644 KB
1
03.in AC 16 ms 532 KB
1
04.in AC 16 ms 544 KB
1