Project Euler 628

题目

Open chess positions

A position in chess is an (orientated) arrangement of chess pieces placed on a chessboard of given size. In the following, we consider all positions in which \(n\) pawns are placed on a \(n \times n\)
board in such a way, that there is a single pawn in every row and every column.

We call such a position an open position, if a rook, starting at the (empty) lower left corner and using only moves towards the right or upwards, can reach the upper right corner without moving onto any field occupied by a pawn.

Let \(f(n)\) be the number of open positions for a \(n \times n\) chessboard.

For example, \(f(3)=2\), illustrated by the two open positions for a \(3 \times 3\) chessboard below.

You are also given \(f(5)=70\).

Find \(f(10^8)\) modulo \(1\,008\,691\,207\).

解决方案

一个局面不是开放局面，当且仅当从左上到右下存在一堵“墙”（如图所示）：

因此，我们需要统计这种非开放局面的数量，然后用总局面数量\(n!\)减去这些非开放局面数量即可。

如果墙位于左下方，那么长度为\(i\)的墙一共有\((n-i)!\)种方法，位于右上方的墙的情况相同，以及主对角线上的那\(1\)种情况。同时，需要减去左下方，右上方都有墙的情况（长度分别为\(i,j\)）：\(\displaystyle{\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}}(n-i-j)!\)。

因此，最终可以得到：

\(\begin{aligned} f(n)&=n!-\left(2\sum_{i=1}^{n-1}(n-i)!+1-\sum_{i=1}^{n-1}\sum_{j=1}^{n-i} (n-i-j)!\right)\\ &=n!-\left(2\sum_{i=1}^{n-1}i!+1-\sum_{i=0}^{n-2}(n-i-1)\cdot i!\right)\\ &=n!-\left(2\cdot(n-1)!+2\sum_{i=0}^{n-2}i!-1-\sum_{i=0}^{n-2}(n-i-1)\cdot i!\right)\\ &=n!-\left(2\cdot(n-1)!-1-\sum_{i=0}^{n-2}(n-i-3)\cdot i!\right)\\ &=(n-2)\cdot(n-1)!+1+\sum_{i=0}^{n-2}(n-i-3)\cdot i!\\ &=n!+1+\sum_{i=0}^{n-1}(n-i-3)\cdot i!\\ \end{aligned}\)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e8;
ll mod=1008691207;
int main(){
    ll fac=1,ans=0;
    for(int i=0;i<=N-1;i++){
        ans=(ans+fac*(N-i-3))%mod;
        fac=fac*(i+1)%mod;
    }
    ans=(ans+fac+1)%mod;
    printf("%lld\n",ans);
}