結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー vjudge1
提出日時 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;
}
0