結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー 37zigen
提出日時 2017-03-11 05:01:43
言語 Java
(openjdk 23)
結果
AC  
実行時間 193 ms / 800 ms
コード長 3,302 bytes
コンパイル時間 2,338 ms
コンパイル使用メモリ 84,452 KB
実行使用メモリ 56,044 KB
最終ジャッジ日時 2024-06-24 11:58:11
合計ジャッジ時間 25,260 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 115
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        new Main().run();
    }
    static long MODULO = 1_000_000_000L + 7;
    static int[] ref = { 10, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    static long[] pow10 = { 1, 10, 100, 1000, 10000 };
    void run() {
        Scanner sc = new Scanner(System.in);
        long K = sc.nextLong();
        long L = sc.nextLong();
        long R = sc.nextLong();
        K = Math.min(K, 60);
        --K;
        if (getFullLen(K) < R) {
            System.out.println(-1);
            return;
        }
        long[] leftCnt = solve(K, L - 1);
        long[] rightCnt = solve(K, R);
        long sum = sum(rightCnt, leftCnt);
        while (sum < 0)
            sum += MODULO;
        long prd = prd(rightCnt, leftCnt);
        System.out.println(sum + " " + prd);
    }
    long sum(long[] arrR, long[] arrL) {
        long ret = 0;
        for (int i = 0; i < 10; ++i) {
            ret = (ret + ref[i] * (arrR[i] - arrL[i]));
            if (arrR[i] < arrL[i])
                throw new AssertionError(arrR[i] + " " + arrL[i] + " " + i);
        }
        return ret;
    }
    long prd(long[] arrR, long[] arrL) {
        long ret = 1;
        for (int i = 0; i < 10; ++i) {
            ret = (ret * pow(ref[i], arrR[i] - arrL[i])) % MODULO;
        }
        return ret;
    }
    long[] solve(long K, long len) {
        if (len == 0)
            return new long[10];
        long left = 0;
        long right = 1L << 60;
        while (right - left > 1) {
            long middle = (right + left) / 2;
            if (getLen(middle, K) > len) {
                right = middle;
            } else {
                left = middle;
            }
        }
        long res = len - getLen(left, K);
        long[] cnt = cnt(left, K);
        long v = -1;
        for (int i = 0; i <= 60; ++i) {
            if ((right + (1L << i) + 1) % (1L << (i + 1)) == 0) {
                v = (i + 1) * (i + 1);
                break;
            }
        }
        if (v == -1)
            throw new AssertionError();
        while (res > 0) {
            int l = String.valueOf(v).length();
            ++cnt[(int) (v / pow10[l - 1])];
            v %= pow10[l - 1];
            --res;
        }
        return cnt;
    }
    long[] cnt(long left, long K) {
        long[] ret = new long[10];
        for (int i = 0; i <= K; ++i) {
            long v = (left + (1L << i) + 1) / (1L << (i + 1));
            long cur = (i + 1) * (i + 1);
            while (cur > 0) {
                ret[(int) (cur % 10)] = (ret[(int) (cur % 10)] + v);
                cur /= 10;
            }
        }
        return ret;
    }
    long getLen(long pos, long K) {
        long len = 0;
        for (int i = 0; i <= K; ++i) {
            long v = (pos + (1L << i) + 1) / (1L << (i + 1));
            len += String.valueOf((i + 1) * (i + 1)).length() * v;
        }
        return len;
    }
    long getFullLen(long K) {
        long len = 0;
        for (int i = 0; i <= K; ++i) {
            len = 2 * len + String.valueOf((i + 1) * (i + 1)).length();
        }
        return len;
    }
    // ax+b(mo)=V
    // x+0*mo=x
    // 0*x+1*mo=mo;
    long inv(long x, long mo) {
        x %= mo;
        long curA = 1;
        long curB = 0;
        long preA = 0;
        long preB = 1;
        long curV = x;
        long preV = mo;
        while (curV != 1) {
            long q = preV / curV;
            preA -= q * curA;
            preB -= q * curB;
            preV -= q * curV;
            long tmp = curV;
            curV = preV;
            preV = tmp;
            tmp = curA;
            curA = preA;
            preA = tmp;
            tmp = curB;
            curB = preB;
            preB = tmp;
        }
        while (curA < 0)
            curA += mo;
        return curA;
    }
    long pow(long a, long n) {
        long ret = 1;
        a %= MODULO;
        for (; n > 0; n >>= 1, a = (a * a) % MODULO) {
            if (n % 2 == 1) {
                ret = (ret * a) % MODULO;
            }
        }
        return ret;
    }
    static void tr(Object... objects) {
        System.out.println(Arrays.deepToString(objects));
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0