#157164 (C++14) No.493 とても長い数列と文字列(Long Long Sequence and a String）

提出ソース

結果

問題	No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー	👑 はまやんはまやん
提出日時	2017-03-11 01:00:46
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	2,880 bytes
コンパイル時間	1,525 ms
コンパイル使用メモリ	166,596 KB
実行使用メモリ	5,256 KB
最終ジャッジ日時	2023-09-06 14:59:09
合計ジャッジ時間	4,318 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	1 ms 4,376 KB
testcase_09	WA	-
testcase_10	AC	1 ms 4,376 KB
testcase_11	AC	1 ms 4,376 KB
testcase_12	AC	1 ms 4,376 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	WA	-
testcase_20	AC	1 ms 4,376 KB
testcase_21	AC	1 ms 4,380 KB
testcase_22	AC	2 ms 4,376 KB
testcase_23	WA	-
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	1 ms 4,380 KB
testcase_26	WA	-
testcase_27	AC	2 ms 4,376 KB
testcase_28	AC	1 ms 4,376 KB
testcase_29	AC	1 ms 4,376 KB
testcase_30	AC	1 ms 4,380 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	1 ms 4,376 KB
testcase_33	AC	2 ms 4,376 KB
testcase_34	AC	2 ms 4,376 KB
testcase_35	AC	1 ms 4,376 KB
testcase_36	AC	1 ms 4,380 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	1 ms 4,376 KB
testcase_39	AC	1 ms 4,376 KB
testcase_40	AC	1 ms 4,380 KB
testcase_41	AC	1 ms 4,376 KB
testcase_42	AC	2 ms 4,380 KB
testcase_43	AC	1 ms 4,376 KB
testcase_44	AC	1 ms 4,380 KB
testcase_45	WA	-
testcase_46	AC	1 ms 4,376 KB
testcase_47	AC	2 ms 4,376 KB
testcase_48	AC	2 ms 4,376 KB
testcase_49	AC	1 ms 4,380 KB
testcase_50	AC	1 ms 4,376 KB
testcase_51	WA	-
testcase_52	WA	-
testcase_53	AC	1 ms 4,376 KB
testcase_54	AC	2 ms 4,380 KB
testcase_55	AC	1 ms 4,376 KB
testcase_56	AC	1 ms 4,380 KB
testcase_57	AC	1 ms 4,376 KB
testcase_58	AC	1 ms 4,376 KB
testcase_59	AC	1 ms 4,376 KB
testcase_60	AC	1 ms 4,376 KB
testcase_61	WA	-
testcase_62	AC	1 ms 4,380 KB
testcase_63	AC	1 ms 4,376 KB
testcase_64	AC	1 ms 4,376 KB
testcase_65	AC	1 ms 4,376 KB
testcase_66	WA	-
testcase_67	WA	-
testcase_68	AC	1 ms 4,376 KB
testcase_69	AC	1 ms 4,380 KB
testcase_70	AC	1 ms 4,380 KB
testcase_71	AC	1 ms 4,376 KB
testcase_72	AC	2 ms 4,376 KB
testcase_73	AC	1 ms 4,376 KB
testcase_74	WA	-
testcase_75	AC	2 ms 4,376 KB
testcase_76	WA	-
testcase_77	WA	-
testcase_78	AC	1 ms 4,380 KB
testcase_79	AC	1 ms 4,376 KB
testcase_80	AC	1 ms 4,380 KB
testcase_81	WA	-
testcase_82	AC	1 ms 4,380 KB
testcase_83	AC	2 ms 4,376 KB
testcase_84	AC	1 ms 4,380 KB
testcase_85	AC	1 ms 4,380 KB
testcase_86	AC	1 ms 4,380 KB
testcase_87	AC	1 ms 4,376 KB
testcase_88	AC	1 ms 4,380 KB
testcase_89	AC	1 ms 4,380 KB
testcase_90	AC	1 ms 4,376 KB
testcase_91	AC	1 ms 4,380 KB
testcase_92	WA	-
testcase_93	AC	1 ms 4,380 KB
testcase_94	AC	1 ms 4,380 KB
testcase_95	AC	1 ms 4,380 KB
testcase_96	WA	-
testcase_97	AC	1 ms 4,380 KB
testcase_98	AC	1 ms 4,376 KB
testcase_99	AC	1 ms 4,380 KB
testcase_100	WA	-
testcase_101	AC	2 ms 4,376 KB
testcase_102	AC	1 ms 4,376 KB
testcase_103	WA	-
testcase_104	AC	1 ms 4,376 KB
testcase_105	AC	2 ms 4,380 KB
testcase_106	WA	-
testcase_107	AC	2 ms 4,376 KB
testcase_108	WA	-
testcase_109	AC	1 ms 4,380 KB
testcase_110	AC	1 ms 4,376 KB
testcase_111	AC	1 ms 4,380 KB
testcase_112	AC	1 ms 4,380 KB
testcase_113	AC	1 ms 4,376 KB
testcase_114	AC	1 ms 4,376 KB
testcase_115	AC	1 ms 4,376 KB
testcase_116	AC	1 ms 4,376 KB
testcase_117	AC	1 ms 4,376 KB
testcase_118	WA	-

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

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
int sub(int x, int y) { return add(x, mod - y); }
int modpow(int a, long long b) {
	int ret = 1;
	while (b > 0) {
		if (b & 1) ret = 1LL * ret * a % mod;
		a = 1LL * a * a % mod; b >>= 1;
	}
	return ret;
}
int modinv(int a) { return modpow(a, mod - 2); }
//-----------------------------------------------------------------
ll K, L, R;
//-----------------------------------------------------------------
ll sz[63], sm[63];
int mu[63];
void pre() {
	sz[0] = 0;
	rep(i, 1, 63) {
		int c = 0;
		int ii = i * i;
		while (0 < ii) c++, ii /= 10;
		sz[i] = 2 * sz[i - 1] + c;
	}

	sm[0] = 0;
	rep(i, 1, 63) {
		ll c = 0;
		int ii = i * i;
		while (0 < ii) {
			if (ii % 10 == 0) c += 10;
			else c += ii % 10;
			ii /= 10;
		}
		sm[i] = 2 * sm[i - 1] + c;
	}

	mu[0] = 1;
	rep(i, 1, 63) {
		int c = 1;
		int ii = i * i;
		while (0 < ii) {
			if (ii % 10 == 0) c = mul(c, 10);
			else c = mul(c, ii % 10);
			ii /= 10;
		}
		mu[i] = mul(mu[i - 1], mu[i - 1], c);
	}

	//rep(i, 0, 63) printf("%d -> %lld\n", i, sz[i]);
}
//-----------------------------------------------------------------
ll calcSum(int K, ll x) {
	if (x == 0) return 0;
	if (x <= sz[K - 1]) return calcSum(K - 1, x);

	ll s = sz[K] - sz[K - 1];
	string kk = to_string(K * K);

	if (x <= s) {
		ll ret = sm[K - 1];
		x -= sz[K - 1];

		int ki = 0;
		while (0 < x) {
			if (kk[ki] == '0') ret += 10;
			else ret += kk[ki] - '0';
			x--; ki--;
		}
		return ret;
	}

	ll ret = sm[K - 1];
	rep(i, 0, kk.length()) {
		if (kk[i] == '0') ret += 10;
		else ret += kk[i] - '0';
	}
	return ret + calcSum(K - 1, x - s);
}
//-----------------------------------------------------------------
ll calcMul(int K, ll x) {
	if (x == 0) return 1;
	if (x <= sz[K - 1]) return calcMul(K - 1, x);

	ll s = sz[K] - sz[K - 1];
	string kk = to_string(K * K);

	if (x <= s) {
		ll ret = mu[K - 1];
		x -= sz[K - 1];

		int ki = 0;
		while (0 < x) {
			if(kk[ki] == '0') ret = mul(ret, 10);
			else ret = mul(ret, kk[ki] - '0');
			x--; ki--;
		}
		return ret;
	}

	ll ret = mu[K - 1];
	rep(i, 0, kk.length()) {
		if(kk[i] == '0') ret = mul(ret, 10);
		else ret = mul(ret, kk[i] - '0');
	}
	return mul(ret, (int)calcMul(K - 1, x - s));
}
//-----------------------------------------------------------------
int main() {
	pre();

	cin >> K >> L >> R;

	if (63 <= K) K = 62;
	if (sz[K] < R) {
		printf("-1\n");
		return 0;
	}

	ll a = calcSum(K, R) - calcSum(K, L - 1);
	ll b = mul(calcMul(K, R), modinv(calcMul(K, L - 1)));
	printf("%lld %lld\n", a, b);
}

yukicoder

結果

テストケース

ソースコード