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

提出ソース

結果

問題	No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー	37zigen
提出日時	2017-03-11 04:29:20
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	3,195 bytes
コンパイル時間	2,368 ms
コンパイル使用メモリ	83,984 KB
実行使用メモリ	58,116 KB
最終ジャッジ日時	2024-06-24 11:57:31
合計ジャッジ時間	27,164 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	159 ms 54,948 KB
testcase_01	AC	187 ms 55,660 KB
testcase_02	AC	190 ms 55,992 KB
testcase_03	AC	129 ms 54,132 KB
testcase_04	AC	186 ms 55,468 KB
testcase_05	AC	187 ms 55,456 KB
testcase_06	AC	170 ms 55,120 KB
testcase_07	AC	185 ms 55,624 KB
testcase_08	AC	130 ms 54,076 KB
testcase_09	AC	185 ms 55,416 KB
testcase_10	AC	188 ms 55,448 KB
testcase_11	AC	180 ms 55,816 KB
testcase_12	AC	189 ms 55,688 KB
testcase_13	AC	184 ms 55,488 KB
testcase_14	AC	187 ms 55,436 KB
testcase_15	AC	188 ms 55,424 KB
testcase_16	AC	187 ms 55,584 KB
testcase_17	AC	187 ms 55,484 KB
testcase_18	AC	184 ms 55,244 KB
testcase_19	AC	185 ms 55,564 KB
testcase_20	AC	188 ms 55,768 KB
testcase_21	AC	187 ms 55,532 KB
testcase_22	AC	188 ms 55,676 KB
testcase_23	AC	167 ms 55,804 KB
testcase_24	AC	170 ms 55,184 KB
testcase_25	AC	190 ms 55,624 KB
testcase_26	AC	186 ms 55,828 KB
testcase_27	AC	185 ms 55,560 KB
testcase_28	AC	184 ms 55,404 KB
testcase_29	AC	185 ms 55,508 KB
testcase_30	AC	184 ms 55,272 KB
testcase_31	AC	185 ms 55,444 KB
testcase_32	AC	186 ms 55,292 KB
testcase_33	AC	182 ms 55,420 KB
testcase_34	AC	180 ms 55,424 KB
testcase_35	AC	188 ms 55,528 KB
testcase_36	AC	190 ms 56,008 KB
testcase_37	AC	166 ms 55,280 KB
testcase_38	AC	184 ms 55,324 KB
testcase_39	AC	185 ms 55,580 KB
testcase_40	AC	187 ms 55,432 KB
testcase_41	AC	185 ms 55,368 KB
testcase_42	AC	187 ms 55,296 KB
testcase_43	AC	183 ms 55,340 KB
testcase_44	AC	185 ms 55,376 KB
testcase_45	AC	187 ms 55,712 KB
testcase_46	AC	184 ms 55,416 KB
testcase_47	AC	186 ms 55,324 KB
testcase_48	AC	184 ms 55,468 KB
testcase_49	AC	187 ms 55,332 KB
testcase_50	AC	186 ms 55,360 KB
testcase_51	AC	185 ms 55,572 KB
testcase_52	AC	167 ms 55,080 KB
testcase_53	AC	184 ms 55,368 KB
testcase_54	AC	215 ms 55,404 KB
testcase_55	AC	194 ms 55,312 KB
testcase_56	AC	186 ms 55,500 KB
testcase_57	AC	183 ms 55,400 KB
testcase_58	AC	188 ms 55,768 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	188 ms 55,784 KB
testcase_115	AC	158 ms 55,252 KB
testcase_116	AC	182 ms 55,636 KB
testcase_117	AC	185 ms 55,408 KB
testcase_118	AC	182 ms 55,368 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 + 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;
		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

結果

テストケース

ソースコード