1 #include<cstdio>
2 #include<cctype>
3 using namespace std ;
4
5 struct state {
6 int len ;
7 int p ;
8 int h ;
9 int last ;
10 state (
const int len ,
const int p ,
const int h ,
11 const int last ) : len ( len ) , p ( p ) , h ( h ) ,
12 last ( last ) {} ;
13 int hash ()
const {
14 return len *
6000 +
250 * p + h *
7 +
last ;
15 //this is a perfect hash
16 }
17 } ;
18
19 const int MAXN =
25 ;
20 const long long MOD = (
long long ) ( 1e9 +
7 ) ;
21 int N , M , K ;
22
23 int G [ MAXN ] [ MAXN ] ;
24 char s [ MAXN ] ;
25
26 const int size_of_dp =
2000000 ;
27 long long dp [ size_of_dp ] ;
28 bool vis [ size_of_dp ] ;
29
30 int main () ;
//complete checking checked
31 long long D (
const state o ) ;
//complete
32 long long T (
const state o ,
const int p ) ;
//complete
33 long long T0 (
const state o ,
const int p ) ;
//complete
34 long long T1 (
const state o ,
const int p ) ;
//complete
35 long long T2 (
const state o ,
const int p ) ;
//complete
36 long long T3 (
const state o ,
const int p ) ;
//complete
37 long long T4 (
const state o ,
const int p ) ;
//complete
38 long long T5 (
const state o ,
const int p ) ;
//complete
39
40 long long D (
const state o ) {
41 if ( vis [ o . hash () ] )
return dp [ o . hash () ] ;
42 vis [ o . hash () ] =
true ;
43 if ( o . len ==
K ) {
44 if ( o . h ==
0 && o . last <
3 )
45 return dp [ o . hash () ] =
1 ;
46 else return 0 ;
47 }
48 long long ans =
0 ;
49 for (
int i =
1 ; i <= N ; ++
i )
50 if ( G [ o . p ] [ i ] ) {
51 ans +=
T ( o , i ) ;
52 ans %=
MOD ;
53 }
54 #ifdef DEBUG
55 printf (
"(%d,%d,%d,%d)=%lld\n" , o . len , o . p , o . h , o . last , ans ) ;
56 #endif
57 return dp [ o . hash () ] =
ans ;
58 }
59
60 long long T (
const state o ,
const int p ) {
61 switch ( o . last ) {
62 case 0 :
return T0 ( o , p ) ;
63 case 1 :
return T1 ( o , p ) ;
64 case 2 :
return T2 ( o , p ) ;
65 case 3 :
return T3 ( o , p ) ;
66 case 4 :
return T4 ( o , p ) ;
67 case 5 :
return T5 ( o , p ) ;
68 }
69 return 233 ;
70 }
71
72 int main () {
73 freopen (
"trace.in" ,
"r" , stdin ) ;
74 freopen (
"trace.out" ,
"w" , stdout ) ;
75 scanf (
"%d%d%d" , & N , & M , &
K ) ;
76 scanf (
"%s" , s +
1 ) ;
77 while ( M --
) {
78 int a , b ;
79 scanf (
"%d%d" , & a , &
b ) ;
80 G [ a ] [ b ] = G [ b ] [ a ] =
1 ;
81 }
82 for (
int i =
1 ; i <= N ; ++ i ) G [
0 ] [ i ] =
1 ;
83 printf (
"%lld\n" , D ( state (
0 ,
0 ,
0 ,
3 ) ) ) ;
84 return 0 ;
85 }
86
87 long long T0 (
const state o ,
const int p ) {
88 if ( s [ p ] ==
')' && o . h >
0 )
89 return D ( state ( o . len +
1 , p , o . h -
1 ,
2 ) ) ;
90 if ( s [ p ] ==
'+' || s [ p ] ==
'-' ||
91 s [ p ] ==
'*' || s [ p ] ==
'/' )
92 return D ( state ( o . len +
1 , p , o . h ,
5 ) ) ;
93 return 0 ;
94 }
95
96 long long T1 (
const state o ,
const int p ) {
97 if ( isdigit ( s [ p ] ) )
98 return D ( state ( o . len +
1 , p , o . h ,
1 ) ) ;
99 if ( s [ p ] ==
'+' || s [ p ] ==
'-' ||
100 s [ p ] ==
'*' || s [ p ] ==
'/' )
101 return D ( state ( o . len +
1 , p , o . h ,
5 ) ) ;
102 if ( s [ p ] ==
')' && o . h >
0 )
103 return D ( state ( o . len +
1 , p , o . h -
1 ,
2 ) ) ;
104 return 0 ;
105 }
106
107 long long T2 (
const state o ,
const int p ) {
108 if ( s [ p ] ==
'+' || s [ p ] ==
'-' ||
109 s [ p ] ==
'*' || s [ p ] ==
'/' )
110 return D ( state ( o . len +
1 , p , o . h ,
5 ) ) ;
111 if ( s [ p ] ==
')' && o . h >
0 )
112 return D ( state ( o . len +
1 , p , o . h -
1 ,
2 ) ) ;
113 return 0 ;
114 }
115
116 long long T3 (
const state o ,
const int p ) {
117 if ( s [ p ] ==
'(' )
118 return D ( state ( o . len +
1 , p , o . h +
1 ,
3 ) ) ;
119 if ( s [ p ] ==
'-' )
120 return D ( state ( o . len +
1 , p , o . h ,
4 ) ) ;
121 if ( s [ p ] ==
'0' )
122 return D ( state ( o . len +
1 , p , o . h ,
0 ) ) ;
123 if ( s [ p ] >=
'1' && s [ p ] <=
'9' )
124 return D ( state ( o . len +
1 , p , o . h ,
1 ) ) ;
125 return 0 ;
126 }
127
128 long long T4 (
const state o ,
const int p ) {
129 if ( s [ p ] ==
'0' )
130 return D ( state ( o . len +
1 , p , o . h ,
0 ) ) ;
131 if ( s [ p ] >=
'1' && s [ p ] <=
'9' )
132 return D ( state ( o . len +
1 , p , o . h ,
1 ) ) ;
133 if ( s [ p ] ==
'(' )
134 return D ( state ( o . len +
1 , p , o . h +
1 ,
3 ) ) ;
135 return 0 ;
136 }
137
138 long long T5 (
const state o ,
const int p ) {
139 if ( s [ p ] ==
'0' )
140 return D ( state ( o . len +
1 , p , o . h ,
0 ) ) ;
141 if ( s [ p ] >=
'1' && s [ p ] <=
'9' )
142 return D ( state ( o . len +
1 , p , o . h ,
1 ) ) ;
143 if ( s [ p ] ==
'(' )
144 return D ( state ( o . len +
1 , p , o . h +
1 ,
3 ) ) ;
145 return 0 ;
146 }
今天Z老把BJOI的题当练习给我们做，结果这道题只有50分。检查出来多写了一个+1，一脸。。
转载于:https://www.cnblogs.com/Christopher-Cao/p/5292338.html
