parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ ゼータ変換 メビウス変換 フレンズの数K<=20なので、O(K2 * K)みたいな計算量で解けそう。 とりあえず自明に求まるものを求めてみる。 任意のフレンズの集合に対してそのフレンズのいるところを必ず通る経路をすべて求める。フレンズの位置の集合をSとする。Sのすべての要素をa[i]<=a[j]かつb[i]<=b[j]ならばi, jという順に並び変えられるならば、Sのすべてを通る経路がある。そうでなければ経路の数は0。 この経路の求め方を考えてみる。これは簡単で、Sの要素をたとえばi1,i2,i3としてこの順に並び変えられた時 (0, 0) => (a[i1], b[i1]) => (a[i2], b[i2]) => … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2019%2F01%2F25%2F174249" title="No.767 配られたジャパリまん - yukicoder - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-01-25 17:42:49 rich https://par.hateblo.jp/entry/2019/01/25/174249 1.0 100%