通项公式: a[n]=sum(k=1 to n)(k!*dp[n][k])
java高精度暴力预处理
/*
USER_ID: test#ggvalid
PROBLEM: 409
SUBMISSION_TIME: 2014-07-14 18:31:44
*/
import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);BigInteger f[] = new BigInteger[101];BigInteger dp[][] = new BigInteger[101][101];BigInteger ans[] = new BigInteger[101];for(int i=0; i<101; i++) for(int j=0; j<101; j++) dp[i][j]=BigInteger.ZERO;for(int i=0; i<101; i++) ans[i]=BigInteger.ZERO;f[1]=BigInteger.ONE;f[2]=BigInteger.valueOf(2);f[3]=BigInteger.valueOf(6);dp[1][1]=BigInteger.ONE; dp[2][1]=BigInteger.ONE; dp[2][2]=BigInteger.ONE; dp[3][1]=BigInteger.ONE;dp[3][2]=BigInteger.valueOf(3); dp[3][3]=BigInteger.ONE;for(int i=4;i<101;i++){dp[i][1]=dp[i][i]=BigInteger.ONE;f[i]=f[i-1].multiply(BigInteger.valueOf(i));}for(int i=4; i<101; i++){for(int j=2; j<101; j++){dp[i][j]=dp[i-1][j].multiply(BigInteger.valueOf(j)).add(dp[i-1][j-1]);}}for(int i=1; i<101; i++){for(int j=1; j<=i; j++){ans[i]=ans[i].add(dp[i][j].multiply(f[j]));}}while(cin.hasNext()){int n=cin.nextInt();System.out.println(ans[n]);}cin.close();}}