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
75
76
77
78
79
80
81
82
| #include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n;
ll dp[12][51][51][51];
ll C[2005][2005];
void combination(int size) {
for (int i = 0; i < size; i++) C[i][0] = 1LL;
for (int i = 1; i < size; i++) {
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
}
ll dfs(int dep, int r, int g, int b) {
if(dp[dep][r][g][b] != -1) return dp[dep][r][g][b];
if(dep == n + 1) {
return dp[dep][r][g][b] = 1;
}
ll ret = 0;
if(r - dep >= 0) {
ret += dfs(dep + 1, r - dep, g, b);
}
if(g - dep >= 0) {
ret += dfs(dep + 1, r, g - dep, b);
}
if(b - dep >= 0) {
ret += dfs(dep + 1, r, g, b - dep);
}
if(dep % 2 == 0) {
if(r - dep / 2 >= 0 && g - dep / 2 >= 0) {
ret += dfs(dep + 1, r - dep / 2, g - dep / 2, b) * C[dep][dep/2];
}
if(g - dep / 2 >= 0 && b - dep / 2 >= 0) {
ret += dfs(dep + 1, r, g - dep / 2, b - dep / 2) * C[dep][dep/2];
}
if(r - dep / 2 >= 0 && b - dep / 2 >= 0) {
ret += dfs(dep + 1, r - dep / 2, g, b - dep / 2) * C[dep][dep/2];
}
}
if(dep % 3 == 0) {
if(r - dep / 3 >= 0 && g - dep / 3 >= 0 && b - dep / 3 >= 0) {
ret += dfs(dep + 1, r - dep / 3, g - dep / 3, b - dep / 3) * C[dep][dep/3] * C[dep - dep / 3][dep/3];
}
}
return dp[dep][r][g][b] = ret;
}
class ChristmasTree {
public:
long long decorationWays(int N, int red, int green, int blue) {
n = N;
combination(55);
memset(dp, -1, sizeof(dp));
return dfs(1, red, green, blue);
}
};
|