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

提出ソース

結果

問題	No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー	akusyounin2412
提出日時	2020-02-23 23:48:38
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	3,710 bytes
コンパイル時間	1,243 ms
コンパイル使用メモリ	126,420 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-04-19 07:32:19
合計ジャッジ時間	4,467 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

# 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 > 63)K = 63;
	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++) {
				if (cur % 10 == 0) {
					ma *= 10;
					ma %= MOD;
					pa += 10;
				}
				else {
					ma *= cur % 10;
					ma %= MOD;
					pa += cur % 10;
				}	
				cur /= 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++) {
				if (cur % 10 == 0) {
					ma *= mod_inv(10);
					ma %= MOD;
					pa -= 10;
				}
				else {
					ma *= mod_inv(cur % 10);
					ma %= MOD;
					pa -= cur % 10;
				}
				cur /= 10;
			}
			L = max(L - ((LL)log10(cnt*cnt) + 1), (LL)0);
		}
	}
	cout << pa << " " << ma << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード