JZOJ1266.玉米田

1 #include
2 #include
3 #include
4 #include <string>
5 #define LL long long
6 #define mo 100000000
7 using namespace std;
8 long long f[13][4100], e[13][4100], ans;
9 int n, m, a[13][13];
10 int pre[20];
11
12 void dfs(int h, int dep, int s, int choose)
13 {
14 if (dep > m)
15 {
16 e[h][&＃43;&＃43;e[h][0]] &＃61; s;
17 return;
18 }
19 if (a[h][dep] && !choose) dfs(h, dep &＃43; 1, s &＃43; pre[dep - 1], 1);
20 dfs(h, dep &＃43; 1, s, 0);
21 }
22
23 void pre_work()
24 {
25 pre[0] &＃61; 1;
26 for (int i &＃61; 1; i <&＃61; 18; i&＃43;&＃43;)
27 pre[i] &＃61; pre[i - 1] * 2;
28 for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
29 dfs(i, 1, 0, 0);
30 }
31
32 void dp()
33 {
34 for (int i &＃61; 1; i <&＃61; e[1][0]; i&＃43;&＃43;)
35 f[1][e[1][i]] &＃61; 1;
36 for (int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;)
37 {
38 for (int j &＃61; 1; j <&＃61; e[i][0]; j&＃43;&＃43;)
39 for (int k &＃61; 1; k <&＃61; e[i - 1][0]; k&＃43;&＃43;)
40 if ((e[i][j] & e[i - 1][k]) &＃61;&＃61; 0)
41 f[i][e[i][j]] &＃43;&＃61; f[i - 1][e[i - 1][k]];
42 }
43 ans &＃61; 0;
44 for (int i &＃61; 1; i <&＃61; e[n][0]; i&＃43;&＃43;)
45 ans &＃43;&＃61; f[n][e[n][i]], ans %&＃61; mo;
46 }
47
48 int main()
49 {
50 freopen("cowfood.in", "r", stdin);
51 freopen("cowfood.out", "w", stdout);
52 scanf("%d%d", &n, &m);
53 for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
54 {
55 for (int j &＃61; 1; j <&＃61; m; j&＃43;&＃43;)
56 scanf("%d", &a[i][j]);
57 }
58 pre_work();
59 dp();
60 printf("%lld", ans);
61 }