結果

問題 No.140 みんなで旅行
ユーザー hos.lyric
提出日時 2015-01-29 23:35:15
言語 D
(dmd 2.083.0)
結果
AC  
実行時間 36 ms
コード長 2,805 Byte
コンパイル時間 1,918 ms
使用メモリ 32,300 KB
最終ジャッジ日時 2019-07-29 21:10:40

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 30 ms
30,784 KB
sample2.txt AC 30 ms
32,036 KB
sample3.txt AC 30 ms
30,520 KB
testcase01.txt AC 29 ms
31,512 KB
testcase02.txt AC 30 ms
31,776 KB
testcase03.txt AC 30 ms
30,784 KB
testcase04.txt AC 31 ms
32,300 KB
testcase05.txt AC 29 ms
30,520 KB
testcase06.txt AC 30 ms
32,300 KB
testcase07.txt AC 31 ms
32,040 KB
testcase08.txt AC 30 ms
32,300 KB
testcase09.txt AC 35 ms
30,524 KB
testcase10.txt AC 31 ms
32,300 KB
testcase11.txt AC 30 ms
31,312 KB
testcase12.txt AC 35 ms
30,784 KB
testcase13.txt AC 35 ms
32,036 KB
testcase14.txt AC 36 ms
31,776 KB
testcase15.txt AC 33 ms
31,312 KB
testcase16.txt AC 32 ms
30,524 KB
testcase17.txt AC 33 ms
32,040 KB
testcase18.txt AC 31 ms
31,052 KB
testcase19.txt AC 30 ms
31,776 KB
テストケース一括ダウンロード

ソースコード

diff #
import core.thread;
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex;

//	Input
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { tokens = readln.split; if (stdin.eof) throw new EOFException; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return to!int(readToken); }
long readLong() { return to!long(readToken); }
real readReal() { return to!real(readToken); }

//	chmin/chmax
void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

//	Pair
struct Pair(S, T) {
	S x; T y;
	int opCmp(    const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	int opCmp(ref const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	string toString() const { return "(" ~ to!string(x) ~ ", " ~ to!string(y) ~ ")"; }
}
auto pair(S, T)(inout(S) x, inout(T) y) { return Pair!(S, T)(x, y); }

//	Array
int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = as.length; for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <  val); }); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <= val); }); }
T[] unique(T)(in T[] as) { T[] bs; foreach (a; as) if (bs.empty || bs[$ - 1] != a) bs ~= a; return bs; }


immutable MO = 10L^^9 + 7;
immutable LIM = 555 * 2 + 5;

long[] inv, fac, facInv;
long[][] bn, S;

int N;

void main(string[] args) {
	inv = new long[LIM];
	inv[1] = 1;
	foreach (i; 2 .. LIM) {
		inv[i] = MO - MO / i * inv[cast(size_t)(MO % i)] % MO;
	}
	fac = new long[LIM];
	facInv = new long[LIM];
	fac[0] = facInv[0] = 1;
	foreach (i; 1 .. LIM) {
		fac[i] = fac[i - 1] * i % MO;
		facInv[i] = facInv[i - 1] * inv[i] % MO;
	}
	
	bn = new long[][](LIM, LIM);
	foreach (n; 0 .. LIM) {
		bn[n][0] = 1;
		bn[n][n] = 1;
		foreach (k; 1 .. n) {
			bn[n][k] = (bn[n - 1][k - 1] + bn[n - 1][k]) % MO;
		}
	}
	S = new long[][](LIM, LIM);
	foreach (n; 0 .. LIM) {
		S[n][0] = 0;
		S[n][n] = 1;
		foreach (k; 1 .. n) {
			S[n][k] = (S[n - 1][k - 1] + k * S[n - 1][k]) % MO;
		}
	}
	
	try {
	for (; ; ) {
		N = readInt;
		
		long ans;
		foreach (k; 1 .. N + 1) {
			long sep = 1;
			foreach_reverse (x; k .. N + 1) {
				long tmp = 1;
				(tmp *= bn[N][x]) %= MO;
				(tmp *= S[x][k]) %= MO;
				(tmp *= sep) %= MO;
debug{
if(N<=3)writeln(k," ",x,"  ",bn[N][x]," ",S[x][k]," ",sep,"  ",tmp);
}
				(ans += tmp) %= MO;
				(sep *= (k * (k - 1))) %= MO;
			}
		}
		writeln(ans);
		
	}
	} catch (EOFException) {}
}
0