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

提出ソース

結果

問題	No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー	37zigen
提出日時	2017-03-11 04:25:21
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	3,179 bytes
コンパイル時間	2,430 ms
コンパイル使用メモリ	81,424 KB
実行使用メモリ	60,444 KB
最終ジャッジ日時	2023-09-06 17:30:23
合計ジャッジ時間	26,462 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	162 ms 40,604 KB
testcase_01	AC	188 ms 41,816 KB
testcase_02	AC	187 ms 41,116 KB
testcase_03	AC	130 ms 39,100 KB
testcase_04	AC	186 ms 41,168 KB
testcase_05	AC	185 ms 41,852 KB
testcase_06	AC	189 ms 40,924 KB
testcase_07	AC	186 ms 41,044 KB
testcase_08	AC	127 ms 39,188 KB
testcase_09	AC	184 ms 41,032 KB
testcase_10	AC	186 ms 41,100 KB
testcase_11	AC	187 ms 41,092 KB
testcase_12	WA	-
testcase_13	AC	185 ms 41,224 KB
testcase_14	AC	184 ms 40,928 KB
testcase_15	AC	183 ms 42,228 KB
testcase_16	AC	184 ms 41,388 KB
testcase_17	AC	184 ms 41,272 KB
testcase_18	WA	-
testcase_19	AC	183 ms 41,272 KB
testcase_20	AC	184 ms 41,004 KB
testcase_21	AC	184 ms 42,284 KB
testcase_22	WA	-
testcase_23	AC	184 ms 41,672 KB
testcase_24	AC	187 ms 41,280 KB
testcase_25	WA	-
testcase_26	AC	185 ms 41,480 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	184 ms 41,568 KB
testcase_31	WA	-
testcase_32	AC	184 ms 41,048 KB
testcase_33	WA	-
testcase_34	AC	186 ms 41,924 KB
testcase_35	WA	-
testcase_36	AC	185 ms 41,396 KB
testcase_37	AC	186 ms 41,224 KB
testcase_38	AC	188 ms 42,024 KB
testcase_39	AC	184 ms 42,152 KB
testcase_40	AC	185 ms 41,748 KB
testcase_41	AC	195 ms 42,004 KB
testcase_42	AC	185 ms 41,740 KB
testcase_43	AC	186 ms 42,060 KB
testcase_44	WA	-
testcase_45	AC	185 ms 42,312 KB
testcase_46	AC	186 ms 40,936 KB
testcase_47	AC	188 ms 41,024 KB
testcase_48	WA	-
testcase_49	AC	187 ms 42,048 KB
testcase_50	AC	184 ms 41,648 KB
testcase_51	AC	184 ms 42,100 KB
testcase_52	AC	186 ms 41,688 KB
testcase_53	AC	184 ms 41,780 KB
testcase_54	WA	-
testcase_55	AC	186 ms 41,948 KB
testcase_56	WA	-
testcase_57	WA	-
testcase_58	AC	186 ms 41,848 KB
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	WA	-
testcase_84	WA	-
testcase_85	WA	-
testcase_86	WA	-
testcase_87	WA	-
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	WA	-
testcase_93	WA	-
testcase_94	WA	-
testcase_95	WA	-
testcase_96	WA	-
testcase_97	WA	-
testcase_98	WA	-
testcase_99	WA	-
testcase_100	WA	-
testcase_101	WA	-
testcase_102	WA	-
testcase_103	WA	-
testcase_104	WA	-
testcase_105	WA	-
testcase_106	WA	-
testcase_107	WA	-
testcase_108	WA	-
testcase_109	WA	-
testcase_110	WA	-
testcase_111	WA	-
testcase_112	WA	-
testcase_113	WA	-
testcase_114	AC	186 ms 41,688 KB
testcase_115	AC	157 ms 40,796 KB
testcase_116	AC	189 ms 41,884 KB
testcase_117	AC	183 ms 41,608 KB
testcase_118	AC	192 ms 41,648 KB

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

ソースコード

raw source code

import java.util.Arrays;
import java.util.Scanner;
import java.util.concurrent.SynchronousQueue;
import java.math.*;

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) - sum(leftCnt);
		long prd = prd(rightCnt) * inv(prd(leftCnt), MODULO) % MODULO;
		System.out.println(sum + " " + prd);
	}

	long sum(long[] arr) {
		long ret = 0;
		for (int i = 0; i < arr.length; ++i) {
			ret = (ret + ref[i] * arr[i]) % MODULO;
		}
		return ret;
	}

	long prd(long[] arr) {
		long ret = 1;
		for (int i = 0; i < arr.length; ++i) {
			ret = (ret * pow(ref[i], arr[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) > len) {
				right = middle;
			} else {
				left = middle;
			}
		}
		long res = len - getLen(left);
		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)] += v;
				cur /= 10;
			}
		}
		return ret;
	}

	long getLen(long pos) {
		long len = 0;
		for (int i = 0; i <= 60; ++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).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;
		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

結果

テストケース

ソースコード