結果

問題 No.140 みんなで旅行
ユーザー しらっ亭しらっ亭
提出日時 2015-08-20 03:04:07
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 241 ms / 5,000 ms
コード長 2,554 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 11,004 KB
実行使用メモリ 35,376 KB
最終ジャッジ日時 2023-09-25 13:44:11
合計ジャッジ時間 2,990 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
8,196 KB
testcase_01 AC 16 ms
8,212 KB
testcase_02 AC 26 ms
9,332 KB
testcase_03 AC 16 ms
8,196 KB
testcase_04 AC 16 ms
8,184 KB
testcase_05 AC 16 ms
8,208 KB
testcase_06 AC 16 ms
8,332 KB
testcase_07 AC 16 ms
8,292 KB
testcase_08 AC 16 ms
8,300 KB
testcase_09 AC 16 ms
8,224 KB
testcase_10 AC 16 ms
8,204 KB
testcase_11 AC 238 ms
35,368 KB
testcase_12 AC 22 ms
9,168 KB
testcase_13 AC 18 ms
8,504 KB
testcase_14 AC 241 ms
35,376 KB
testcase_15 AC 240 ms
34,892 KB
testcase_16 AC 97 ms
18,584 KB
testcase_17 AC 53 ms
12,936 KB
testcase_18 AC 189 ms
29,020 KB
testcase_19 AC 206 ms
30,900 KB
testcase_20 AC 44 ms
11,924 KB
testcase_21 AC 17 ms
8,464 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