377.1

書き忘れ。

250

頂点が格子点に乗る正方形が与えられた領域の中にいくつ存在するかという問題。

1x1の中に入る正方形は1個、2x2の中に入る正方形は2個、...という風になるので、途中経過がオーバーフローしないように注意しながらループを回せばおしまい。

500

盤面上に白と黒の面があり、白と黒の間だけ接続がある。白の値を保存して、黒の値を接続された白の値の合計に更新するという操作と、その逆の操作を交互にN回やった後、盤面上に記入されている値を答えよという問題。

値が発散するので、指定された値のmodを返す。前回の500と同様に行列積をバイナリに実行するだけ。途中でオーバーフローにだけ注意することが重要。

1000

P個の文字を使ってできる高々長さNの文字列とQ個の文字を使ってできる高々長さNの文字列をくっつけて、長さ1以上の文字列を作る。各文字列には高々1個のアクセントを付けることができる。このとき作れる文字列の数を答えよという問題。

これまた発散するので指定された数のmodで答える。左側は1+2P+3P^2+...+(N+1)P^N個あり、これをQに置き換えれば右側。長さ0のものはカウントしないので、全体から最後に1引くことを忘れないようにする。

最終的に式変形をすると、(a/b)%cという形になるので、これを計算できるかどうかというだけの問題。(a/b)%c=(a%(b*c))/bとなることを知っていますか、という問題だった。検索したらかなり面倒そうで、かつ汎用でない式が出てきてどうしたものかと思ったけれど、実際には大分簡単...。