修正前の問題文:「a,b,c,dが相異なる」の場合以下の条件を満たす通り数dp[n]を考える １：n人存在する ２：n人全てが、いずれかの人と赤or青の糸で結ばれている ３：問題の２条件と最終的な状態の条件を満たす。以上を満たすdp[n]が求まれば、元の問題の答え…

yukicoder No.1857 Gacha Addiction 橙diffが解けたので書く！以下すべてpi=pi/sとする。 i回目で終了するケースを考える これはi-1回目までに重複がなく、i回目に初めて重複が起きる i回目までは無視してi-1回目までを考える。 これはΠ(1+pi)を展開した各項…

yukicoder No.1856 Mex Sum 2 橙diffが解けたので書く！AとかA'は無視して mexがiで長さがjの整数列について考える。 dp[i][j]:=mexがiで長さがjの整数列の通り数 この通り数がわかれば 答えは、ΣΣBinomial(n,i)*pow(m+1,n-i)*dp[j][i]*j になる。なのでdpが…

E:FPS解を考える最終的に左右に動かす数をLとRとすると m個をL+R種類(最低一回は使用)で塗る場合の数は [x^m](e^x-1)^(L+R)*m!であり (e^xとm!は展開すると7!/(3!*2!*2!)みたいな形になるので求めたいものがもとまる) 最後のm-(L+R)以外は左右が自由なのと L…

コンテスト中にバグらせていた自分の解放がやっと通ったのでメモ書き。 以下の３パターンのうちの満たすものを合計する １：Nと上からn桁は一致するNより小さいもの ２：Nより桁数が小さいもの ３：Nそのものその前に前計算パートで memo[i][j]:=丁度j種類の…