練習記です。解説AC上等で700点問題をやっていく週間。

E - Stop. Otherwise...

問題概要：互いに区別されないK面サイコロをN個振ったとき、「どの2つのサイコロの出目の和も t でない」場合の数を 2≤t≤2K の範囲ですべて求めよ。(素数 998244353 で割った余りで答える。)

解説：t は全列挙すればいいので、定数として扱います。

基本事項ですが「互いに区別されない」の部分を確認しておきます。サイコロが区別されないので、「出目の組み合わせ」には順番がなく、出目のリストをソートした数列と同一視できます。

N=7 K=9
区別される出目列 a=3 b=1 c=4 d=1 e=5 f=9 g=2
区別のない出目列   3   1   4   1   5   9   2

出目の和に関する条件がなければ、場合の数は「K個のものをN個選ぶ重複あり組み合わせ」であり、H(K, N) = C(K-1+N, N) です。(H(0,0)=1 に注意。)

サイコロの出目の和が t になったということは、ある数 s について出目が s のサイコロと (t-s) のサイコロがあったということです。この s, t-s のペアは全列挙できます。(1,6) と (6,1) のようなペアを同一視するために s < t-s に限って数えたペアの個数を p と置きます。(p をどうやって求めるのか？ 全列挙です。)

例えば N=4, K=6, t=9 では 9 = 3+6 = 4+5 なのでペアは p=2 通り。9 = 1+8 = 2+7 に関しては、7, 8 が出目としてありえないのでペアではないとします。

これらのペア (s, t-s) について、出目列に出目 s と出目 t-s の両方が含まれていたら、それらの出目の和が t になってしまってダメです。

1. 出目列にペアのどちらも含まれていない ←OK
2. 出目列にペアの片方が含まれているが、他方は含まれていない ←OK
3. 出目列にペアの両方が含まれている ←ダメ

そこで、出目列を3通りに分割します。出目列 x に対して「各ペア (a, b) について x に a か b が出現するなら +1、しないなら +0 」というスコアを q(x) とおきます。 q の値が等しい出目列をグループ化して、各グループに含まれる出目列のうち、条件を満たすものの個数を数えていく、という方針です。(こうすると q の値を定数とみなして式を立てられる、テクい。)

1. p 個あるペアのうち、どの q 個が出現するのか、という場合があって、C(p, q) 通り。
2. そのそれぞれについて、出目のうち q 個は、それらのペアの「片方」の値です。そのどちらかが出たかについて2通りの場合があって、2^q 通り。
3. そのそれぞれについて、残りの N-q 個の出目の場合の数を計算します。そのため、出目を4通りに分類します。

3-1. q 個のペアに含まれる数値。出たほうの値は何度出てもかまいません。一方、「もう片方」が出ると条件に違反しますので、そっちはなしです。
3-2. q 個のペアとは別のペアに含まれる数値。これらが出ないという仮定で計算しているので、出ません。
3-3. ペアに含まれない数値。s に対して t-s が出目としてありえる値(1〜K)でなければペアになりません。これは何個出てもかまいません。
3-4. t/2。これは t が偶数のときだけ生じるエッジケースです。出目 t/2 は1個まで出てもよく、2つ出てはいけません。これを後回しにするため、いったん t は奇数と仮定します。

まとめると、残りの N-q 個の出目は「q 個のペアに含まれる、出たほうの数」と「ペアにならない数」 (K-2p個) で埋まっていることが分かりました。これらの場合の数は H(q + K-2p, N-q) 通りです。

t が偶数の場合は、t/2 が出るか出ないかで場合分けして考えます。

1. t/2 が出る場合、N-q 個のうち1個が t/2 なので、残りの選びかたは H(q + K-2p - 1, N-q - 1) です。
2. t/2 が出ない場合、奇数と同様ですが「ペアにならない数値」の選択肢が1個少なくて、 H(q + K-2p - 1, N-q) です。

これを頑張って書けば実装できます。有限体上の組み合わせの計算については略。

提出：

謝辞

解説PDFに加えて、kmjp さんの解説を大いに参考にしました。ただし、本稿に誤りがあったら私の責任です。