|
|
1 #include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6#define madd(a,b) a=(a+b)%MOD
7
8const int MOD=1000000007;
9const int MAXC=55, MAXH=75, MAXW=10, MAXB=15;
10long g[MAXC], Comb[MAXC][MAXC];
11int dp[MAXW][MAXB][MAXC][MAXH][MAXW][2];
12
13class SkewedPerspective
14   {
15
16public:
17 int countThem(vector <int> cubes, int B, int w)
18  {
19 int n=cubes.size(), total=0;
20 int i, j, k;
21 for(i=0; i<n; i++) total+=cubes[i];
22
23 for(i=0; i<=total; i++)
24 for(j=0; j<=i; j++)
25 Comb[i][j]=(j?(Comb[i-1][j]+Comb[i-1][j-1])%MOD:1);
26 g[0]=1;
27 for(i=0; i<n; i++)
28 for(j=total; j; j--)
29 for(k=1; k<=j && k<=cubes[i]; k++)
30 g[j]=(g[j]+g[j-k]*Comb[j][k])%MOD;
31
32 long ans=0;
33 dp[1][0][0][0][0][0]=1;
34 for(int tower=1; tower<=w; tower++)for(int black=0; black<=B; black++)
35 for(int color=0; color<=total; color++)for(int need=0; need<=total+black*2; need++)
36 for(int needOdd=0; needOdd<=tower; needOdd++)for(int lastBlack=0; lastBlack<2; lastBlack++)
37 {
38 int x=dp[tower][black][color][need][needOdd][lastBlack];
39 if(!x)continue;
40 //get result
41 if(black+color>0 && (B-black)*2+total-color>=need && total-color>=needOdd)
42 ans=(ans+g[color]*x)%MOD;
43 //put colored
44 madd(dp[tower][black][color+1][need][needOdd][0], x);
45 if(lastBlack) continue;
46 //put black
47 int layer=black*2+color-(tower-1);
48 for(int blackSize=1; blackSize+black*2<=B*2; blackSize++)
49 if(blackSize%2==0)
50 madd(dp[tower][black+blackSize/2][color][need][needOdd][1], x);
51 else
52 {
53 if(!layer && blackSize==1) continue; //"b1bbbb"
54 int needNow=(layer?layer-1:layer+1);
55 if(need+needNow<=total+B*2)
56 madd(dp[tower+1][black+(blackSize+1)/2][color][need+needNow][needOdd+needNow%2][1], x);
57 }
58
59 }
60 return int(ans);
61 }
62 };
63
64int main()
65{
66 SkewedPerspective a;
67 int cubes[]={1, 1, 0};
68 vector<int> t(cubes, cubes+3);
69
70 cout<<a.countThem(t, 1, 2)<<endl;
71 return 0;
72}
73
|