#157247 (Java21) No.493 とても長い数列と文字列(Long Long Sequence and a String）

提出ソース

結果

問題	No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー	37zigen
提出日時	2017-03-11 05:01:43
言語	Java21 (openjdk 21)
結果	AC
実行時間	195 ms / 800 ms
コード長	3,302 bytes
コンパイル時間	4,005 ms
コンパイル使用メモリ	82,224 KB
実行使用メモリ	42,380 KB
最終ジャッジ日時	2023-09-06 17:31:38
合計ジャッジ時間	29,341 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	150 ms 40,420 KB
testcase_01	AC	151 ms 40,672 KB
testcase_02	AC	153 ms 40,476 KB
testcase_03	AC	124 ms 39,300 KB
testcase_04	AC	152 ms 40,496 KB
testcase_05	AC	155 ms 40,272 KB
testcase_06	AC	157 ms 40,856 KB
testcase_07	AC	155 ms 40,644 KB
testcase_08	AC	125 ms 39,648 KB
testcase_09	AC	153 ms 40,924 KB
testcase_10	AC	157 ms 40,624 KB
testcase_11	AC	160 ms 40,756 KB
testcase_12	AC	157 ms 40,480 KB
testcase_13	AC	156 ms 40,608 KB
testcase_14	AC	156 ms 40,716 KB
testcase_15	AC	157 ms 40,884 KB
testcase_16	AC	157 ms 40,888 KB
testcase_17	AC	156 ms 40,844 KB
testcase_18	AC	156 ms 41,120 KB
testcase_19	AC	157 ms 40,536 KB
testcase_20	AC	156 ms 40,804 KB
testcase_21	AC	154 ms 40,364 KB
testcase_22	AC	159 ms 40,748 KB
testcase_23	AC	154 ms 40,416 KB
testcase_24	AC	155 ms 40,840 KB
testcase_25	AC	159 ms 40,864 KB
testcase_26	AC	158 ms 40,880 KB
testcase_27	AC	159 ms 40,436 KB
testcase_28	AC	157 ms 41,112 KB
testcase_29	AC	158 ms 40,532 KB
testcase_30	AC	157 ms 41,108 KB
testcase_31	AC	159 ms 40,952 KB
testcase_32	AC	158 ms 40,524 KB
testcase_33	AC	159 ms 40,580 KB
testcase_34	AC	157 ms 40,884 KB
testcase_35	AC	160 ms 40,880 KB
testcase_36	AC	157 ms 40,496 KB
testcase_37	AC	158 ms 40,804 KB
testcase_38	AC	158 ms 40,624 KB
testcase_39	AC	157 ms 40,780 KB
testcase_40	AC	157 ms 40,536 KB
testcase_41	AC	159 ms 40,656 KB
testcase_42	AC	159 ms 40,544 KB
testcase_43	AC	159 ms 40,852 KB
testcase_44	AC	161 ms 40,760 KB
testcase_45	AC	159 ms 40,608 KB
testcase_46	AC	160 ms 40,896 KB
testcase_47	AC	159 ms 40,896 KB
testcase_48	AC	159 ms 40,408 KB
testcase_49	AC	159 ms 40,652 KB
testcase_50	AC	159 ms 40,552 KB
testcase_51	AC	163 ms 40,640 KB
testcase_52	AC	160 ms 40,980 KB
testcase_53	AC	159 ms 41,096 KB
testcase_54	AC	161 ms 40,396 KB
testcase_55	AC	158 ms 40,892 KB
testcase_56	AC	162 ms 40,968 KB
testcase_57	AC	158 ms 40,652 KB
testcase_58	AC	159 ms 40,428 KB
testcase_59	AC	186 ms 41,132 KB
testcase_60	AC	188 ms 41,612 KB
testcase_61	AC	186 ms 41,024 KB
testcase_62	AC	185 ms 41,208 KB
testcase_63	AC	188 ms 41,544 KB
testcase_64	AC	191 ms 41,364 KB
testcase_65	AC	186 ms 41,316 KB
testcase_66	AC	191 ms 41,692 KB
testcase_67	AC	190 ms 41,076 KB
testcase_68	AC	187 ms 41,872 KB
testcase_69	AC	187 ms 42,108 KB
testcase_70	AC	193 ms 41,988 KB
testcase_71	AC	186 ms 41,692 KB
testcase_72	AC	191 ms 41,244 KB
testcase_73	AC	189 ms 42,048 KB
testcase_74	AC	194 ms 41,956 KB
testcase_75	AC	179 ms 41,788 KB
testcase_76	AC	194 ms 40,868 KB
testcase_77	AC	181 ms 42,240 KB
testcase_78	AC	194 ms 42,144 KB
testcase_79	AC	183 ms 42,224 KB
testcase_80	AC	187 ms 41,128 KB
testcase_81	AC	188 ms 41,224 KB
testcase_82	AC	186 ms 40,972 KB
testcase_83	AC	195 ms 41,760 KB
testcase_84	AC	186 ms 41,788 KB
testcase_85	AC	186 ms 42,380 KB
testcase_86	AC	187 ms 41,536 KB
testcase_87	AC	188 ms 41,924 KB
testcase_88	AC	185 ms 41,728 KB
testcase_89	AC	178 ms 41,684 KB
testcase_90	AC	194 ms 41,648 KB
testcase_91	AC	192 ms 41,964 KB
testcase_92	AC	180 ms 41,888 KB
testcase_93	AC	181 ms 40,972 KB
testcase_94	AC	194 ms 40,760 KB
testcase_95	AC	194 ms 41,464 KB
testcase_96	AC	194 ms 42,136 KB
testcase_97	AC	194 ms 41,944 KB
testcase_98	AC	194 ms 41,184 KB
testcase_99	AC	182 ms 42,004 KB
testcase_100	AC	194 ms 42,052 KB
testcase_101	AC	193 ms 42,096 KB
testcase_102	AC	181 ms 41,936 KB
testcase_103	AC	192 ms 40,760 KB
testcase_104	AC	190 ms 41,720 KB
testcase_105	AC	184 ms 41,068 KB
testcase_106	AC	186 ms 41,812 KB
testcase_107	AC	194 ms 41,500 KB
testcase_108	AC	189 ms 40,936 KB
testcase_109	AC	189 ms 41,880 KB
testcase_110	AC	193 ms 41,904 KB
testcase_111	AC	191 ms 41,636 KB
testcase_112	AC	156 ms 40,844 KB
testcase_113	AC	183 ms 41,852 KB
testcase_114	AC	185 ms 41,444 KB
testcase_115	AC	161 ms 40,684 KB
testcase_116	AC	186 ms 41,844 KB
testcase_117	AC	185 ms 41,820 KB
testcase_118	AC	190 ms 41,216 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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));
	}

}

yukicoder

結果

テストケース

ソースコード