結果
| 問題 |
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();
// 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);
}
}
}