解法
である全てのペア
について、【
と
について対称な式】の値を合計せよ。
という問題設定はよく登場します。このような問題では、 という条件を外して
かつ
である全てのペア
について、【
と
について対称な式】の値を合計せよ。
と考えると見通しが良くなることが非常に多いです。この値を求めてから、 の場合を引き、対称性を利用して
で割ると元々の答えが求められることになります。
ということで、 を
かつ
である全てのペア
について合計することを考えます。
ここで が
と二項係数を用いて分解できることに注目します。これを全てのペア について合計したものが、今求めたい値です。
ここで和を取る順番を逆にします。ある を1つ固定し、全てのペア
について、
それぞれの次数が
となる項だけを取り出してみましょう。そうするとそれらの合計は、次の形に因数分解できます。
実際にこの式を展開すると、全てのペア に対する
が全て足された形になっていることが確認できます。
この値を について合計すれば良いので、今求めたい値は
となります。これは の
乗和を全て前計算しておくことで、
で求めることができます。
ここから の場合を引き、対称性を利用して
で割ると答えになります。
の場合の総和も、
の
乗和を用いて
と計算できます。
計算量は前計算パートが 、全ての
に対して答えを求めるパートが
となります。