POJ - 1737 Connected Graph，Java（计数类DP）

POJ - 1737 Connected Graph

C++高精太难写了，直接用Java的大整数会方便一点

常规方法

import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;public class Main {
    static Scanner cin = new Scanner(System.in);static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));public static BigInteger ksm(int k){
    BigInteger res=BigInteger.ONE;for(int i=1;i<=k*(k-1)/2;i++) res=res.multiply(BigInteger.valueOf(2));return res;}public static BigInteger C(int a,int b){
    BigInteger res=BigInteger.ONE;for(int i=1;i<=a;i++) res=res.multiply(BigInteger.valueOf(i));for(int i=1;i<=b;i++) res=res.divide(BigInteger.valueOf(i));for(int i=1;i<=a-b;i++) res=res.divide(BigInteger.valueOf(i));return res;}public static void main(String[] args) throws IOException{
    while(cin.hasNext()){
    int n=cin.nextInt();if(n==0) break;BigInteger []f = new BigInteger[n+1];f[1]=BigInteger.ONE;for(int i=1;i<=n;i++){
    f[i]=ksm(i);for(int j=1;j<i;j++)f[i]=f[i].subtract(f[j].multiply(C(i-1,i-j).multiply(ksm(i-j))));}bw.write(f[n].toString()+"\n");}bw.flush();}
}

预处理50种情况

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    static Scanner cin = new Scanner(System.in);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static BigInteger ksm(int k){
    BigInteger res=BigInteger.ONE;for(int i=1;i<=k*(k-1)/2;i++) res=res.multiply(BigInteger.valueOf(2));return res;}public static BigInteger C(int a,int b){
    BigInteger res=BigInteger.ONE;for(int i=1;i<=a;i++) res=res.multiply(BigInteger.valueOf(i));for(int i=1;i<=b;i++) res=res.divide(BigInteger.valueOf(i));for(int i=1;i<=a-b;i++) res=res.divide(BigInteger.valueOf(i));return res;}public static void main(String[] args) {
    BigInteger [][]f = new BigInteger[51][51];for(int k=1;k<=50;k++){
    f[k][1]=BigInteger.ONE;for(int i=1;i<=k;i++){
    f[k][i]=ksm(i);for(int j=1;j<i;j++)f[k][i]=f[k][i].subtract(f[k][j].multiply(C(i-1,i-j).multiply(ksm(i-j))));}}while(cin.hasNext()){
    int n=cin.nextInt();if(n==0) break;out.println(f[n][n]);}out.flush();}
}