yukicoder : No.1138 No Bingo!

これ真正面から取り掛かって解けるのかな。
https://yukicoder.me/problems/no/1138

問題

整数Nが与えられる。
N*Nのビンゴカードのうち、(N-1)*N個のマスに穴が開いており、かつまだビンゴが成立していないのは何通りか。

解法

縦と横にそれぞれ穴が1個ずつあるという条件を考える。
1～NのPermutation Pに対し、(i,P[i])に1個ずつ穴が開いている、と置くとこの縦横の条件を満たせる。
あとは斜めの条件を達成するために、

• P[i]=iとなるiがない
• P[i]=N+1-iとなるiがない

を考える必要がある。

そこで、包除原理の要領で、それぞれの条件を満たす組み合わせを求めよう。
片方の条件を満たすには、Pが完全順列であればよくO(N)で求められる。
両者を共に満たす条件は、OEISにO(N)の簡単な漸化式が掲載されているのでこれを使おう。
A003471 - OEIS

ll N;
const ll mo=998244353;

ll S[5];
ll A[202020];
ll B[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	S[1]=1;
	for(i=1;i<=N;i++) S[1]=S[1]*i%mo;
	A[0]=B[0]=1;
	for(i=2;i<=N;i++) {
		A[i]=(i-1)*(A[i-1]+A[i-2])%mo;
		if(i>=4) {
			if(i%2==0) B[i]=((i-1)*B[i-1]+2*(i-2)*B[i-4])%mo;
			else B[i]=((i-1)*B[i-1]+2*(i-1)*B[i-2])%mo;
		}
	}
	S[2]=S[3]=A[N];
	S[4]=B[N];
	
	ll ret=S[1]-S[2]-S[3]+S[4]+mo+mo;
	cout<<ret%mo<<endl;
	
	
	
}

まとめ

地道に考えれば最後の漸化式もわかるのかな。