この手の累積和高速化が半端じゃなく苦手なことがわかった。 問題へのリンク 問題概要 長さ の数列 が与えられる。 この数列をいくつかの区間に分割する方法のうち、 番目の区間に含まれる数列の要素の総和が で割り切れるようなものの個数を 1000000007 で…

個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …

最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった！ 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…

すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…

ができた。本番中に解き切りたかった 問題へのリンク 問題概要 個の整数 がある。整数 を 1 つ固定したとき、先手と後手は以下のようにしてゲームを進める: 先手は現在残っている整数のうち、最大のものを取って足す 後手は現在残っている整数のうち、 に最…

最近、ABC 201〜300 の D 問題埋めを推奨している身としては、僕も同様のトレーニングとして SRM 401〜650 辺りの DIV1 Hard 埋めを始めてみようと思い立った。 問題へのリンク editorial へのリンク 問題概要 二次元平面上において、以下の条件を満たす線分…