長さNの1〜Nの数字が1つずつある数列でどの隣り合った3つの数字を選んでも門松列になっている数列は何通りあるか。1e9+7で割った余りを求めよ。終了後に解説見ました。「合ってるやん!!」と突っ込みました。nCmを前計算することを忘れていたんですね。この時、oが3つ以上並んでいたらそのoの列は門松列列を満たしていなければなりません。5を含んでも門松列を満たさなければいけないです。oは絶対に門松列を満たします。左にoが2つであれば2つのうち大きい方を左側、小さい方を右側に持っていった1通り。oが3つ以上であればその列自体が門松列列を満たす必要があります。oがx個あるとすると、各要素を(x-o+1)とすることでまた条件を満たす門松列列が出来ます。この時右端の2要素の上下関係が逆転します。x個の門松列列の数の半分が左側に入り得る、ということになります。n=4まではサンプルに入っているので、n=5からnの新しく入る位置をループで回しながら、右側の空きの個数の門松列列の通り数×左側の空きの個数の門松列列の個数×n個からの右側の個数の選び方をして、更に左右の空き個数が3個以上なら2で割った数字を毎回足してあげればOKです。割るときはフェルマーの小定理を用いて逆元を求めましょう。i=5;i<=n;i++){//i個の順列。iを除いた0〜(i-1)までの順列を利用。0;}感想ここはサラッと流したかったのだけれども、三角形求める時点でミスが発覚して大幅タイムロス。今後活かせるからいいや。Bernoulli「3月中に毎日1問解いて黄色になろう!」キャンペーン5問目。Sort今年の解き納め問題。#1(E、G)忘れそうなのでEとGも。日)ネットの海に生息するらしいバーチャルグソクムシ。競プロとCTFをメインに、たまにEsolangを混ぜます。(7)月別アーカイブリンクGitHubはてなブログをはじめよう!Hyogaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。