結果

問題 No.681 Fractal Gravity Glue
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-11-06 20:36:34
言語 Java21
(openjdk 21)
結果
AC  
実行時間 119 ms / 2,000 ms
コード長 2,919 bytes
コンパイル時間 3,549 ms
コンパイル使用メモリ 74,528 KB
実行使用メモリ 56,304 KB
最終ジャッジ日時 2023-08-15 19:37:11
合計ジャッジ時間 7,058 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 119 ms
55,788 KB
testcase_01 AC 118 ms
55,536 KB
testcase_02 AC 119 ms
56,044 KB
testcase_03 AC 119 ms
55,708 KB
testcase_04 AC 118 ms
55,744 KB
testcase_05 AC 118 ms
55,708 KB
testcase_06 AC 118 ms
55,500 KB
testcase_07 AC 119 ms
55,924 KB
testcase_08 AC 118 ms
55,544 KB
testcase_09 AC 117 ms
55,572 KB
testcase_10 AC 117 ms
55,768 KB
testcase_11 AC 117 ms
55,716 KB
testcase_12 AC 117 ms
55,724 KB
testcase_13 AC 116 ms
55,720 KB
testcase_14 AC 117 ms
56,288 KB
testcase_15 AC 116 ms
55,296 KB
testcase_16 AC 117 ms
55,564 KB
testcase_17 AC 116 ms
55,584 KB
testcase_18 AC 117 ms
55,664 KB
testcase_19 AC 117 ms
56,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

class Main {
    static final long MOD = 1000000007;
    static final long INFINITY = (1L << 62) - 1;
    static void myAssert(boolean condition) {
        if (!condition) {
            throw new RuntimeException("assert ga mitasarete nai");
        }
    }
    static long limitedPower(long x, long exponent) {
        if (x < 0 || exponent < 0) {
            throw new RuntimeException();
        }
        if (x == 1) {
            return 1;
        }
        if (x == 0) {
            return exponent == 0 ? 1 : 0;
        }
        if (exponent == 0) {
            return 1;
        }
        if (x >= INFINITY || exponent >= 100) {
            return INFINITY;
        }
        long limit = INFINITY / x;
        long prod = 1;
        for (int i = 0; i < exponent; ++i) {
            if (prod > limit) {
                return INFINITY;
            }
            prod *= x;
        }
        return prod;
    }
    static long powerMod(long x, long exponent) {
	long prod = 1;
	for (int i = 63; i >= 0; --i) {
	    prod = (prod * prod) % MOD;
	    if ((exponent & 1L << i) != 0) {
		prod = (prod * x) % MOD;
	    }
	}
	return prod;
    }
    static long height(int b, int d) {
        return (powerMod(d + 1, b) + MOD - 1) % MOD;
    }
    static long limitedHeight(int b, int d) {
        return limitedPower(d + 1, b) - 1;
    }
    static long wholeSize(int b, int d) {
        long temp = powerMod(d + 1, b) + MOD - 1;
        temp %= MOD;
        temp = (temp * (d + 1)) % MOD;
        temp = (temp * powerMod(d, MOD - 2)) % MOD;
        temp = (temp + MOD - b) % MOD;
        return temp;
    }
    static long nthSizeSub(int b, int d, long n) {
        myAssert(n <= limitedHeight(b, d));
        if (n == 0) {
            return 0;
        }
        long prevHeight = limitedHeight(b - 1, d);
        long temp = n / (prevHeight + 1);
        long total = (wholeSize(b - 1, d) + b) * temp % MOD;
        long remainder = n % (prevHeight + 1);
        return total + nthSizeSub(b - 1, d, remainder);
    }
    static long nthSize(int b, int d, int n) {
        // n <= limitedHeight(k, d) to naru youna saisyouno k wo mitukeru
        int k = 0;
        while (true) {
            if (n <= limitedHeight(k, d)) {
                break;
            }
            k++;
        }
        assert (k <= b);
        return nthSizeSub(k, d, n);
    }
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.next());
        int b = Integer.parseInt(scan.next());
        int d = Integer.parseInt(scan.next());
        myAssert(0 <= n);
        myAssert(n <= 1000000000);
        myAssert(1 <= b);
        myAssert(b <= 1000000000);
        myAssert(1 <= d);
        myAssert(d <= 1000000000);
        myAssert(n <= limitedHeight(b, d));
        System.out.println((wholeSize(b, d) - nthSize(b, d, n) + MOD) % MOD);
    }
}
0