結果

問題 No.3034 7 problems
ユーザー GrenacheGrenache
提出日時 2018-04-02 20:13:11
言語 Java21
(openjdk 21)
結果
AC  
実行時間 408 ms / 2,000 ms
コード長 10,315 bytes
コンパイル時間 4,060 ms
コンパイル使用メモリ 76,096 KB
実行使用メモリ 63,284 KB
最終ジャッジ日時 2023-09-08 13:33:06
合計ジャッジ時間 25,865 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
60,344 KB
testcase_01 AC 150 ms
60,436 KB
testcase_02 AC 369 ms
62,528 KB
testcase_03 AC 289 ms
61,104 KB
testcase_04 AC 289 ms
61,232 KB
testcase_05 AC 350 ms
62,592 KB
testcase_06 AC 347 ms
62,176 KB
testcase_07 AC 358 ms
61,960 KB
testcase_08 AC 327 ms
61,508 KB
testcase_09 AC 355 ms
62,624 KB
testcase_10 AC 292 ms
61,588 KB
testcase_11 AC 337 ms
61,624 KB
testcase_12 AC 308 ms
61,080 KB
testcase_13 AC 322 ms
61,456 KB
testcase_14 AC 310 ms
61,428 KB
testcase_15 AC 320 ms
61,872 KB
testcase_16 AC 339 ms
61,496 KB
testcase_17 AC 328 ms
61,956 KB
testcase_18 AC 400 ms
62,608 KB
testcase_19 AC 353 ms
62,432 KB
testcase_20 AC 348 ms
62,144 KB
testcase_21 AC 279 ms
61,224 KB
testcase_22 AC 380 ms
62,828 KB
testcase_23 AC 324 ms
61,564 KB
testcase_24 AC 380 ms
62,536 KB
testcase_25 AC 372 ms
62,588 KB
testcase_26 AC 283 ms
61,216 KB
testcase_27 AC 408 ms
62,492 KB
testcase_28 AC 355 ms
62,552 KB
testcase_29 AC 357 ms
62,012 KB
testcase_30 AC 284 ms
60,952 KB
testcase_31 AC 365 ms
62,436 KB
testcase_32 AC 310 ms
61,796 KB
testcase_33 AC 361 ms
62,668 KB
testcase_34 AC 283 ms
61,352 KB
testcase_35 AC 360 ms
62,360 KB
testcase_36 AC 333 ms
61,816 KB
testcase_37 AC 261 ms
61,448 KB
testcase_38 AC 369 ms
62,340 KB
testcase_39 AC 350 ms
62,300 KB
testcase_40 AC 377 ms
62,468 KB
testcase_41 AC 304 ms
61,504 KB
testcase_42 AC 357 ms
62,348 KB
testcase_43 AC 399 ms
62,420 KB
testcase_44 AC 291 ms
60,980 KB
testcase_45 AC 338 ms
61,732 KB
testcase_46 AC 325 ms
63,284 KB
testcase_47 AC 317 ms
61,300 KB
testcase_48 AC 306 ms
61,380 KB
testcase_49 AC 406 ms
62,564 KB
testcase_50 AC 316 ms
61,672 KB
testcase_51 AC 312 ms
61,228 KB
testcase_52 AC 151 ms
60,184 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;


