結果

問題 No.8034 7 problems
コンテスト
ユーザー tanzaku
提出日時 2018-04-02 22:46:08
言語 Java
(openjdk 23)
結果
AC  
実行時間 464 ms / 2,000 ms
コード長 3,903 bytes
コンパイル時間 4,033 ms
コンパイル使用メモリ 83,104 KB
実行使用メモリ 98,924 KB
最終ジャッジ日時 2024-06-26 06:51:22
合計ジャッジ時間 27,027 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class p3034 {
	int t;
	
//	static {
//		final int mod = (int)1e9+7;
//		int m = 4;
//		int p = 0;
//		for (int i = 1; i < powmod(m, m, mod); i++) {
//			p++;
//		}
//		for (int i = 0; i < m * m * m; i++) {
//			dump(p % m + 1);
//			p /= m;
//		}
//	}
	
	long[] a = new long[(int)1e6];
	long[] fact = new long[(int)1e6];
	public p3034() {
		fact[0] = 1;
		for (int i = 1; i < fact.length; i++) fact[i] = fact[i-1] * i % mod;
		for (long[] d : memo) Arrays.fill(d, -1L);
		for (long[] d : memo2) Arrays.fill(d, -1L);
		
//		for (int n = 1; n <= 10; n++) {
//			long s = 0;
//			for (int j = 1; j < n; j++) {
//				s += rec2(n, j) * j;
//			}
//			System.err.print(s + ",");
//		}
//		dump();
		for (int i = 1; i < a.length; i++) {
			a[i] = (a[i-1] * (i+1) % mod + fact[i]) % mod;
		}
//		dump(a);
		
//		int m = 1+(int)Math.sqrt(100000);
//		long[][] dp = new long[m][100000+1];
//		for (int i = 1; i*i <= 100000; i++) {
//			long[] val = new long[i*i];
//			for (int j = 0; j < i*i; j++) {
//				val[j] = rec3(i*i, j);
//			}
//			mp.put(i*i, val);
//		}
	}
	
	long[][] memo = new long[1000][1000];
	long rec(int n, int d) {
		if (n == 1) return d == 0 ? 1 : 0;
		if (d < 0) return 0;
		if (memo[n][d] < 0) {
			memo[n][d] = (rec(n - 1, d - 1) * powmod(n - 1, mod - 2, mod) % mod + rec(n - 1, d)) % mod;
		}
		return memo[n][d];
	}

	long[][] memo2 = new long[1000][1000];
	long rec2(int n, int d) {
		if (n == 1) return d == 0 ? 1 : 0;
		if (d < 0) return 0;
		if (memo2[n][d] < 0) {
			memo2[n][d] = (rec2(n - 1, d - 1) + rec2(n - 1, d) * (n - 1)) % mod;
		}
		return memo2[n][d];
	}
	
	TreeMap<Integer, long[]> mp = new TreeMap<>();
	long rec3(int n, int d) {
		long[] cache = mp.get(n);
		if (cache != null) return cache[d];
		if (n == 1) return d == 0 ? 1 : 0;
		if (d < 0) return 0;
		if (memo2[n][d] < 0) {
			memo2[n][d] = (rec2(n - 1, d - 1) + rec2(n - 1, d) * (n - 1)) % mod;
		}
		return memo2[n][d];
	}
	
	static final int mod = (int)1e9+7;
	void solveTestcase(final Scanner in, final PrintWriter out) {
		int n = in.nextInt();
		out.println((long)n * n);
		out.println((long)n * n * n - n + (long)n * n);
		out.println(t);
		out.println(4L * n * n + 17);
		out.println(powmod(n, (long)n * n * n, mod));
		out.println(n);
		
//		long ans = 0;
//		for (int j = 1; j < n; j++) {
////			dump(n, j, rec2(n, j));
//			ans += rec2(n, j) * j % mod ;
//		}
//		ans %= mod;
//		out.println(ans* n % mod);
		out.println(a[n-1] * n % mod);
	}
	
	void solve() {
		try (final PrintWriter out = new PrintWriter(System.out)) {
			try (final Scanner in = new Scanner(System.in)) {
				t = in.nextInt();
//				int t = 1;
				for (int x = 0; x < t; x++) {
					if (x != 0) {
						out.println();
					}
					solveTestcase(in, out);
				}
			}
		}
	}
	private static int[] permutation(int n) {
		int[] ps = new int[n];
		for(int i = 0; i < n; i++) ps[i] = i;
		return ps;
	}
	private static final void swap(int[] xs, int i, int j) {
		final int t = xs[j];
		xs[j] = xs[i];
		xs[i] = t;
	}
	private static final boolean nextPermutation(final int[] xs) {
		for(int i = xs.length - 1; i > 0; i--) {
			if(xs[i - 1] > xs[i]) {
				continue;
			}

			for(int j = i, k = xs.length - 1; j < k; j++, k--) {
				swap(xs, j, k);
			}

			for(int j = i; j < xs.length; j++) if(xs[j] > xs[i - 1]) {
				swap(xs, j, i - 1);
				break;
			}

			return true;
		}
		return false;
	}

	static long powmod(long n, long r, int m) {
		long res = 1;
		for(; r != 0; r >>>= 1, n = n * n % m) {
			if((r&1) == 1) {
				res = res * n;
				if(res >= m) {
					res %= m;
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
		new p3034().solve();
	}

	static void dump(Object...objects) { System.err.println(Arrays.deepToString(objects)); }
}
0