けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

NTT

yukicoder No.980 Fibonacci Convolution Hard (母関数)

すごい面白かった!!! 問題へのリンク 問題概要 整数 が与えらえたときに、漸化式 を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ: 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、10000…

AtCoder AGC 005 D - ~K Perm Counting (900 点)

包除原理勉強会の一環なん。なんか最初、0〜N-1 を 2K で割った余りで類別したところで鎖を作って、そこでのサイズ i のマッチングの個数を数えたりしたのだけど、それをマージするのに NTT を使うとか血迷ったん^^; https://beta.atcoder.jp/contests/agc00…