結果

問題 No.140 みんなで旅行
ユーザー しらっ亭しらっ亭
提出日時 2015-08-20 03:04:07
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 293 ms / 5,000 ms
コード長 2,554 bytes
コンパイル時間 112 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 37,888 KB
最終ジャッジ日時 2024-07-18 10:47:37
合計ジャッジ時間 2,926 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
10,880 KB
testcase_01 AC 32 ms
10,880 KB
testcase_02 AC 40 ms
12,032 KB
testcase_03 AC 30 ms
10,880 KB
testcase_04 AC 30 ms
11,008 KB
testcase_05 AC 29 ms
10,880 KB
testcase_06 AC 30 ms
11,008 KB
testcase_07 AC 29 ms
10,880 KB
testcase_08 AC 29 ms
10,880 KB
testcase_09 AC 30 ms
11,008 KB
testcase_10 AC 30 ms
10,880 KB
testcase_11 AC 293 ms
37,632 KB
testcase_12 AC 37 ms
11,648 KB
testcase_13 AC 32 ms
11,136 KB
testcase_14 AC 289 ms
37,888 KB
testcase_15 AC 290 ms
37,760 KB
testcase_16 AC 122 ms
21,120 KB
testcase_17 AC 70 ms
15,744 KB
testcase_18 AC 230 ms
31,616 KB
testcase_19 AC 253 ms
33,536 KB
testcase_20 AC 61 ms
14,720 KB
testcase_21 AC 30 ms
11,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
全然わからんので解説を見た
"""

MOD = 10 ** 9 + 7


def combi(n, mod):
    c = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for x in range(n + 1):
        c[x][0] = 1
        for y in range(1, x + 1):
            c[x][y] = (c[x - 1][y] + c[x - 1][y - 1]) % mod
    return c


def solve():
    N = int(input())

    C = combi(N, MOD)

    # F[x][y] は 夫婦同じグループに入る夫婦がx組で、そのx組がyグループに分かれる組み合わせ
    F = [[0 for y in range(N + 1)] for x in range(N + 1)]
    for x in range(1, N + 1):
        F[x][1] = 1
        # y > x のとき、x組の夫婦をy には分けられないので、0通り
        # y = 0 のとき、0組には分けられないので 0通り
        # y = 1 のとき、1 グループに分ける組み合わせは常に1通り
        # なので、y は 2 から x までループさせる
        for y in range(2, x + 1):
            # x組がyグループになるのは以下の和
            #   (x-1)組の夫婦が(y-1)グループを作り、x組目の夫婦が新たなグループを作る場合
            #   (x-1)組の夫婦が  y  グループを作り、x組目の夫婦がそのいずれかに含まれる場合(y 通りあるので y を掛ける)
            F[x][y] = (F[x - 1][y - 1] + y * F[x - 1][y]) % MOD

    # 夫婦同じグループに入る夫婦が既にyグループ作っているとき、同じグループに
    # 入らない夫婦が1組いると、その夫婦の分かれ方はy*(y-1)通り。
    # z組ならそのz乗。そのようなP[y][z] = (y*(y-1))^z を計算。
    P = [[0 for i in range(N + 1)] for j in range(N + 1)]
    for y in range(N + 1):
        P[y][0] = 1  # 0 乗 は 1
        for z in range(1, N + 1):
            # y*y-1 の z-1 乗に、 y*(y-1) を掛ければ、 y*(y-1) の z 乗
            P[y][z] = P[y][z - 1] * (y * (y - 1)) % MOD

    ret = 0
    for x in range(1, N + 1):
        for y in range(1, x + 1):
            # N組中x組の夫婦は夫婦で同じグループに入っており、全体でyグループを構成するケース
            # C[N][x] : まずN組の夫婦のうち、夫婦同じグループに入るx組を選ぶ
            # F[x][y] : そのようなx組の夫婦がyグループを構成する組み合わせ
            # P[y][N-x] : 夫婦別のグループに入る(N-x)組のyグループへの分かれ方
            ret = (ret + C[N][x] * F[x][y] * P[y][N - x]) % MOD

    print(ret)


if __name__ == '__main__':
    solve()
0