#249379 (Java21) No.3034 7 problems

提出ソース

結果

問題	No.3034 7 problems
ユーザー	tanzaku
提出日時	2018-04-02 22:46:08
言語	Java21 (openjdk 21)
結果	AC
実行時間	442 ms / 2,000 ms
コード長	3,903 bytes
コンパイル時間	5,866 ms
コンパイル使用メモリ	80,408 KB
実行使用メモリ	100,552 KB
最終ジャッジ日時	2023-09-08 13:43:18
合計ジャッジ時間	26,425 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	194 ms 87,068 KB
testcase_01	AC	195 ms 86,876 KB
testcase_02	AC	410 ms 98,068 KB
testcase_03	AC	329 ms 91,136 KB
testcase_04	AC	340 ms 89,356 KB
testcase_05	AC	387 ms 96,036 KB
testcase_06	AC	387 ms 95,864 KB
testcase_07	AC	392 ms 95,368 KB
testcase_08	AC	384 ms 93,372 KB
testcase_09	AC	387 ms 95,840 KB
testcase_10	AC	337 ms 91,284 KB
testcase_11	AC	373 ms 95,216 KB
testcase_12	AC	345 ms 90,984 KB
testcase_13	AC	368 ms 92,940 KB
testcase_14	AC	353 ms 93,080 KB
testcase_15	AC	360 ms 93,324 KB
testcase_16	AC	357 ms 93,476 KB
testcase_17	AC	368 ms 91,792 KB
testcase_18	AC	436 ms 100,552 KB
testcase_19	AC	366 ms 92,996 KB
testcase_20	AC	391 ms 96,124 KB
testcase_21	AC	342 ms 88,468 KB
testcase_22	AC	411 ms 97,976 KB
testcase_23	AC	358 ms 92,608 KB
testcase_24	AC	408 ms 98,504 KB
testcase_25	AC	394 ms 98,264 KB
testcase_26	AC	324 ms 90,640 KB
testcase_27	AC	442 ms 100,468 KB
testcase_28	AC	399 ms 95,620 KB
testcase_29	AC	380 ms 95,848 KB
testcase_30	AC	318 ms 88,176 KB
testcase_31	AC	392 ms 96,092 KB
testcase_32	AC	353 ms 93,552 KB
testcase_33	AC	389 ms 95,808 KB
testcase_34	AC	323 ms 90,928 KB
testcase_35	AC	387 ms 95,664 KB
testcase_36	AC	342 ms 93,212 KB
testcase_37	AC	302 ms 87,480 KB
testcase_38	AC	386 ms 95,592 KB
testcase_39	AC	386 ms 95,844 KB
testcase_40	AC	401 ms 97,860 KB
testcase_41	AC	342 ms 91,216 KB
testcase_42	AC	390 ms 95,856 KB
testcase_43	AC	421 ms 100,180 KB
testcase_44	AC	335 ms 88,760 KB
testcase_45	AC	368 ms 93,372 KB
testcase_46	AC	344 ms 91,344 KB
testcase_47	AC	334 ms 91,576 KB
testcase_48	AC	330 ms 90,840 KB
testcase_49	AC	418 ms 98,416 KB
testcase_50	AC	360 ms 90,912 KB
testcase_51	AC	332 ms 91,044 KB
testcase_52	AC	196 ms 86,972 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

結果

テストケース

ソースコード