【今日の精進】ARC102E - Stop. Otherwise...

毎日格上の問題を倒すやつの9日目です。

問題リンク

atcoder.jp

問題概要

区別できない 面ダイスが 個あるよ。

「どの異なる2つのダイスの目の和も にならない場合の数を で割った余り」の答えをありえるすべての に対して求めてね。

解法

包除原理で解きます。

が奇数の場合の方がわかりやすいので、まずはそれを考えます。簡単に偶数の場合にも拡張できます。

まず、共存させてはいけない数の組がいくつあるかを容易に求めることが可能です。

この後、 とすることで目的の数を求められます。

これらは全て、二項係数の組み合わせで求めることができます。¹

偶数の場合は、 みたいにすればいけます。これも奇数よりは複雑ですが難しくはありません。²

提出コード

MOD=998244353
comb=[[0 for i in range(10000)] for i in range(10000)]
comb[0][0]=1
for i in range(1,5000):
    for j in range(i+2):
        comb[i][j]=comb[i-1][j]+comb[i-1][j-1]
        comb[i][j]%=MOD
K,N=map(int,input().split())
finans=[-1]*(2*K-1)
for i in range(2,2*K+1):
    if finans[i-2]!=-1:
        break
    if i%2==1:
        ans=0
        sign=1
        for j in range(i//2+1):
            ans+=sign*comb[N-j*2+K-1][N-j*2]*comb[i//2][j]
            sign=-sign
            ans%=MOD
        finans[i-2]=ans
        finans[-i+1]=ans
    else:
        ans=0
        sign=1
        for j in range(i//2):
            ans+=sign*comb[N-j*2+K-2][N-j*2]*comb[i//2-1][j]
            ans+=sign*comb[N-j*2+K-3][N-j*2-1]*comb[i//2-1][j]
            sign=-sign
            ans%=MOD
        finans[i-2]=ans
        finans[-i+1]=ans
print(*finans,sep="\n")

Submission #46021166 - AtCoder Regular Contest 102

感想

問題名の由来がわからなすぎる…

---

1. 「写像12相」を総整理！ 〜 数え上げ問題の学びの宝庫 〜 - Qiitaの「玉区別しない・箱区別する・制限なし」参照↩
2. 「難しくないかどうかは人によりますよね？」という意見は受けつけません。↩