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

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

高速畳み込み計算

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

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

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution (800 点)

これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…

yukicoder No.886 Direct

添字 GCD 畳み込みの練習に 問題へのリンク 問題概要 の格子点上の二点対であって、その二点を結ぶ線分上に格子点をもたないものが何個あるかを数え上げよ。(1000000007 で割ったあまりで) 制約 解法 1:添字 GCD 畳み込み この問題は、線分として 軸や 軸に…

Educational Codeforces Round 057 G - Lucky Tickets

NTT と聞いて 問題へのリンク 問題概要 偶数 が与えられる。 十進法表記で () しか登場しない 桁の整数のうち、 前半 桁の各位の和 後半 桁の各位の和 が等しいものが何通りあるか、998244353 で割ったあまりで答えよ。leading zero は OK。 制約 考えたこと…

Codeforces 488 DIV1 E - Nikita and Order Statistics

FFT 勉強シリーズその 2 なん。 うーん、、、これ思いつけるもんなんかいな...なのん Codeforces 488 DIV1 E - Nikita and Order Statistics 問題概要 要素の整数数列 と整数 が与えられる。数列 の連続する部分列のうち、「 未満の値となっているものが 個…

yukicoder 0206 数の積集合を求めるクエリ

FFT の勉強シリーズその 1 なん yukicoder 0206 数の積集合を求めるクエリ 問題概要 どの 2 つも互いに相異なるサイズ L の数列 A[0], A[1], ..., A[L-1] と どの 2 つも互いに相異なるサイズ M の数列 B[0], B[1], ..., B[M-1] とが与えられる。 各 A[i], B…