2013-team5/andrew/30/B

从 Trac 迁移的文章

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

原文章内容如下：

{{{
import java.util.*;
import java.math.*;
import java.io.*;

public class Main {
    static public void main(String args[]) throws Exception{
        Scanner sc = new Scanner(new File("derangements.in"));
        PrintWriter pw = new PrintWriter(new File("derangements.out"));
        int n = sc.nextInt();
        BigInteger Comb[][] = new BigInteger[210][210];
        for (int i = 0; i <= n; i++){
            Comb[i][0] = Comb[i][i] = BigInteger.valueOf(1);
            for (int j = 1; j < i; j++){
                Comb[i][j] = Comb[i - 1][j].add(Comb[i - 1][j - 1]);
            }
        }
        BigInteger D[] = new BigInteger[210];
        D[0] = BigInteger.valueOf(0);
        D[1] = BigInteger.valueOf(0);
        D[2] = BigInteger.valueOf(1);
        for (int i = 3; i <= n; i++){
            D[i] = BigInteger.valueOf(i - 1).multiply(D[i - 1].add(D[i - 2]));
        }

        BigInteger F[] = new BigInteger[210];
        F[0] = BigInteger.valueOf(1);
        for (int i = 1; i <= n; i++) F[i] = F[i - 1].multiply(BigInteger.valueOf(2));

        BigInteger ans = BigInteger.valueOf(1);
        for (int i = 0; i <= n; i++){
            ans = ans.add(Comb[n][i].multiply(D[n - i]).multiply(F[n - i]));
        }
        pw.println(ans);
        sc.close();
        pw.close();
    }
}
}}}

import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
    static public void main(String args[]) throws Exception{
        Scanner sc = new Scanner(new File("derangements.in"));
        PrintWriter pw = new PrintWriter(new File("derangements.out"));
        int n = sc.nextInt();
        BigInteger Comb[][] = new BigInteger[210][210];
        for (int i = 0; i <= n; i++){
            Comb[i][0] = Comb[i][i] = BigInteger.valueOf(1);
            for (int j = 1; j < i; j++){
                Comb[i][j] = Comb[i - 1][j].add(Comb[i - 1][j - 1]);
            }
        }
        BigInteger D[] = new BigInteger[210];
        D[0] = BigInteger.valueOf(0);
        D[1] = BigInteger.valueOf(0);
        D[2] = BigInteger.valueOf(1);
        for (int i = 3; i <= n; i++){
            D[i] = BigInteger.valueOf(i - 1).multiply(D[i - 1].add(D[i - 2]));
        }
        BigInteger F[] = new BigInteger[210];
        F[0] = BigInteger.valueOf(1);
        for (int i = 1; i <= n; i++) F[i] = F[i - 1].multiply(BigInteger.valueOf(2));
        BigInteger ans = BigInteger.valueOf(1);
        for (int i = 0; i <= n; i++){
            ans = ans.add(Comb[n][i].multiply(D[n - i]).multiply(F[n - i]));
        }
        pw.println(ans);
        sc.close();
        pw.close();
    }
}