結果
問題 | No.140 みんなで旅行 |
ユーザー |
![]() |
提出日時 | 2020-01-21 20:49:08 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 814 ms / 5,000 ms |
コード長 | 2,040 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 43,852 KB |
最終ジャッジ日時 | 2024-07-06 05:19:00 |
合計ジャッジ時間 | 5,561 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
class mint:def __init__(self, x):self.__x = x % mddef __str__(self):return str(self.__x)def __add__(self, other):if isinstance(other, mint): other = other.__xreturn mint(self.__x + other)def __sub__(self, other):if isinstance(other, mint): other = other.__xreturn mint(self.__x - other)def __rsub__(self, other):return mint(other - self.__x)def __mul__(self, other):if isinstance(other, mint): other = other.__xreturn mint(self.__x * other)__radd__ = __add____rmul__ = __mul__def __truediv__(self, other):if isinstance(other, mint): other = other.__xreturn mint(self.__x * pow(other, md - 2, md))def __pow__(self, power, modulo=None):return mint(pow(self.__x, power, md))def nCr(com_n, com_r):if com_n < com_r: return 0return fac[com_n] / fac[com_r] / fac[com_n - com_r]memo = {}def s(n, r):if n < r: return 0if n == r or r == 1: return mint(1)if (n, r) in memo: return memo[n, r]memo[n, r] = res = s(n - 1, r - 1) + r * s(n - 1, r)return res# combinationの準備md = 10 ** 9 + 7n_max = 555fac = [mint(1)]for i in range(1, n_max + 1): fac.append(fac[-1] * i)def main():n = int(input())# 1グループになるのは1通りと分かるので2グループ以上に分かれる場合を考えるans = mint(1)# 夫婦が同じ車に乗るa組と別の車に乗るb組を決めるfor a in range(2, n + 1):b = n - a# n組からa組選ぶのがnCa通りc = nCr(n, a)# a,bを固定したら、gグループ作るときの場合の数を求めるfor g in range(2, a + 1):# a組の夫婦をgグループに分ける方法がs(a,g)通り# bの1組の夫婦の別れ方がg*(g-1)通りif b:ans += c * s(a, g) * pow(g * (g - 1), b, md)else:ans += c * s(a, g)print(ans)main()