結果
| 問題 | No.8034 7 problems |
| ユーザー |
 Grenache
|
| 提出日時 | 2018-04-02 20:13:11 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 435 ms / 2,000 ms |
| コード長 | 10,315 bytes |
| コンパイル時間 | 3,895 ms |
| コンパイル使用メモリ | 79,708 KB |
| 実行使用メモリ | 50,132 KB |
| 最終ジャッジ日時 | 2024-06-26 06:43:44 |
| 合計ジャッジ時間 | 24,683 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 51 |
ソースコード
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();// Q1pr.println(n * n);// Q2long cnt1 = n * n * n - n;pr.println(cnt1 + n * n);// Q3pr.println(t);// Q4 7 -> 213(3*71) 13 -> 693(3^2*7*11) 18 -> 1313(13*101)pr.println(4 * n * n + 17);// Q5pr.println(modPow(n, n * n * n, MOD));// Q6pr.println(n);// Q7pr.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! % 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(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);}}}