AtCoder確率,形式的べき級数・多項式,二項係数,数え上げ

問題へのリンク

問題概要

座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。
1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\ ...

数学動的計画法,数え上げ,重複組合せ,写像12相,スターリング数,第2種スターリング数,ベル数,二項係数

条件を満たすものが何通りあるか数える問題、すなわち数え上げ問題には様々なものがありますが、「\(n\) 個の玉を \(x\) 個の箱に分ける方法は何通りか」などといった、典型的なものはある程度パターン化して解くことができます。 ...

2020年10月23日数学数え上げ,写像12相,スターリング数,第2種スターリング数,ベル数

ベル数は「写像12相」と呼ばれるものを通して学ぶと、他の数え上げ問題との関わりが分かり全体像がスッキリします。ぜひ確認してみることをおすすめします。
「写像12相」で典型的な数え上げ問題のパターン総整理

ベル数とは

...

2020年10月22日数学スターリング数,第2種スターリング数,数え上げ,写像12相

第2種スターリング数は「写像12相」と呼ばれるものを通して学ぶと、他の数え上げ問題との関わりが分かり全体像がスッキリします。ぜひ確認してみることをおすすめします。
「写像12相」で典型的な数え上げ問題のパターン総整理

第 ...

2020年3月31日AtCoder剰余,動的計画法,数え上げ,逆元,木DP,部分木,階乗

問題へのリンク

問題概要

木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。

制約\(2 \leq N \leq 1000 \)
考え方前提: ...

2020年3月10日AtCoder合計得点が何通りか,数え上げ,DP,競プロ,ナップサック

問題へのリンク

問題概要

N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。合計得点は何通り考えられるか?

制約1 ≤ N ≤ 100
1 ≤ p ...

2020年3月8日AtCoder数え上げ,500点,競プロ,区間,素数,Pで割り切れる,剰余

問題概要

長さ N の数 S が与えられる。
素数 P で割り切れるような区間の選び方は何通りあるか?

制約\(1 \leq N \leq 2 \times 10^5\)
\(2 \leq P \leq 10000\ ...

2020年2月24日AtCoder剰余,二項係数,操作,数え上げ,500点,重複組合せ

問題概要

n 個の部屋に 1 ずつ人がいる。以下を k 回行ったとき、考えられる状態は何通りあるか \(10^9+7\) で割った余りで答えよ。

ある部屋 \(i\) にいた人が、\(i \neq j\) を満たす任意の部屋 \( ...

2020年2月10日AtCoder場合分け,動的計画法,数え上げ,DP,500点,桁DP

問題へのリンク

問題概要

1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。

制約

\begin{align}
&1 \leq N \leq 10^{100} \\ ...

2020年1月19日AtCoder数え上げ,桁の数が等しい,400点

問題へのリンク

問題

N以下の整数の組(A, B)について、Aの先頭とBの末尾の数が等しく、Aの末尾とBの先頭の数が等しいのは何通りあるか?

制約

$$1\leq N \leq 2 \times 10^5$$