結果

問題 No.681 Fractal Gravity Glue
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-11-06 20:36:34
言語 Java21
(openjdk 21)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 2,919 bytes
コンパイル時間 3,378 ms
コンパイル使用メモリ 78,168 KB
実行使用メモリ 41,428 KB
最終ジャッジ日時 2024-05-03 06:21:31
合計ジャッジ時間 5,787 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 111 ms
40,052 KB
testcase_01 AC 109 ms
39,880 KB
testcase_02 AC 123 ms
41,120 KB
testcase_03 AC 126 ms
41,224 KB
testcase_04 AC 127 ms
40,968 KB
testcase_05 AC 129 ms
41,356 KB
testcase_06 AC 127 ms
41,260 KB
testcase_07 AC 128 ms
41,184 KB
testcase_08 AC 127 ms
41,428 KB
testcase_09 AC 126 ms
41,252 KB
testcase_10 AC 124 ms
41,300 KB
testcase_11 AC 111 ms
39,820 KB
testcase_12 AC 128 ms
41,288 KB
testcase_13 AC 111 ms
40,032 KB
testcase_14 AC 126 ms
40,904 KB
testcase_15 AC 110 ms
40,048 KB
testcase_16 AC 122 ms
41,200 KB
testcase_17 AC 131 ms
41,072 KB
testcase_18 AC 125 ms
40,948 KB
testcase_19 AC 115 ms
39,952 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