結果
| 問題 | No.493 とても長い数列と文字列(Long Long Sequence and a String） |
| ユーザー |
 e869120
|
| 提出日時 | 2017-03-07 14:14:20 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,335 bytes |
| コンパイル時間 | 1,010 ms |
| コンパイル使用メモリ | 77,524 KB |
| 実行使用メモリ | 17,088 KB |
| 最終ジャッジ日時 | 2024-06-23 19:27:52 |
| 合計ジャッジ時間 | 5,045 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
| testcase_100 | -- | - |
| testcase_101 | -- | - |
| testcase_102 | -- | - |
| testcase_103 | -- | - |
| testcase_104 | -- | - |
| testcase_105 | -- | - |
| testcase_106 | -- | - |
| testcase_107 | -- | - |
| testcase_108 | -- | - |
| testcase_109 | -- | - |
| testcase_110 | -- | - |
| testcase_111 | -- | - |
| testcase_112 | -- | - |
| testcase_113 | -- | - |
| testcase_114 | -- | - |
| testcase_115 | -- | - |
| testcase_116 | -- | - |
| testcase_117 | -- | - |
| testcase_118 | -- | - |
ソースコード
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
#pragma warning(disable:4996)
long long K, L, R, U, V; string Y;
long long sums(long long P, long long Q) {
if (P >= (1LL << Q))return (1LL << 62);
if (P < 0)return -(1LL << 62);
long long ret = 0, U = P;
for (int i = 1; i <= Q; i++) {
ret += ((U + 1) / 2) * to_string(i).size();
U -= (U + 1) / 2;
}
return ret;
}
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 63; i++) {
if ((b / (1LL << i)) % 2 == 1)p *= q;
q *= q;
p %= m; q %= m;
}
return p;
}
void search() {
//左の境界を探索
long long L1 = -1, R1 = (1LL << K) + 1, M1;
while (true) {
M1 = (L1 + R1) / 2;
long long Y1 = sums(M1 - 1, K), Y2 = sums(M1, K);
if (Y1 < L && Y2 >= L) {
U = M1; U++;
if (Y2 - L >= 1) {
long long I = M1, J = 1;
while (I % 2 == 0) { I /= 2; J++; }
Y += to_string(J).substr(to_string(J).size() - (Y2 - L), (Y2 - L));
}
break;
}
if (Y2 < L)L1 = M1;
if (Y1 >= L)R1 = M1;
}
//右の境界を探索
L1 = -1; R1 = (1LL << K) + 1;
while (true) {
M1 = (L1 + R1) / 2;
long long Y1 = sums(M1, K), Y2 = sums(M1 + 1, K);
if (Y1 <= R && Y2 > R) {
V = M1;
if (R - Y1 >= 1) {
long long I = M1, J = 1; I++;
while (I % 2 == 0) { I /= 2; J++; }
Y += to_string(J).substr(0, (R - Y1));
}
break;
}
if (Y2 <= R)L1 = M1;
if (Y1 > R)R1 = M1;
}
}
void solve(long long K, long long L, long long R) {
if (R > sums((1LL << K) - 1, K)) { cout << "-1" << endl; return; }
search();
//端数部分の和と積を求める
long long wa = 0, seki = 1;
for (int i = 0; i < Y.size(); i++) {
long long G = (Y[i] - '0'); if (G == 0)G = 10;
wa += G; seki *= G;
}
//区間の部分の積と和を求める
U--;
for (int i = 1; i <= K; i++) {
long long U1 = (U + 1) / 2;
long long U2 = (V + 1) / 2;
string T = to_string(i);
long long w1 = 0, w2 = 1;
for (int j = 0; j < T.size(); j++) {
long long G = (T[j] - '0'); if (G == 0)G = 10;
w1 += G; w2 *= G;
}
//cout << U2 - U1 << ' ' << U << ' ' << V << endl;
wa += w1*(U2 - U1);
seki *= modpow(w2, U2 - U1, 1000000007);
seki %= 1000000007;
U -= U1; V -= U2;
}
//出力
cout << wa << ' ' << seki << endl;
}
int main() {
for (int h = 1; h <= 2; h++) {
for (int i = 1; i <= 50; i++) {
// ------ end ------ //
string TS = to_string(h);
string ID = to_string(i); if (ID.size() == 1)ID = "0" + ID;
FILE *in = freopen(("./subtask" + TS + "_" + ID + ".txt").c_str(), "r", stdin);
cin >> K >> L >> R; L--;
FILE *out = freopen(("./subtask" + TS + "_" + ID + ".txt").c_str(), "w", stdout);
solve(K, L, R);
}
}
for (int i = 1; i <= 4; i++) {
// ------ end ------ //
string ID = to_string(i); if (ID.size() == 1)ID = "0" + ID;
FILE *in = freopen(("./sample_" + ID + ".txt").c_str(), "r", stdin);
cin >> K >> L >> R; L--;
FILE *out = freopen(("./sample_" + ID + ".txt").c_str(), "w", stdout);
solve(K, L, R);
}
for (int i = 1; i <= 5; i++) {
// ------ end ------ //
string ID = to_string(i); if (ID.size() == 1)ID = "0" + ID;
FILE *in = freopen(("./special_" + ID + ".txt").c_str(), "r", stdin);
cin >> K >> L >> R; L--;
FILE *out = freopen(("./special_" + ID + ".txt").c_str(), "w", stdout);
solve(K, L, R);
}
return 0;
}