377.1

行列乗算セット。ライブラリを書くことになった件...。

250

二次元盤面上の指定された矩形領域内の格子点を頂点とする正方形は何通りあるか答えよ、という問題。

軸平行なものと、傾いているものを別々にカウントするだけ。いずれもできるだけ左下に固定して、どこまで右上に移動できるかを計算してやる。

500

黒い点と白い点がそれぞれいくつかずつある。色の違う点の間には隣接関係があることがあり、以下の操作を交互に行う。黒い点の持っている点数を、隣接しているすべての白い点の持っている点数の合計値にする。白黒判定して同様の処理を行う。このとき、指定された回数だけ操作した結果の各点の点数を答えよ、という問題。

二つの操作をまとめた操作を行列にして、べき乗してやる。奇数回の場合は最初の操作をそこから更に行う。最後に点数を計算するべく、初期値ベクトルを乗じる。

950

K種類の文字をN文字並べた文字は何通りあるか答えよ、という問題。ただし、一度だけ任意の文字にアクセントを置くことができ、アクセントが違うものは別と思うことにする。

状態はアクセントの有無で、アクセントは一回しか使えないので、使ってない状態から使った状態になるか、変化しないかのいずれか。行列乗算に今までの合計値を足し込むための列を追加してやる必要がある。後はやるだけ。