左端のビンから考え、DP をする。 dp[i: i 番目のビン][j: i 番目のビンは、左の i 個のビンの中で j 番目に使われる][k: (i+1)番目のビンが i 番目のビンよりあとなら 1、そうでないなら 0] ::= 条件を満たす状態数 とし、累積和を計算しながら DP を計算す…

頂点 0 まで戻ってくる場合の問題について考える。 すると、無駄な探索をしなければ、L/2+1 個の頂点に到達することができる。 頂点 0 まで戻る必要が無い場合には、深さが最大となる頂点までの距離の分 (すなわち深さの最大値) だけ移動距離を増やせるため…

求める値は、簡単な考察で分かる。(各 i に対して、どこに辺を張るかを考えると、辺を張るときは K-1 倍、張らないとき K 倍となる) M が 10^6 以下と小さいので、1 周期分計算し、周期の回数(N/M回)だけかけ、周期からはみ出す分(N%M の部分)を掛け合わせれ…

lcm は、各素数ごとに max を取るのと同じなので、各素数ごとに独立に M の lower bound を計算できる。 class MissingLCM { public: bool isPrime(ll x){ if(x<=1) return false; for(ll i = 2; i*i <= x; i++) if(x%i==0) return false; return true; } in…

各頂点に対して独立に期待値を求める。 有向グラフにして考える。 開始頂点を w とする。 頂点 u から v に辺が張られているとする。u が先に招待される場合は、自明に u は招待される。 v が先に招待される場合は、v の先の頂点まで見る必要があるので DFS …

想定解とはおそらく少し違う方法で解いた (定数倍高速化を頑張って TLE ギリギリなので、想定解が思いつくならそちらの方がよい。)まず、i 日目で隣り合う 2 人がどうペアになるか全列挙し、高速ゼータ変換を行う。すると、i 日目の食事で、ペアにできない人…