結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー はまやんはまやんはまやんはまやん
提出日時 2017-03-11 01:25:32
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 115
権限があれば一括ダウンロードができます

ソースコード

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