T1 数数
【问题描述】
fadbec 很善于数数，⽐如他会数将 a 个红球，b 个黄球，c 个蓝球，d 个绿球排成⼀列，任意相邻不同⾊的数⽬。 现在 R 君不知道 fadbec 数的对不对，想让你也算⼀算。 由于数字⽐较⼤，所以请输出除以 109 + 7 的余数。
【输入格式】
⼀⾏四个正整数 a,b,c,d。
【输出格式】
输出包含⼀个整数，表⽰答案。
【样例输入 1】
1 1 1 2
【样例输出 1】
36
【数据规模及约定】
对于前 30% 的数据，1 ≤ a,b,c,d ≤ 3。 对于前 100% 的数据，1 ≤ a,b,c,d ≤ 30。
这个题纯用组合数学是比较麻烦的，因为插入之后或许原先同种颜色相邻的情况中间插入新颜色，那种情况就合法了，所以不好推。
但是看到这个题的数据范围我们可以想到高维DPqwq。。。。
DP的话每次放入的话可以一个一个地考虑，所以比较方便。。。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
int a,b,c,d;
const LL mod = 1e9+7;
LL dp[35][35][35][35][4];
int sum(int a,int b,int c,int d,int k){
if(a+b+c+d == 0) return 1;
LL sum = 0;
for(int i = 0;i<4;i++){
if(k!=i) sum+= dp[a][b][c][d][i];
}
return sum%mod;
}
int main(){
//freopen("count.in","r",stdin);
//freopen("count.out","w",stdout);
cin >> a >> b >> c >> d;
int l = a+b+c+d;
for(int i=1;i<=l;i++){
for(int n1=0; n1<=a && n1<=i;n1++){
for(int n2=0;n2<=b && n1+n2 <= i;n2++){
for(int n3=0;n3<=c && n1+n2+n3 <= i;n3++){
int n4 = i-n1-n2-n3;
if(n1>0){
dp[n1][n2][n3][n4][0] = sum(n1-1,n2,n3,n4,0);
}
if(n2>0){
dp[n1][n2][n3][n4][1] = sum(n1,n2-1,n3,n4,1);
}
if(n3>0){
dp[n1][n2][n3][n4][2] = sum(n1,n2,n3-1,n4,2);
}
if(n4>0){
dp[n1][n2][n3][n4][3] = sum(n1,n2,n3,n4-1,3);
}
}
}
}
}
LL ans = sum(a,b,c,d,-1);
cout<<ans<<endl;
return 0;
}