結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー akusyounin2412akusyounin2412
提出日時 2020-02-23 23:59:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 800 ms
コード長 3,834 bytes
コンパイル時間 1,171 ms
コンパイル使用メモリ 129,176 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-11 00:27:54
合計ジャッジ時間 3,788 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 115
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;// 998244353;// ;
constexpr long long INF = numeric_limits<LL>::max() / 2;
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourd; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Rrep(i,mf) for(LL i=mf-1;i>=0;i--)
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
struct Edge { LL to, cost; };
struct edge { LL from, to, cost; };
vector<vector<LL>>g, rev;
vector<edge>edges;
vector<LL>v;
map<LL, LL>ma;
set<LL>st;
LL h, w, n, m, k, t, s, p, q, last, cnt, sum[210000], ans, a[510000], b[510000], dp[210000];
string str, ss;
bool f;
char c;
LL length[64];
LL mul[64], plu[64];
LL mod_inv(LL n,LL k=MOD-2) {
	LL ret = 1, x = n;
	while (k>0) {
		if (k & 1)ret *= x;
		x *= x;
		k /= 2;
		ret %= MOD;
		x %= MOD;
	}
	return ret;
}
int main() {
	length[1] = 1;
	mul[1] = 1;
	plu[1] = 1;
	for (LL i = 1; i < 63; i++) {
		LL cur = (i + 1) * (i + 1);
		int keta = log10(cur)+1;
		length[i + 1] = length[i] * 2 + keta;
		vector<LL>V;
		mul[i + 1] = mul[i] * mul[i] % MOD;
		plu[i + 1] = plu[i] * 2;
		for (int j = 0; j < (LL)log10((i + 1) * (i + 1))+1; j++) {
			if (cur % 10 == 0) {
				mul[i + 1] *= 10;
				mul[i + 1] %= MOD;
				plu[i + 1] += 10;
			}
			else {
				mul[i + 1] *= cur % 10;
				mul[i + 1] %= MOD;
				plu[i + 1] += cur % 10;
			}
			cur /= 10;
		}
	}
	LL K, L, R;
	cin >> K >> L >> R;
	if (K > 62)K = 62;
	if (R > length[K]) {
		cout << -1 << endl;
		return 0;
	}
	LL ma = 1, pa = 0;
	while (R != 0) {
		cnt = 0;
		while (R >= length[cnt + 1]) cnt++;
		R -= length[cnt];
		ma *= mul[cnt];
		ma %= MOD;
		pa += plu[cnt];
		cnt++;
		if (R > 0) {
			LL cur = cnt * cnt;
			for (int i = 0; i < min(R,(LL)log10(cnt*cnt)+1); i++) {
				LL keta = mod_inv(10, (LL)log10(cnt*cnt) - i);
				if ((cur/keta) % 10 == 0) {
					ma *= 10;
					ma %= MOD;
					pa += 10;
				}
				else {
					ma *= (cur / keta) % 10;
					ma %= MOD;
					pa += (cur / keta) % 10;
				}	
			}
			R = max(R - ((LL)log10(cnt*cnt) + 1), (LL)0);
		}
	}
	L--;
	while (L != 0) {
		cnt = 0;
		while (L >= length[cnt + 1]) cnt++;
		L -= length[cnt];
		ma *= mod_inv(mul[cnt]);
		ma %= MOD;
		pa -= plu[cnt];
		cnt++;
		if (L > 0) {
			LL cur = cnt * cnt;
			for (int i = 0; i < min(L,(LL)log10(cnt*cnt)+1); i++) {
				LL keta = mod_inv(10, (LL)log10(cnt*cnt) - i);
				if ((cur / keta) % 10 == 0) {
					ma *= mod_inv(10);
					ma %= MOD;
					pa -= 10;
				}
				else {
					ma *= mod_inv((cur / keta) % 10);
					ma %= MOD;
					pa -= (cur / keta) % 10;
				}
			}
			L = max(L - ((LL)log10(cnt*cnt) + 1), (LL)0);
		}
	}
	cout << pa << " " << ma << endl;
	return 0;
}
0