【Codeforces】Gym 101156G Non-Attacking Queens 打表

题意

求$n\times n$的棋盘上放$3$个皇后使得互相不攻击的方案数

---

拓展是$m\times n$棋盘上放$k$皇后，暴力打表找到了公式

OEIS

代码

import java.math.BigInteger;

import java.util.Scanner;

/**

 * Created by cyuun on 2018/1/24.

 */

public class Main {

    public static void main(String[] args) {

        BigInteger n,ans;

        Scanner cin = new Scanner(System.in);

        n=cin.nextBigInteger();

        if(n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(1))==0) {

            //(n - 1)(n - 3)(2n^4 - 12n^3 + 25n^2 - 14n + 1)/12

            ans=n.subtract(BigInteger.valueOf(1));

            ans=ans.multiply(n.subtract(BigInteger.valueOf(3)));

            BigInteger part1=n.multiply(n).multiply(n).multiply(n).multiply(BigInteger.valueOf(2));

            BigInteger part2=n.multiply(n).multiply(n).multiply(BigInteger.valueOf(12));

            BigInteger part3=n.multiply(n).multiply(BigInteger.valueOf(25));

            BigInteger part4=n.multiply(BigInteger.valueOf(14));

            ans=ans.multiply(part1.subtract(part2).add(part3).subtract(part4).add(BigInteger.valueOf(1)));

            ans=ans.divide(BigInteger.valueOf(12));

        }else {

            //n(n - 2)^2(2n^3 - 12n^2 + 23n - 10)/12

            ans=n;

            ans=ans.multiply(n.subtract(BigInteger.valueOf(2))).multiply(n.subtract(BigInteger.valueOf(2)));

            BigInteger part1=n.multiply(n).multiply(n).multiply(BigInteger.valueOf(2));

            BigInteger part2=n.multiply(n).multiply(BigInteger.valueOf(12));

            BigInteger part3=n.multiply(BigInteger.valueOf(23));

            ans=ans.multiply(part1.subtract(part2).add(part3).subtract(BigInteger.valueOf(10)));

            ans=ans.divide(BigInteger.valueOf(12));

        }

        System.out.println(ans);

    }

}