f(n, m):= nxnのときの配置可能な最大の1の数とする。ただし、1<=m<=n任意のnについてf(n, 1) = 0よって x = 0 のときは例外として処理する。以下、m>=2、x>=1とする。nxnのm-free行列について1が最大となる置き方の一つはmxmの部分行列ごとに、右下に1個0の…

すべての頂点iについて(a[i], i)を終点候補として優先順位度付きキューに突っ込んおく。(u[i], v[i]) 間をコスト2w[i]の無向辺で接続したグラフでダイクストラ法っぽいことをする。 まず往復についてであるが、往路と復路の最短経路の長さが等しいことは明ら…

すべての順列を見ていくのは明らかに無理なので、a[j]ごとに計算していく。つまり、f[a] = f[a] + a[M(もとの配列の添字はj)] となるような順列を数える。その数えをg(j)としておく。g(j)さえ求まれば解はΣa[j]g(j) a[j]より大きい値の数えをx, a[j]以上値の…