2323 PERMS

2323 PERMS



概要

1からn、n個の数からなる順列を考えたとき、ある２つの数を見たとき

大きい数が小さい数より前（左側）にあるときinversionであるという。

例えば<312>は3>1と3>2より2 inversionsである。

nとkが与えられたとき、n個の数からなる全ての順列の内、k inversionsである

順列は何個あるかを答えよ。

next_permutationを使って順列permを生成して、

for (int i = 0; i < n; ++i)
    for (int j = i+1; j < n; ++j)
        if (perm[i] > perm[j]) ++inversions;

とやっていくと、O(n!*n^2)でTLEは明らか。

よって他の方法（きっとDP的解法）を模索する。

とはいっても方針が立たなかったので↑の方法で、
できるところまで実際に計算させてみる。

すると以下のような結果になる。

n=1  1

  2  1  1

  3  1  2  2  1

  4  1  3  5  6  5  3  1

  5  1  4  9 15 20 22 20 15  9  4  1

  ...

ここであるnの項差に注目すると

map[n][k] = map[n-1][0] + map[n-1][1] + ... + map[n-1][k];

になっている。（一部例外あり）

どういうことか考えてみた。


n=4を例に取ると、
0 inversionは<1234>だけである。これはn=3の0 inversionにあたる<123>の末尾に4をつけた形である。
また、1 inversionは<1243>,<1324>,<2134>の3つである。これはn=3の0 inversionである<123>に
１つだけinversionが起こるように4を追加したものと、n=3の1 inversionsである<132>と<213>に
inversionが起こらないように4を追加したものである。
このように仮説の意味が理解できる。


しかし、n=5のとき、5 inversionsは22個であるが、map[4][0] + ... + map[4][5]は23であり、
仮説に矛盾が生じている。
これは次のように理解できる。


n-1個の数からなる順列に数nを追加して増やせるinversionsの最大値は、
nを先頭（左端）に追加したときのn-1である。
よって、nのときk inversionsを計算するにあたって、k'+(n-1) < kであるmap[n-1][k']の値は
加算してはいけない。


このように考えると、map[5][5] = map[4][1] + ... + map[4][5] = 22となり正しい。

#include<cstdio>
#include<cstring>

using namespace std;

int main() {
    long long int map[19][201];
    memset(map, 0, sizeof(map));
    map[1][0] = 1;
    for (int n = 2; n <= 18; ++n)
        for (int k = 0; k <= 1+(n-1)*n/2; ++k)
            for (int i = k, c = 0; i >= 0 && c < n; --i, ++c)
                map[n][k] += map[n-1][i];
    int n, k;
    while (scanf("%d %d", &n, &k), n)
        printf("%lld\n", map[n][k]);
}