public class Main_yukicoder3034 {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		final int MOD = 1_000_000_007;

//		String s1 = "33-06-53-53"; // As C I I
//		String s2 = "100111011000111101000110111111101011110100110010111011101101110110111011011111100111111010111100101100001110011011101011100111110000111000011110010111010101011101101000110000111010101101001110110111001010101100110101111011111101110110111111001111110101111001011000011100110111010111011101101001110100011000011101000110010111011101101110110011111000011101110110000111010010101110110101111011111101110110111111001111110101111001011000011100110111010111011101101001100111001011010110001110101111000011101001111001111011111110101111001111000011110011111010111100101110101010111010010011101011110000111010011101101110010111011101101111111001111011111110101111001111000011100100110010111010001100001101101101100010101100100100110111011101110110111111010001100001110111011011101101001110010011001011101001110001111010001101001111100111011111110101111001011000011101110110111011100111110101111010111101111101111110110111011111100011110100011010011101001111010011001011110011110010111010011110011111010111101011000001111011111011111110011110010111010011110011110010111010011110011110100011010010101100110001111010001101111111010111101001100101110111011011101001001010101101100011110100110111111000111101000110111111101011110100110010111011101101110100000111011101101111110000111010011100100110000111011101101001110100011001011101110110111011101111101111111010011100111110101110100111010111100001111001111101011110010111010101011101110011110111111101011110011110000111001111100001110111111101111100001111010011101001100001110000111101001101111110111011010011101000110000111010111101001110011111000011100100110010111010111101001111010011001011101001111001011101010101110110101111011111101011110111111001001100101010110011010111101001110111011011111110011111010111010111101111110000111101111101111010110001100101101001110101011011111110101100111011010011101011110000111011101101111111001111101011100010110010111101001100101110111011011111110011110010111010011110011111010111101011001010110111011010011110100111001111101011101001111010011001011101110110111111000111101000110111111101011110100110010111011101101110011000111101001101111110001111010001101111111010111101001100101110111011011101001010110111011011111101011111100111011111110010110100111011101101111111001111011111110101111011111000011110100110111111101001100101110100111001111101001111001111101011110010111010101011101110010110000111011101101110110010011000011101101111010111011101101001110101111011111110101111001111001011101001111001111000011110010110010111100101110101110101111010011101110110111111100111110101110101111011111100001110111011011111101011110100111101001100001110100111000111101000110100111101111101111101100011101001101111111001111010001101001111010011000011110100110111111010111101001010110010011100100001101100011101111101111011000101100001011110011100101010110110111110010011001011110111110000111101001110100110000111000011101101110000111100101101001111011111011111101101110111111101001101111110110111001011101110110000111100111100001110100101011101110100110000111001001100001111001111010001101001010110011010111101111110111011011111100001111010011000011101001110100011000011101011110000111011101100001111001011000011111010111010111100111100101110100111100111110101111010111011101101001110111011000011110010111010111010111101111111010011011111100111110000111100111101000110111111101011101101110010111010011100100110010111010111101001111001011101010101110";
//		pr.println(s2.length());
//		for (int i = 0; i < s2.length(); i += 7) {
//			pr.print((char)Integer.parseInt(s2.substring(i, i + 7), 2));
//		}
//		pr.println();
		// Nchoutennnogurafugaaru.
		// n頂点のグラフがある
		// hajime,konogurafunihahennganai.
		// はじめ、このグラフには辺がない
		// konogurafuniN-1kaisousasuru.
		// このグラフにn-1回操作する
		// Ikaimenosousadeha[1,I]nohannideichiyourannsuuwomochiiteseisuuAwoseiseishi,choutennI+1tochoutennAnoaidanihennwotsuikasuru.
		// i回目の操作では[1,i]の範囲で一様乱数を用いて整数aを生成し、頂点i+1と頂点aの間に辺を追加する
		// sousagaowattaatonihakigadekiteiru.
		// 操作が終わった後には木ができている
		// kokode,kinosukoawo,2ijouNikanosubetenoseisuuJnitsuitenochoutenn1tochoutennJnokyorinosouwatoteigisuru.
		// ここで、木のスコアを2以上n以下のすべての整数jについての頂点1と頂点jの距離の総和と定義する
		// ranndamunikouseisarerukinosukoanokitaichiwoXtoshitatoki,N!Xwo10^9+7dewattaamariwomotomenasai.
		// ランダムに構成される木のスコアの期待値をxとしたとき、n!xを10^9+7で割った余りを求めなさい
		// tadashi,konoataihakanarazuseisuuninarukotogashoumeidekiru.
		// ただし、この値は必ず整数になることが証明できる

		PC pc = new PC(100_000, MOD);
		long[] xn = new long[100_000 + 1];
		long[] d = new long[100_000 + 1];
		long[] sumd = new long[100_000 + 1];
		d[1] = 0;

		for (int i = 2; i <= 100_000; i++) {
			d[i] = sumd[i - 1] + i - 1;
			d[i] *= pc.ifact[i] * pc.fact[i - 1] % MOD;
			d[i] %= MOD;
			sumd[i] = sumd[i - 1] + d[i];
			sumd[i] %= MOD;
			xn[i] = d[i] * i % MOD;
		}

		int t = sc.nextInt();
		for (int tcase = 0; tcase < t; tcase++) {
			if (tcase > 0) {
				pr.println();
			}

			long n = sc.nextInt();


			// Q1
			pr.println(n * n);

			// Q2
			long cnt1 = n * n * n - n;
			pr.println(cnt1 + n * n);

			// Q3
			pr.println(t);

			// Q4 7 -> 213(3*71) 13 -> 693(3^2*7*11) 18 -> 1313(13*101)
			pr.println(4 * n * n + 17);

			// Q5
			pr.println(modPow(n, n * n * n, MOD));

			// Q6
			pr.println(n);

			// Q7
			pr.println(xn[(int)n] * pc.fact[(int)n] % MOD);
		}
	}

	static long modPow(long a, long n, int MOD) {
		long loop = n;
		long ret = 1;
		long x = a % MOD;
		while (loop > 0) {
			if (loop % 2 == 1) {
				ret = ret * x % MOD;
			}
			x = x * x % MOD;
			loop /= 2;
		}

		return ret;
	}

    static class PC {
    	// MOD must be a prime number.
    	int MOD;
    	// fact[i] : i! % MOD
    	long[] fact;
    	// ifact[i] : 1/i! % MOD
    	long[] 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=7219428434016265740
    	private 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(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
		pr = new Printer(System.out);

		solve();

//		pr.close();
		pr.flush();
//		sc.close();
	}

	static String INPUT = null;

	private static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}
0