问题描述：
The norm of a vector v = (v1, v2, ... , vn) is define as norm(v) = |v1| + |v2| + ... + |vn|. And in Problem 0000, there are n cases, the standard output is recorded as a vector x = (x1, x2, ... , xn). The output of a submitted solution is also records as a vector y = (y1, y2, ... , yn). The submitted solution will be accepted if and only if norm(x - y) ≤ m (a given tolerance).
Knowing that all the output xi are in range [a, b], an incorrent solution that outputs integer yi in range [a, b] with equal probability may also get accepted. Given the standard output xi, you are supposed to calculate the possibility of getting accepted using such solution.
n, m, a, b (1 ≤ n, m ≤ 50, -50 ≤ a < b ≤ 50)
Accepted 3411Java380MS9938K import java.util. * ; import java.math. * ; public class Main{ public static void main(String[] args){ int n,m,a,b,x[] = new int [ 51 ]; BigInteger d[][] = new BigInteger[ 51 ][ 51 ],f1,f2,f3; Scanner cin = new Scanner(System.in); while (cin.hasNext()) { n = cin.nextInt(); m = cin.nextInt(); a = cin.nextInt(); b = cin.nextInt(); // System.out.println(n+" "+m+" "+a+" "+b); int i,j,k,t; for (i = 1 ;i <= n;i ++ ) x[i] = cin.nextInt(); for (i = 0 ;i <= n;i ++ ) for (j = 0 ;j <= m;j ++ ) d[i][j] = BigInteger.ZERO; for (i = a;i <= b;i ++ ){ t = Math.abs(i - x[ 1 ]); // System.out.println(t); if (t <= m) { d[ 1 ][t] = d[ 1 ][t].add(BigInteger.ONE); // System.out.println("d[1]["+t+"]="+d[1][t]); } } for (i = 2 ;i <= n;i ++ ){ for (j = a;j <= b;j ++ ){ t = Math.abs(j - x[i]); if (t <= m){ for (k = t;k <= m;k ++ ){ d[i][k] = d[i][k].add(d[i - 1 ][k - t]); // System.out.println("d["+i+"]["+k+"]="+d[i][k]); } } } } f1 = BigInteger.ZERO; for (i = 0 ;i <= m;i ++ ) f1 = f1.add(d[n][i]); f2 = BigInteger.ONE; for (i = 1 ;i <= n;i ++ ) f2 = f2.multiply(BigInteger.valueOf(b - a + 1 )); // System.out.println(f1+" "+f2); f3 = f1.gcd(f2); f1 = f1.divide(f3); f2 = f2.divide(f3); System.out.println(f1 + " / " + f2); } }} /* 1 1 0 214 2 2 52 3 2 44 3 2 52 3 2 41/13/327/32 */代码的核心部分是Lines 30-40。简单吧，嘻嘻…
转载于:https://www.cnblogs.com/DreamUp/archive/2010/10/09/1846717.html
