#249379 (Java21) No.3034 7 problems

提出ソース

結果

問題	No.3034 7 problems
ユーザー	tanzaku
提出日時	2018-04-02 22:46:08
言語	Java21 (openjdk 21)
結果	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	215 ms 85,508 KB
testcase_01	AC	213 ms 85,564 KB
testcase_02	AC	421 ms 96,720 KB
testcase_03	AC	363 ms 91,160 KB
testcase_04	AC	351 ms 89,004 KB
testcase_05	AC	403 ms 94,244 KB
testcase_06	AC	410 ms 93,856 KB
testcase_07	AC	400 ms 93,960 KB
testcase_08	AC	390 ms 91,420 KB
testcase_09	AC	418 ms 94,140 KB
testcase_10	AC	353 ms 89,020 KB
testcase_11	AC	404 ms 91,864 KB
testcase_12	AC	372 ms 89,352 KB
testcase_13	AC	383 ms 91,524 KB
testcase_14	AC	381 ms 91,288 KB
testcase_15	AC	362 ms 91,588 KB
testcase_16	AC	384 ms 91,408 KB
testcase_17	AC	380 ms 91,516 KB
testcase_18	AC	452 ms 98,688 KB
testcase_19	AC	393 ms 91,452 KB
testcase_20	AC	402 ms 93,860 KB
testcase_21	AC	343 ms 86,480 KB
testcase_22	AC	430 ms 96,552 KB
testcase_23	AC	390 ms 91,356 KB
testcase_24	AC	435 ms 96,736 KB
testcase_25	AC	430 ms 94,124 KB
testcase_26	AC	342 ms 86,708 KB
testcase_27	AC	464 ms 98,924 KB
testcase_28	AC	415 ms 94,068 KB
testcase_29	AC	415 ms 94,348 KB
testcase_30	AC	343 ms 86,344 KB
testcase_31	AC	418 ms 94,256 KB
testcase_32	AC	378 ms 89,188 KB
testcase_33	AC	410 ms 94,488 KB
testcase_34	AC	351 ms 86,820 KB
testcase_35	AC	422 ms 94,260 KB
testcase_36	AC	387 ms 91,352 KB
testcase_37	AC	320 ms 86,056 KB
testcase_38	AC	410 ms 94,360 KB
testcase_39	AC	415 ms 94,300 KB
testcase_40	AC	439 ms 96,816 KB
testcase_41	AC	370 ms 89,140 KB
testcase_42	AC	422 ms 94,420 KB
testcase_43	AC	454 ms 98,728 KB
testcase_44	AC	357 ms 89,000 KB
testcase_45	AC	379 ms 91,452 KB
testcase_46	AC	364 ms 89,148 KB
testcase_47	AC	357 ms 89,144 KB
testcase_48	AC	346 ms 89,148 KB
testcase_49	AC	446 ms 96,688 KB
testcase_50	AC	354 ms 89,052 KB
testcase_51	AC	360 ms 89,168 KB
testcase_52	AC	222 ms 85,280 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)); }
}

yukicoder

結果

テストケース

ソースコード