結果

問題 No.528 10^9と10^9+7と回文
ユーザー TatsunoTatsuno
提出日時 2017-06-10 00:40:12
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,986 bytes
コンパイル時間 2,055 ms
コンパイル使用メモリ 175,244 KB
実行使用メモリ 4,372 KB
最終ジャッジ日時 2023-10-24 04:19:59
合計ジャッジ時間 5,391 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>
using namespace std;
using i32 = int; using i64 = long long int; using f64 = double; using str = string;
template <typename T> using vec = vector<T>;
template <typename T> using heap = priority_queue<T>;
void in() {}; template <typename T, typename...TS> void in(T &&x, TS &&...xs) { cin>>x; in(move(xs)...); };
template <typename T> void _out(const char *sep, const char *end, T &&x) { cout<<x<<end; };
template <typename T, typename...TS> void _out(const char *sep, const char *end, T &&x, TS &&...xs) { cout<<x<<sep; _out(sep, end, move(xs)...); }
#define indef(t, ...) t __VA_ARGS__; in(__VA_ARGS__)
#define get(t) []{ t _; cin >> _; return _; }()
#define put(...) _out("", "", __VA_ARGS__)
#define out(...) _out(" ", "\n", __VA_ARGS__)
#define times(n, i) for (i32 i =  0 ; i <  (n); ++i)
#define range(a, b, i) for (i32 i = (a); i <  (b); ++i)
#define upto(a, b, i) for (i32 i = (a); i <= (b); ++i)
#define downto(a, b, i) for (i32 i = (a); i >= (b); --i)
#define all(xs) (xs).begin(), (xs).end()
#define sortall(xs) sort(all(xs))
#define reverseall(xs) reverse(all(xs))
#define even(x) (((x) & 1) == 0)
#define odd(x) (((x) & 1) == 1)
#define append emplace_back
#define findge lower_bound
#define findgt upper_bound
const i64 MOD = 1000000007;
const f64 EPS = 1e-10;

template <typename T> T prevpow(T a, T x) {
    if (a <= 1 || x < 1) throw domain_error(NULL);
    auto n = floor(log(double(x)) / log(double(a)));
    auto p = pow(a, n + 1);
    return p <= x ? p : pow(a, n);
}

template <typename T> tuple<T, T, T> gcdext(T a, T b) {
    T s0 = 1, s1 = 0;
    T t0 = 0, t1 = 1;
    T q = 1;
    while (b != 0) {
        q = a / b;
        swap(a, b); b = b % a;
        swap(s0, s1); s1 = s1 - q*s0;
        swap(t0, t1); t1 = t1 - q*t0;
    }
    return a < 0 ? make_tuple(-a, -s0, -t0) : make_tuple(a, s0, t0);
}

template <typename T> T invmod(T n, T m) {
    auto gxy = gcdext(n, m);
    T g, x, y; tie(g, x, y) = gxy;
    if (g != 1 || m == 0) throw domain_error(NULL);
    return (x+m)%m;
}

template <typename T> T powmod(T x, T p, T m) {
    if (p < 0) return powmod(invmod(x, m), -p, m);
    if (p == 0) return 1 % m;
    if (m == 1 || m == -1) return 0;
    T b = x % m;
    T t = prevpow(T(2), p);
    T r = 1;
    while (true) {
        if (p >= t) {
            r = (r*b) % m;
            p -= t;
        }
        t >>= 1;
        if (t <= 0) break;
        r = (r*r) % m;
    }
    return r;
}

const i64 mod0 = 10e9;
const i64 mod7 = 10e9+7;
str s;

i64 solve(str s, i64 m) {
    i64 ans0 = 0, ans7 = 0;
    upto(1, s.size()-1, li) {
        i64 p = powmod(10ll, i64(li+1) / 2, m);
        p -= powmod(10ll, i64(li+1) / 2 - 1, m);
        while (p < 0) p += m;
        ans0 = (ans0 + p) % m;
    }
    {
        i64 l = (s.size()+1)/2;
        str s1 = "";
        str s2 = "";
        times(l, li) {
            s1 += s[li];
            s2 += s[s.size()/2+li];
        }
        str ss = s1;
        times(l, li) {
            if (s1[s1.size()-1-li] > s2[li]) {
                downto(ss.size()-1, 0, si) {
                    if (ss[si] > '0') {
                        ss[si]--;
                        break;
                    }
                    ss[si] = '9';
                }
                if (ss[0] == '0') {
                    return ans0;
                }
                break;
            }
            if (s1[s1.size()-1-li] < s2[li]) {
                break;
            }
        }
        i64 t = 0;
        times(ss.size(), si) {
            t = (t + (ss[si]-'0') * powmod(10ll, i64(ss.size()-1-si), m)) % m;
        }
        i64 u = 0;
        range(1, ss.size(), si) {
            u = (u + 9 * powmod(10ll, i64(ss.size()-1-si), m)) % m;
        }
        i64 p = t - u;
        while (p < 0) p += m;
        ans0 = (ans0 + p) % m;
    }
    return ans0;
}

i32 main()
{
    in(s);
    out(solve(s, mod0));
    out(solve(s, mod7));
    return 0;
}
0