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

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

写像12相

AtCoder ABC 140 A - Password (灰色, 100 点)

「場合の数」の問題! 問題へのリンク 問題概要 3 桁の整数のうち、各桁の値が 1 以上 以下の整数であるものの個数を求めよ。 制約 解法 各桁ごとに 通りの選択肢があるので、3 桁の整数は 通り 考えられます。 これは重複順列などと呼ばれている考え方です…

Yosupo Library Checker - Partition Function

ここでは の計算量の解法を実装した。本当は FPS を使えば の計算量でできる。 問題へのリンク 問題概要 非負整数値 が与えられる。 の分割数を 998244353 で割った余りを求めよ。 制約 考えたこと ここでは、この記事に書いた の計算量の解法を実装した。 q…

yukicoder No.269 見栄っ張りの募金活動

分割数で鮮やかに解ける! 問題へのリンク 問題概要 人のクラスで総額 円を集めることにした。 このクラスの生徒は皆見栄っ張りであり、出席番号順が1つ前の生徒に比べて 円以上高い金額を寄付しないと気が済まない。 この条件を満たす方法の個数を 1000000…

第4回 ドワンゴからの挑戦状 予選 2018 C - Kill/Death (500 点)

分割数のいい感じの問題! 問題へのリンク 問題概要 長さ の数列 killA, killB が与えられる。この 2 つの広義単調減少である。 次の条件を満たす長さ の数列 deathA, deathB の組の個数を 1000000007 で割ったあまりを求めよ。 killA の総和 = deathB の総…

AtCoder ARC 104 E - Random LIS (赤色, 700 点)

ゲーは確かに面白いかもしれない。 問題へのリンク 問題概要 長さ の整数列 が与えらる。 同じく長さ の整数列 は、 各 について独立に、 を満たす整数の一様分布からランダムに選ばれる。 このとき、 の最長増加部分列の長さの期待値を mod 1000000007 で計…

Codeforces 315 DIV1 B. Symmetric and Transitive (R2100)

ベル数の練習に 問題へのリンク 問題概要 (超意訳) 個の区別できる要素から何個か選んで残りを捨てて ( 個以上捨てなければならない)、選んだ要素を何個かのグループに分ける方法が何通りあるか求めよ。 制約 考えたこと 個選ぶとすると選び方は 通りあり、…

yukicoder No.391 CODING WAR

写像12相の 玉は区別する 箱も区別する 各箱の玉は 1 個以上 という場合の問題!!! 問題へのリンク 問題概要 個の互いに区別できる玉を、 個の互いに区別できる箱に入れる。 ただし、どの箱についても玉が 1 個以上入るようにするな方法が何通りあるか、10…

スターリング数と、問題まとめ

この間分割数の記事についての記事を書いたときに続けてスターリング数も次回書くつもりですっかり忘れていたので書こうと思い立ちました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含…

分割数と、問題まとめ

こないだのドワンゴからの挑戦状で、分割数を用いる問題が出題されたので、周辺の話題を整理してみました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。今回は分割数を、…