結果

問題 No.140 みんなで旅行
ユーザー hos.lyric
提出日時 2015-01-29 23:35:15
言語 D
(dmd 2.083.0)
結果
AC  
実行時間 38 ms
コード長 2,805 Byte
コンパイル時間 2,091 ms
使用メモリ 28,572 KB
最終ジャッジ日時 2018-12-03 05:57:14

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 32 ms
28,572 KB
sample2.txt AC 33 ms
28,572 KB
sample3.txt AC 33 ms
28,568 KB
testcase01.txt AC 31 ms
28,572 KB
testcase02.txt AC 33 ms
28,568 KB
testcase03.txt AC 32 ms
28,568 KB
testcase04.txt AC 32 ms
28,572 KB
testcase05.txt AC 32 ms
28,572 KB
testcase06.txt AC 32 ms
28,572 KB
testcase07.txt AC 30 ms
28,568 KB
testcase08.txt AC 32 ms
28,568 KB
testcase09.txt AC 36 ms
28,568 KB
testcase10.txt AC 32 ms
28,568 KB
testcase11.txt AC 33 ms
28,568 KB
testcase12.txt AC 37 ms
28,572 KB
testcase13.txt AC 38 ms
28,568 KB
testcase14.txt AC 34 ms
28,568 KB
testcase15.txt AC 32 ms
28,572 KB
testcase16.txt AC 34 ms
28,572 KB
testcase17.txt AC 35 ms
28,568 KB
testcase18.txt AC 31 ms
28,572 KB
testcase19.txt AC 31 ms
28,572 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