zoj3411-Special Special Judge-高精度dp

Special Special Judge Time Limit: 2 Seconds       Memory Limit: 65536 KB

Because of recent update of ZOJ, some special judges were broken. You're requested to fix the special judge for Problem 0000.

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.

Input

The input contains no more than 100 test cases. The first line of each case contains 4 integers n, m, a, b (1 ≤ n, m ≤ 50, -50 ≤ a < b ≤ 50), as described above. Then follows a line contains n integers, x1, x2, ... , xn (a ≤ xi ≤ b), indicating the standard output of the n cases.

Process to end of input.

Output

For each case, output the possibility as a irreducible fraction of getting accepted using the incorrent solution in a single line.

Sample Input

1 1 0 2
1
      

Sample Output

1/1      

终有一天能达到WATASHI大神的高度吧！加油吧少年！      

诶，满满的都是泪啊。。。      

import java.util.*;
import java.math.*;

public class Main {
	static BigInteger dp[][]=new BigInteger [60][60];//不加static会报错，静态方法不能引用一个非静态的成员变量
	//dp[i][j]代表前面i个数，总的误差为j时accepted的output数
	public static void main(String[] args) {
		int n,m,a,b;
		Scanner scan=new Scanner(System.in);
		while(scan.hasNext())
		{
			n=scan.nextInt();
			m=scan.nextInt();
			a=scan.nextInt();
			b=scan.nextInt();
			dp[0][0]=BigInteger.valueOf(1);
			for(int i=1;i<=m;++i)
				dp[0][i]=BigInteger.valueOf(0);
			for(int i=1;i<=n;++i)
			{
				int temp=scan.nextInt();
				for(int j=0;j<=m;++j)
				{
					BigInteger hehe=BigInteger.ZERO;
					for(int k=a;k<=b;++k)
					{
						if((j-Math.abs(temp-k))>=0)
							hehe=hehe.add(dp[i-1][j-Math.abs(temp-k)]);
					}
					dp[i][j]=hehe;
				}
			}
			BigInteger fenzi=BigInteger.ZERO,fenmu=BigInteger.valueOf(b-a+1);
			for(int i=0;i<=m;++i)
				fenzi=fenzi.add(dp[n][i]);
			fenmu=fenmu.pow(n);
			BigInteger my_gcd=fenzi.gcd(fenmu);
			System.out.println(fenzi.divide(my_gcd)+"/"+fenmu.divide(my_gcd));
		}
	}
}