結果
| 問題 | No.140 みんなで旅行 |
| ユーザー |
 Grenache
|
| 提出日時 | 2017-09-11 21:56:04 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 191 ms / 5,000 ms |
| コード長 | 5,314 bytes |
| コンパイル時間 | 3,961 ms |
| コンパイル使用メモリ | 78,156 KB |
| 実行使用メモリ | 43,948 KB |
| 最終ジャッジ日時 | 2024-11-07 17:08:58 |
| 合計ジャッジ時間 | 8,002 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder140 {private static Scanner sc;private static Printer pr;private static void solve() {final int MOD = 1_000_000_007;int n = sc.nextInt();PC pc = new PC(n, MOD);long[][] S = new long[n + 1][n + 1];S[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {S[i][j] += S[i - 1][j - 1];S[i][j] %= MOD;S[i][j] += S[i - 1][j] * j % MOD;S[i][j] %= MOD;// if (S[i][j] != pc.S(i, j)) {// pr.printf("NG %d %d %d\n", i, j, S[i][j]);// }}}long ans = 0;for (int j = 1; j <= n; j++) {// int S(long n, int r) {// int[] S = new int[j];// int r = j;// long ret = 0;// for (int i = 1; i <= r; i++) {// long tmp = (r - i) % 2 == 0 ? 1 : -1;// tmp *= pc.pow(i, n) * pc.C(r, i) % MOD;// ret = (ret + tmp + MOD) % MOD;// S[i - 1] = (int)(ret * pc.ifact[i] % MOD);// }// ret = ret * ifact[r] % MOD;for (int i = 1; i <= j; i++) {long tmp = pc.C(n, j);// tmp *= pc.S(j, i);tmp *= S[j][i];tmp %= MOD;tmp *= pc.pow(i * (i - 1), n - j);tmp %= MOD;ans += tmp;ans %= MOD;}}pr.println(ans);}@SuppressWarnings("unused")private static class PC {// MOD must be prime number.int MOD;// fact[i] : i! % MODlong[] fact;// ifact[i] : 1/i! % MODlong[] ifact;PC(int size, int MOD) {// O(size)// n=sizeまでのnCrを求める。// nHrはn+r-1Crになってしまうので注意this.MOD = MOD;fact = new long[size + 1];fact[0] = 1;for (int i = 1; i <= size; i++) {fact[i] = fact[i - 1] * i % MOD;}ifact = new long[size + 1];int loop = MOD - 2;long x = fact[size];ifact[size] = 1;while (loop > 0) {if (loop % 2 == 1) {ifact[size] = ifact[size] * x % MOD;}x = x * x % MOD;loop /= 2;}for (int i = size - 1; i >= 0; i--) {ifact[i] = ifact[i + 1] * (i + 1) % MOD;}}// 組合せの数int C(int n, int r) {if (r > n) {return 0;}return (int)(((fact[n] * ifact[n - r]) % MOD) * ifact[r] % MOD);}// 順列int P(int n, int r) {if (r > n) {return 0;}return (int)((fact[n] * ifact[n -r]) % MOD);}// 重複組み合わせ// 異なるn種のものから重複を許してr個を選ぶ場合の数// 0個の種類もあり得るint H(int n, int r) {if (n == 0 && r == 0) {return 1;}return C(n + r - 1, r);}// 組合せの数(nが大きいとき)// O(r)で求めることができる。rはsizeの大きさまでint C2(long n, int r) {long ret = ifact[r];for (int i = 1; i <= r; i++) {long tmp = (n - r + i) % MOD;ret = (ret * tmp) % MOD;}return (int)ret;}// 第2種スターリング数// n人をちょうどr個のグループに分ける(グループの区別はなし)// グループの区別をする場合はr!S(n,r)。全射の場合の数と同義// O(r log n)int S(long n, int r) {//全射の場合の数を包除原理を使って求めて、1/r!をかける。long ret = 0;for (int i = 1; i <= r; i++) {long tmp = (r - i) % 2 == 0 ? 1 : -1;tmp *= pow(i, n) * C(r, i) % MOD;ret = (ret + tmp + MOD) % MOD;}ret = ret * ifact[r] % MOD;return (int)ret;}long pow(int a, long n) {long loop = n;long ret = 1;long x = a;while (loop > 0) {if (loop % 2 == 1) {ret = ret * x % MOD;}x = x * x % MOD;loop /= 2;}return ret;}// 組合せの数// パスカルの三角形MODなし// 限界：n=66 : 66C33=7219428434016265740private final static int LIMIT = 66;private static int to;private static long[][] cache;static long CLong(int n, int r) {if (r > n) {return 0;}if (n > LIMIT) {throw new IllegalArgumentException(Integer.toString(n));}if (cache == null) {cache = new long[LIMIT + 1][];cache[0] = new long[1];cache[0][0] = 1;to = 0;}if (cache[n] == null) {for (int i = to + 1; i <= n; i++) {cache[i] = new long[i + 1];for (int j = 0; j <= i; j++) {if (j == 0 || j == i) {cache[i][j] = 1;} else {if (Long.MAX_VALUE - cache[i - 1][j - 1] < cache[i - 1][j]) {throw new IllegalArgumentException("Overflow");} else {cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j];}}}}to = n;}return cache[n][r];}}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}