2010-1088

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

Contest 5 by Bomb - A  
Special Special Judge
    题目给出了一个有n个元素的序列向量{An}作为标准，然后Fire 对每个元素在[a,b]范围内乱猜，问他瞎猜完之后每个元素之间的差的绝对值之和小于等于m的概率的精确值是多少，用分数表示。
    如果不考虑数据范围，用f[i][j]表示猜到第i个元素，这i个元素分别与精确值的差的绝对值之和为j时,一共存在的情况数。那么有递退式：f[i][j]=sum{f[i][j-(s-Ai)]}(max(a,A［i］-j)<=s<=min(b,A[i]+j)).那么最后的结果就是sum{f[n][i]/(b-a+1)}(0<=i<=m)，通分即可
    但是现在要考虑高精度运算，可以采用JAVA中的BigInteger类帮助运算，免去了自己去写高精度。

JAVA程序：
{{{
#!java
import java.util.*;
import java.math.*;
public class Main
{
    static int data[]=new int[100];
    static BigInteger f[][]=new BigInteger [100][100];
    static int abs(int s)
    {
        if (s<0)
            return -s;
        return s;
    }
    static BigInteger gcd(BigInteger a,BigInteger b)
    {
        if (a.equals(BigInteger.valueOf(0)))
            return b;
        return gcd(b.mod(a),a);
    }
    public static void main(String args[])
    {
        int n,m,a,b;
        Scanner sin=new Scanner(System.in);
        while (sin.hasNextInt())
        {
            n=sin.nextInt();
            m=sin.nextInt();
            a=sin.nextInt();
            b=sin.nextInt();
            for (int i=1;i<=n;i++)
            {
                data[i]=sin.nextInt();
            }
            for (int i=0;i<=n;i++)
                for (int j=0;j<=m;j++)
                    f[i][j]=BigInteger.valueOf(0);
            f[0][0]=BigInteger.valueOf(1);
            for (int i=1;i<=n;i++)
                for (int j=0;j<=m;j++)
                {
                    int min=data[i]-j;
                    int max=data[i]+j;
                    if (min<a)
                        min=a;
                    if (max>b)
                        max=b;
                    for (int s=min;s<=max;s++)
                    {
                        int diff=abs(s-data[i]);
                        f[i][j]=f[i][j].add(f[i-1][j-diff]);
                    }
                }
            BigInteger sum=BigInteger.valueOf(0);
            for (int i=0;i<=m;i++)
                sum=sum.add(f[n][i]);
            BigInteger d=BigInteger.valueOf(1);
            for (int i=1;i<=n;i++)
                d=d.multiply(BigInteger.valueOf(b-a+1));
            BigInteger p=gcd(sum,d);
            BigInteger aa=sum.divide(p);
            BigInteger bb=d.divide(p);
            System.out.println(aa+"/"+bb);
        }
    }
}
}}}

Contest 5 by Bomb - A

Special Special Judge

题目给出了一个有n个元素的序列向量{An}作为标准，然后Fire 对每个元素在[a,b]范围内乱猜，问他瞎猜完之后每个元素之间的差的绝对值之和小于等于m的概率的精确值是多少，用分数表示。

如果不考虑数据范围，用f[i][j]表示猜到第i个元素，这i个元素分别与精确值的差的绝对值之和为j时,一共存在的情况数。那么有递退式：f[i][j]=sum{f[i][j-(s-Ai)]}(max(a,A［i］-j)<=s<=min(b,A[i]+j)).那么最后的结果就是sum{f[n][i]/(b-a+1)}(0<=i<=m)，通分即可

但是现在要考虑高精度运算，可以采用JAVA中的BigInteger类帮助运算，免去了自己去写高精度。

JAVA程序：

import java.util.*;
import java.math.*;
public class Main
{
    static int data[]=new int[100];
    static BigInteger f[][]=new BigInteger [100][100];
    static int abs(int s)
    {
        if (s<0)
            return -s;
        return s;
    }
    static BigInteger gcd(BigInteger a,BigInteger b)
    {
        if (a.equals(BigInteger.valueOf(0)))
            return b;
        return gcd(b.mod(a),a);
    }
    public static void main(String args[])
    {
        int n,m,a,b;
        Scanner sin=new Scanner(System.in);
        while (sin.hasNextInt())
        {
            n=sin.nextInt();
            m=sin.nextInt();
            a=sin.nextInt();
            b=sin.nextInt();
            for (int i=1;i<=n;i++)
            {
                data[i]=sin.nextInt();
            }
            for (int i=0;i<=n;i++)
                for (int j=0;j<=m;j++)
                    f[i][j]=BigInteger.valueOf(0);
            f[0][0]=BigInteger.valueOf(1);
            for (int i=1;i<=n;i++)
                for (int j=0;j<=m;j++)
                {
                    int min=data[i]-j;
                    int max=data[i]+j;
                    if (min<a)
                        min=a;
                    if (max>b)
                        max=b;
                    for (int s=min;s<=max;s++)
                    {
                        int diff=abs(s-data[i]);
                        f[i][j]=f[i][j].add(f[i-1][j-diff]);
                    }
                }
            BigInteger sum=BigInteger.valueOf(0);
            for (int i=0;i<=m;i++)
                sum=sum.add(f[n][i]);
            BigInteger d=BigInteger.valueOf(1);
            for (int i=1;i<=n;i++)
                d=d.multiply(BigInteger.valueOf(b-a+1));
            BigInteger p=gcd(sum,d);
            BigInteger aa=sum.divide(p);
            BigInteger bb=d.divide(p);
            System.out.println(aa+"/"+bb);
        }
    }
}