#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
実行時間	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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	140 ms 54,760 KB
testcase_01	AC	156 ms 54,996 KB
testcase_02	AC	155 ms 55,116 KB
testcase_03	AC	132 ms 54,248 KB
testcase_04	AC	161 ms 54,844 KB
testcase_05	AC	161 ms 55,132 KB
testcase_06	AC	156 ms 55,072 KB
testcase_07	AC	159 ms 55,048 KB
testcase_08	AC	133 ms 54,252 KB
testcase_09	AC	158 ms 55,080 KB
testcase_10	AC	155 ms 54,920 KB
testcase_11	AC	161 ms 54,888 KB
testcase_12	AC	159 ms 55,240 KB
testcase_13	AC	158 ms 54,964 KB
testcase_14	AC	160 ms 55,128 KB
testcase_15	AC	158 ms 55,128 KB
testcase_16	AC	158 ms 54,868 KB
testcase_17	AC	159 ms 55,128 KB
testcase_18	AC	156 ms 55,172 KB
testcase_19	AC	156 ms 55,120 KB
testcase_20	AC	153 ms 54,900 KB
testcase_21	AC	159 ms 55,104 KB
testcase_22	AC	155 ms 54,888 KB
testcase_23	AC	152 ms 54,816 KB
testcase_24	AC	143 ms 54,856 KB
testcase_25	AC	155 ms 54,888 KB
testcase_26	AC	156 ms 55,044 KB
testcase_27	AC	156 ms 54,964 KB
testcase_28	AC	154 ms 55,056 KB
testcase_29	AC	157 ms 54,840 KB
testcase_30	AC	155 ms 54,900 KB
testcase_31	AC	156 ms 54,984 KB
testcase_32	AC	155 ms 54,872 KB
testcase_33	AC	160 ms 54,872 KB
testcase_34	AC	155 ms 54,992 KB
testcase_35	AC	156 ms 54,904 KB
testcase_36	AC	155 ms 54,912 KB
testcase_37	AC	164 ms 55,068 KB
testcase_38	AC	156 ms 54,828 KB
testcase_39	AC	157 ms 54,868 KB
testcase_40	AC	156 ms 55,092 KB
testcase_41	AC	153 ms 55,072 KB
testcase_42	AC	153 ms 55,088 KB
testcase_43	AC	157 ms 55,068 KB
testcase_44	AC	156 ms 54,956 KB
testcase_45	AC	146 ms 54,520 KB
testcase_46	AC	155 ms 55,200 KB
testcase_47	AC	157 ms 55,020 KB
testcase_48	AC	141 ms 54,688 KB
testcase_49	AC	159 ms 54,832 KB
testcase_50	AC	157 ms 54,828 KB
testcase_51	AC	156 ms 55,200 KB
testcase_52	AC	153 ms 54,948 KB
testcase_53	AC	139 ms 54,616 KB
testcase_54	AC	155 ms 55,160 KB
testcase_55	AC	154 ms 54,900 KB
testcase_56	AC	141 ms 54,668 KB
testcase_57	AC	154 ms 54,952 KB
testcase_58	AC	155 ms 55,196 KB
testcase_59	AC	181 ms 55,416 KB
testcase_60	AC	190 ms 55,468 KB
testcase_61	AC	183 ms 55,436 KB
testcase_62	AC	183 ms 55,616 KB
testcase_63	AC	185 ms 55,540 KB
testcase_64	AC	185 ms 55,612 KB
testcase_65	AC	185 ms 55,596 KB
testcase_66	AC	185 ms 55,448 KB
testcase_67	AC	183 ms 55,452 KB
testcase_68	AC	181 ms 55,464 KB
testcase_69	AC	167 ms 55,212 KB
testcase_70	AC	187 ms 55,900 KB
testcase_71	AC	172 ms 54,896 KB
testcase_72	AC	169 ms 55,060 KB
testcase_73	AC	187 ms 55,512 KB
testcase_74	AC	186 ms 55,492 KB
testcase_75	AC	188 ms 55,516 KB
testcase_76	AC	168 ms 54,936 KB
testcase_77	AC	187 ms 55,348 KB
testcase_78	AC	185 ms 55,596 KB
testcase_79	AC	169 ms 54,908 KB
testcase_80	AC	183 ms 55,728 KB
testcase_81	AC	187 ms 55,604 KB
testcase_82	AC	186 ms 55,544 KB
testcase_83	AC	167 ms 55,028 KB
testcase_84	AC	166 ms 55,008 KB
testcase_85	AC	190 ms 55,912 KB
testcase_86	AC	184 ms 55,612 KB
testcase_87	AC	181 ms 55,896 KB
testcase_88	AC	172 ms 56,044 KB
testcase_89	AC	169 ms 55,020 KB
testcase_90	AC	190 ms 55,788 KB
testcase_91	AC	192 ms 55,968 KB
testcase_92	AC	171 ms 55,196 KB
testcase_93	AC	169 ms 55,072 KB
testcase_94	AC	168 ms 54,980 KB
testcase_95	AC	171 ms 55,176 KB
testcase_96	AC	169 ms 55,076 KB
testcase_97	AC	188 ms 55,736 KB
testcase_98	AC	188 ms 55,796 KB
testcase_99	AC	186 ms 55,400 KB
testcase_100	AC	189 ms 55,488 KB
testcase_101	AC	186 ms 55,732 KB
testcase_102	AC	169 ms 55,328 KB
testcase_103	AC	185 ms 55,360 KB
testcase_104	AC	167 ms 55,164 KB
testcase_105	AC	166 ms 55,204 KB
testcase_106	AC	188 ms 55,936 KB
testcase_107	AC	169 ms 55,840 KB
testcase_108	AC	171 ms 55,264 KB
testcase_109	AC	185 ms 55,772 KB
testcase_110	AC	186 ms 55,708 KB
testcase_111	AC	190 ms 55,692 KB
testcase_112	AC	158 ms 54,984 KB
testcase_113	AC	193 ms 55,620 KB
testcase_114	AC	179 ms 55,256 KB
testcase_115	AC	155 ms 54,804 KB
testcase_116	AC	187 ms 55,472 KB
testcase_117	AC	185 ms 55,544 KB
testcase_118	AC	187 ms 55,612 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

結果

テストケース

ソースコード