題目描述：
解N維遞推方程，滿足：
f(X1,X2,X3,?,Xn)=f(X1?1,X2,X3,?,Xn)+f(X1,X2?1,X3,?,Xn)+f(X1,X2,X3?1,?,Xn)+?+f(X1,X2,X3,?,Xn?1),(?Xi>=0)∧(?Xi>0)
f(0,0,0,?,0)=1,
f(X1,X2,X3,?,Xn)=0,?Xi<0;
輸入：
第一行一個(gè)整數(shù)T，表示有T組測(cè)試數(shù)據(jù)。
每組測(cè)試數(shù)據(jù)2行，第一行一個(gè)整數(shù)N。第二行有N個(gè)整數(shù)，表示X1...Xn。 1≤Xi≤50,1≤N≤50,1≤T≤100都是整數(shù)。
輸出：
每組數(shù)據(jù)輸出一行，只有一個(gè)整數(shù)，f(X1,X2...Xn)。最后的答案對(duì)10^9+7取余輸出。
樣例輸入：
4
1
8
2
1 2
3
1 1 1
10
10 10 10 10 10 10 10 10 10 10
樣例輸出：
1
3
6
453209373
問題分析：
先分析二維的情況
即：f(x,y) = f(x-1,y)+f(x,y-1);
該函數(shù)可抽象為下圖的二維空間的，從左上角的起點(diǎn)至右下角只能向x或y方向走的路徑總數(shù)，易知存在左上角至任意一點(diǎn)的路徑數(shù)為該點(diǎn)上方的路徑種數(shù)和該點(diǎn)左方的路徑種數(shù)。
二維空間
故：問題轉(zhuǎn)化為求起點(diǎn)至某點(diǎn)按照上述走法的路徑總數(shù)。
又由圖可知每一條路徑由x方向走4步，y方向走4步的排列組合
即：f(x,y) = C(x,x+y)*C(y,y);或f(x,y) = C(y,x+y)*C(x,x);
推而廣之：n維空間即
f(x1,x2,x3,x4……xn) = C(x1,sum)*C(x2,sum-x1)*C(x3,sum-x1-x2)*……*C(xn,xn);
(sum為x1至xn的和)。
**
還是要吐槽下簡書的markdown編輯不支持本地圖片上傳
java實(shí)現(xiàn)如下：
**
<pre><code>
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static BigInteger MOD = new BigInteger("1000000007");
public static BigInteger c(long num,long sum) {
BigInteger s=BigInteger.ONE;
num=num>sum-num?sum-num:num;
for(int i=1;i<=num;i++)
s = s.multiply(new BigInteger(String.valueOf(sum-i+1)));
for(int i=1;i<=num;i++)
s = s.divide(new BigInteger(String.valueOf(i)));
s = s.mod(MOD);
return s;
}
public static long count(long[] arr,long sum) {
BigInteger s=c(arr[0],sum);
for(int i=1,len=arr.length-1;i<=len;i++){
s = s.multiply(c(arr[i],sum-=arr[i-1]));
s = s.mod(MOD);
}
return Long.parseLong(s.toString());
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=0;i < t;i++){
int n = sc.nextInt();
long[] arr = new long[n];
long sum = 0l;
for(int j=0;j < n;j++){
arr[j] = sc.nextLong();
sum+=arr[j];
}
Arrays.sort(arr);
System.out.println(count(arr,sum));
}
}
}
</code></pre>
