結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 23 ms
31,508 KB
sample2.txt AC 22 ms
30,788 KB
sample3.txt AC 23 ms
32,300 KB
testcase01.txt AC 23 ms
31,312 KB
testcase02.txt AC 22 ms
31,052 KB
testcase03.txt AC 23 ms
31,776 KB
testcase04.txt AC 22 ms
30,524 KB
testcase05.txt AC 23 ms
31,052 KB
testcase06.txt AC 22 ms
32,304 KB
testcase07.txt AC 24 ms
32,568 KB
testcase08.txt AC 23 ms
30,520 KB
testcase09.txt AC 27 ms
31,312 KB
testcase10.txt AC 23 ms
31,772 KB
testcase11.txt AC 22 ms
31,048 KB
testcase12.txt AC 27 ms
32,568 KB
testcase13.txt AC 26 ms
31,776 KB
testcase14.txt AC 24 ms
32,036 KB
testcase15.txt AC 24 ms
31,312 KB
testcase16.txt AC 27 ms
31,048 KB
testcase17.txt AC 30 ms
32,300 KB
testcase18.txt AC 23 ms
32,036 KB
testcase19.txt AC 22 ms
31,508 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