結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String)
ユーザー vjudge1vjudge1
提出日時 2025-01-27 13:20:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 800 ms
コード長 2,121 bytes
コンパイル時間 3,619 ms
コンパイル使用メモリ 281,696 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-27 13:20:28
合計ジャッジ時間 6,544 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 115
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int p = 1e9 + 7, N = 61;
i64 k, l, r, len[N], sum[N], prod[N];
inline int fix(int d) { return d == 0 ? 10 : d; }
inline i64 query_sum(i64 L, i64 R, i64 l, i64 r, int k) {
i64 ans = 0;
if (l <= L && R <= r) return sum[k];
if (l <= L + len[k - 1] - 1) {
ans = ans + query_sum(L, L + len[k - 1] - 1, l, r, k - 1);
}
int sq = k * k, lg = log10(sq) + 1;
for (int i = lg - 1; i >= 0; i--) {
if (r >= L + len[k - 1] + i && l <= L + len[k - 1] + i) {
ans += fix(sq % 10);
}
sq /= 10;
}
if (r >= R - len[k - 1] + 1) {
ans = ans + query_sum(R - len[k - 1] + 1, R, l, r, k - 1);
}
return ans;
}
inline i64 query_prod(i64 L, i64 R, i64 l, i64 r, int k) {
i64 ans = 1;
if (l <= L && R <= r) return prod[k];
if (l <= L + len[k - 1] - 1) {
ans = ans * query_prod(L, L + len[k - 1] - 1, l, r, k - 1) % p;
}
int sq = k * k, lg = log10(sq) + 1;
for (int i = lg - 1; i >= 0; i--) {
if (r >= L + len[k - 1] + i && l <= L + len[k - 1] + i) {
ans = ans * fix(sq % 10) % p;
}
sq /= 10;
}
if (r >= R - len[k - 1] + 1) {
ans = ans * query_prod(R - len[k - 1] + 1, R, l, r, k - 1) % p;
}
return ans;
}
inline int digit_sum(int x) {
int sum = 0;
while (x) {
sum += fix(x % 10), x /= 10;
}
return sum;
}
inline i64 digit_prod(int x) {
i64 sum = 1;
while (x) {
sum = sum * fix(x % 10) % p, x /= 10;
}
return sum;
}
int main(int argc, char const *argv[]) {
cin >> k >> l >> r, prod[0] = 1;
for (int i = 1; i <= 60; i++) {
int sq = i * i, l = log10(sq) + 1;
len[i] = len[i - 1] * 2 + l;
sum[i] = 2 * sum[i - 1] + digit_sum(sq);
prod[i] = prod[i - 1] * prod[i - 1] % p * digit_prod(sq) % p;
}
k = min(k, 60ll);
if (len[k] < r) {
cout << "-1\n";
return 0;
}
cout << query_sum(1, len[k], l, r, k) << ' ';
cout << query_prod(1, len[k], l, r, k) << ' ';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0