Sgu/221

同sgu220是一樣的題目,不同的是n由10變成了50.這導致最終的答案結果會超出int64(long long),想偷懶的人可以選擇使用java.math.BigInteger來做這道題.

source code:

import java.io.*;
import java.util.*;
import java.math.*;
public class Solution{
  public static void main(String args[])throws IOException{
    Scanner input=new Scanner(System.in);
    PrintWriter output=new PrintWriter(System.out);
    int n=input.nextInt(),bishop=input.nextInt();
    BigInteger[][] f1=new BigInteger[n+1][bishop+1];
    BigInteger[][] f2=new BigInteger[n][bishop+1];
    BigInteger ans=BigInteger.ZERO;
    int l1[]=new int[n+1],l2[]=new int[n];
    for(int i=1,j=n;i<=j;++i,--j)
      l1[i]=l1[j]=i+i-1;
    Arrays.sort(l1);
    for(int i=1,j=n-1;i<=j;++i,--j)
      l2[i]=l2[j]=i+i;
    Arrays.sort(l2);
    for(int i=0;i<=n;i++){
      f1[i][0]=BigInteger.ONE;
      for(int j=1;j<=bishop;j++)
        f1[i][j]=BigInteger.ZERO;
    }
    for(int i=0;i<n;i++){
      f2[i][0]=BigInteger.ONE;
      for(int j=1;j<=bishop;j++)
        f2[i][j]=BigInteger.ZERO;
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=bishop;j++){
        f1[i][j]=new BigInteger(f1[i-1][j].toString());
        if(l1[i]+1>=j)
          f1[i][j]=f1[i][j].add(f1[i-1][j-1].multiply(BigInteger.valueOf(l1[i]-j+1)));
      }
    for(int i=1;i<n;i++)
      for(int j=1;j<=bishop;j++){
        f2[i][j]=new BigInteger(f2[i-1][j].toString());
        if(l2[i]+1>=j)
          f2[i][j]=f2[i][j].add(f2[i-1][j-1].multiply(BigInteger.valueOf(l2[i]-j+1)));
      }
    for(int i=0;i<=bishop;i++)
      ans=ans.add(f1[n][i].multiply(f2[n-1][bishop-i]));
    output.println(ans.toString());
    input.close();
    output.close();
  }
}