結果

問題 No.140 みんなで旅行
ユーザー krotonkroton
提出日時 2015-01-30 00:37:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 1,029 bytes
コンパイル時間 1,259 ms
コンパイル使用メモリ 144,628 KB
実行使用メモリ 12,040 KB
最終ジャッジ日時 2023-09-05 08:14:22
合計ジャッジ時間 2,437 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
11,744 KB
testcase_01 AC 7 ms
11,748 KB
testcase_02 AC 8 ms
11,768 KB
testcase_03 AC 8 ms
11,824 KB
testcase_04 AC 8 ms
11,764 KB
testcase_05 AC 7 ms
11,748 KB
testcase_06 AC 8 ms
11,848 KB
testcase_07 AC 7 ms
11,784 KB
testcase_08 AC 8 ms
11,840 KB
testcase_09 AC 7 ms
11,852 KB
testcase_10 AC 7 ms
11,912 KB
testcase_11 AC 9 ms
11,896 KB
testcase_12 AC 8 ms
11,784 KB
testcase_13 AC 8 ms
12,040 KB
testcase_14 AC 9 ms
11,968 KB
testcase_15 AC 9 ms
11,744 KB
testcase_16 AC 8 ms
11,776 KB
testcase_17 AC 7 ms
11,764 KB
testcase_18 AC 8 ms
11,764 KB
testcase_19 AC 8 ms
11,760 KB
testcase_20 AC 7 ms
11,748 KB
testcase_21 AC 8 ms
11,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

/*
A[n][k] := n組をkグループにわける(夫婦は同じグループに)
B[k][n] := すでにできているkグループにn組をわける(夫婦は別のグループに)
C[n][k] := 普通の組み合わせ
*/

ll A[600][600], B[600][600], C[600][600];

int main(){
	for(int n=0;n<600;n++){
		for(int k=0;k<=n;k++){
			if(k == 0 || k == n){
				C[n][k] = 1;
			} else {
				C[n][k] = (C[n-1][k] + C[n-1][k-1]) % MOD;
			}
		}
	}
	for(int n=1;n<600;n++){
		A[n][1] = 1;
		for(int k=2;k<=n;k++){
			A[n][k] = (A[n-1][k] * k + A[n-1][k-1]) % MOD;
		}
	}
	for(int k=1;k<600;k++){
		B[k][0] = 1;
		for(int n=1;n<600;n++){
			B[k][n] = B[k][n-1] * k * (k - 1) % MOD;
		}
	}

	int n; cin >> n;

	ll res = 0;
	for(int x=1;x<=n;x++){
		for(int k=1;k<=x;k++){
			int y = n - x;
			
			ll tmp = C[n][x];
			tmp = (tmp * A[x][k]) % MOD;
			tmp = (tmp * B[k][y]) % MOD;

			res = (res + tmp) % MOD;
		}
	}

	cout << res << endl;
	return 0;
}
0