Submission #27677553

---

Source Code Expand

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
#include <string>
using namespace std;


constexpr uint32_t totient(uint32_t x){
    uint32_t ans = x;
    for(uint32_t i = 2; i * i <= x; i++) if(x % i == 0){
        ans /= i;
        ans *= i - 1;
        do x /= i; while(x % i == 0);
    }
    if(x != 1){
        ans /= x;
        ans *= x - 1;
    }
    return ans;
}
template<uint32_t P> struct Modint{
    static_assert(P < 0x80000000, "P must be smaller than 2^31");
    uint32_t a;
    Modint<totient(P)> b;
private:
    static uint32_t mod(uint64_t x){
        if(x < P * 2) return uint32_t(x);
        return uint32_t(x % P) + P;
    }
    static uint32_t mul(uint32_t a, uint32_t b){
        return mod(uint64_t(a) * b);
    }
    static uint32_t pow(uint32_t a, uint32_t b){
        uint32_t ans = 1;
        while(b){
            if(b & 1) ans = mul(ans, a);
            a = mul(a, a);
            b >>= 1;
        }
        return ans;
    }
public:
    Modint(uint64_t x): a(mod(x)), b(x){}
    Modint(uint32_t a, Modint<totient(P)> b): a(a), b(b){}
    uint32_t val() const {
        if(a < P) return a;
        return a - P;
    }
    Modint& operator*=(const Modint& other){
        a = mul(a, other.a);
        b *= other.b;
        return *this;
    }
    Modint operator*(const Modint& other) const {
        return Modint(*this) *= other;
    }
    Modint& operator+=(const Modint& other){
        a += other.a;
        if(a >= P * 2) a -= P;
        if(a >= P * 2) a -= P;
        b += other.b;
        return *this;
    }
    Modint operator+(const Modint& other) const {
        return Modint(*this) += other;
    }
    Modint pow(const Modint& other) const {
        return {pow(a, other.b.a), b.pow(other.b)};
    };
};
template<> struct Modint<1>{
    uint32_t a;
    Modint(uint64_t x): a(bool(x)){}
    uint32_t val() const {
        return 0;
    }
    Modint& operator*=(const Modint& other){
        a &= other.a;
        return *this;
    }
    Modint operator*(const Modint& other) const {
        return Modint(*this) *= other;
    }
    Modint& operator+=(const Modint& other){
        a |= other.a;
        return *this;
    }
    Modint operator+(const Modint& other) const {
        return Modint(*this) += other;
    }
    Modint pow(const Modint& other) const {
        return {a || !other.a};
    }
};


using M = Modint<1000000009>;
string get_char(string_view s){
    if(s.empty()) return "";
    return {s.end() - 3, s.end()};
}
void next(string_view& s){
    s = s.substr(0, s.size() - 3);
}
const vector<string> digit = {"〇", "一", "二", "三", "四", "五", "六", "七", "八", "九"};
M 一(string_view& s){
    const auto p = find(digit.begin(), digit.end(), get_char(s));
    if(p == digit.end()) return 0;
    next(s);
    return p - digit.begin();
}
M 二(string_view& s){
    const auto p = find(digit.begin(), digit.end(), get_char(s));
    if(p == digit.end()) return 1;
    next(s);
    return p - digit.begin();
}
M 十(string_view& s){
    M a = 一(s);
    if(get_char(s) != "十") return a;
    next(s);
    return 二(s) * 10 + a;
}
M 百(string_view& s){
    M a = 十(s);
    if(get_char(s) != "百") return a;
    next(s);
    return 二(s) * 100 + a;
}
M 千(string_view& s){
    M a = 百(s);
    if(get_char(s) != "千") return a;
    next(s);
    return 二(s) * 1000 + a;
}
M 万(string_view& s){
    M a = 千(s);
    if(get_char(s) != "万") return a;
    next(s);
    return 千(s) * 10000 + a;
}
M 億(string_view& s){
    M a = 万(s);
    if(get_char(s) != "億") return a;
    next(s);
    return 千(s) * 1'0000'0000 + a;
}
M expression(string_view& s){
    if(get_char(s) != "乗") return 億(s);
    next(s);
    M b = expression(s);
    assert(get_char(s) == "の");
    next(s);
    M a = expression(s);
    return a.pow(b);
}
string encode(uint32_t x){
    function<string(uint32_t)> f = [&](uint32_t x){
        if(x >= 100000000) return f(x / 100000000) + "億" + f(x % 100000000);
        if(x >= 10000) return f(x / 10000) + "万" + f(x % 10000);
        if(x >= 2000) return f(x / 1000) + "千" + f(x % 1000);
        if(x >= 1000) return "千" + f(x % 1000);
        if(x >= 200) return f(x / 100) + "百" + f(x % 100);
        if(x >= 100) return "百" + f(x % 100);
        if(x >= 20) return f(x / 10) + "十" + f(x % 10);
        if(x >= 10) return "十" + f(x % 10);
        return vector<string>{"", "一", "二", "三", "四", "五", "六", "七", "八", "九"}[x];
    };
    string ans = f(x);
    if(ans.empty()) ans = "〇";
    return ans;
}
int main(){
    string s;
    cin >> s;
    string_view p = s;
    cout << encode(expression(p).val()) << endl;
}

Submission Info

Judge Result