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

提出ソース

結果

問題	No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー	はまやんはまやん
提出日時	2017-03-11 01:25:32
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 800 ms
コード長	2,882 bytes
コンパイル時間	1,829 ms
コンパイル使用メモリ	168,860 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-24 09:28:18
合計ジャッジ時間	4,439 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

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

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

ソースコード

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

結果

テストケース

ソースコード