結果
問題 | No.493 とても長い数列と文字列(Long Long Sequence and a String) |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}