結局、フェルマーの小定理から x = i のとき 1 で、それ以外の時に 0 となるような p-1 次式が作れてしまうというだけの問題。賢い。 あとは a[ i ] = 1 のときに毎回 1 - (x-i)^(p-1) の係数を二項定理で作るだけ。 p = int(input()) a = list(map(int, inp…

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

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…