スーパー包除原理マン 問題 n個の整数aとn個の整数pと整数mが与えられる i番目の整数a[i]をp[i]%の確率で選ぶ、という操作を各iについて行い、0個以上n個以下の整数を選ぶ 1以上m以下の整数の中で、選ばれた整数の少なくとも1つで割り切れるものの個数の期待…

包除原理マスターになりたい 問題 n個の相異なる整数aと整数mが与えられる 1以上m以下のそれぞれの整数iについて、aのうちiと互いに素であるものの個数を求めよ1 1 解法 xと互いに素な数 ってのは xの素因数のどれでも割り切れないような数 と言い換えられる…

問題 n(:偶数)頂点の木が与えられる これらの頂点を端点を共有しないペアn/2組に分け、各ペアの2頂点間にリボンを張る どの辺にも少なくとも1本のリボンが張られているようなペアの分け方は何通りあるか2 解法 f(S): Sのどの辺にもリボンが張られていないよ…