結果

問題 No.140 みんなで旅行
ユーザー しらっ亭
提出日時 2015-08-20 03:04:07
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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