P3182 [HAOI2016]放棋子 题解(错排+java大整数)

题目链接

题目大意

其实稍微转换一下就会发现这是一个错排问题

(dp[i]=(n-1) imes(dp[i-1]+dp[i-2]))

然后套一下java大整数的板子

代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        Integer n=cin.nextInt();
        BigInteger[] dp = new BigInteger[300];
        dp[1]=BigInteger.valueOf(0);
        dp[2]=BigInteger.valueOf(1);
        for(int i=3;i<=n;i++){
            BigInteger x=BigInteger.valueOf(i-1);
            dp[i]=x.multiply((dp[i-1].add(dp[i-2])));
        }
        System.out.println(dp[n]);
    }
}