一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

約数系の包除原理の問題として解いたけど、どう帰着するのかわからなかった。 まず lcm ではなくて最大公約数 gcd で考える。 lcm( i,k ) = i*k//gcd( i,k ) で求まる。 すると、1 ≦ i ≦ n, k なので、k の約数の集合を g とすると、g = gcd( i,k ) になる i…

172 4完 パフォ1421 173 4完 パフォ1319 まあ失敗ではないけど大成功でもない感じ。次で水色なりたいね。 172は包除原理の一般法則を知らなかったのが原因。Fは難しかった。 #172 E import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.re…