結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー 👑 はまやんはまやんはまやんはまやん
提出日時 2017-03-11 01:25:32
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 800 ms
コード長 2,882 bytes
コンパイル時間 1,529 ms
コンパイル使用メモリ 167,532 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-06 15:03:29
合計ジャッジ時間 5,147 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

#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);
}
0