結果

問題 No.681 Fractal Gravity Glue
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-11-06 20:36:34
言語 Java
(openjdk 23)
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 2,919 bytes
コンパイル時間 2,143 ms
コンパイル使用メモリ 78,300 KB
実行使用メモリ 41,472 KB
最終ジャッジ日時 2024-11-24 04:04:26
合計ジャッジ時間 5,477 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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