ABC 401-500/ABC423F - Loud Cicada - 競技プログラミング用 知識集積所

---

問題

ABC423F

必要知識

B以下レベルの内容は省略

• 二項係数※
• 包除原理※

考え方

包除原理※の応用で、条件のうちちょうどm個を満たすパターン数は以下を計算すればよい。

Comb[m,m]*（条件からm個選んで、それを満たすパターン数を出す……のComb[n,m]パターンの合計）
- Comb[m+1,m]*（条件からm+1個選んで、それを満たすパターン数を出す……のComb[n,m+1]パターンの合計）
+ Comb[m+2,m]*（条件からm+2個選んで、それを満たすパターン数を出す……のComb[n,m+2]パターンの合計）
-……
+ (-1)^(n-m)*Comb[n,m]*（条件からn個選んで、それを満たすパターン数を出す……のComb[n,n]パターンの合計）

これは、bit全探索※の要領で、

• セミを何種類か選んで、それらが全部が大量発生する回数を求める
• それを以下の要領で全部足す
  • 発生するセミの種類数がm未満なら無視
  • m以上で、mと偶奇が一致するならComb[種類数,m]倍したものを足す
  • m以上で、mと偶奇が異なるならComb[種類数,m]倍したものを引く

これを2^nパターン全部やればよい。

セミ何種類かが全部が大量発生する回数は、yを周期の最小公倍数で割ればよい。
しかし、最小公倍数が大きくなりすぎてlong long型すらはみ出るのが問題。
そこで、ある程度より大きくなるときにはINFを返すような独自関数を実装することでうまく回避する。

二項係数※の計算は、nが高々20なので、

n /1 *(n-1) /2 *(n-2) /3 *…… *(n-r+1) /r

と上下交互に愚直にやる方法で時間的にも大きさ的にも問題ない。

解答例

解答例

注意点

別解