#954546 (C++17) No.2649 [Cherry 6th Tune C] Anthem Flower

提出ソース

結果

問題	No.2649 [Cherry 6th Tune C] Anthem Flower
ユーザー	mjtai
提出日時	2024-02-23 22:35:13
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	423 ms / 2,000 ms
コード長	9,069 bytes
コンパイル時間	3,430 ms
コンパイル使用メモリ	248,476 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-09-29 07:35:07
合計ジャッジ時間	8,054 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	225 ms 6,816 KB
testcase_02	AC	228 ms 6,816 KB
testcase_03	AC	214 ms 6,820 KB
testcase_04	AC	217 ms 6,820 KB
testcase_05	AC	423 ms 6,816 KB
testcase_06	AC	419 ms 6,820 KB
testcase_07	AC	22 ms 6,816 KB
testcase_08	AC	22 ms 6,816 KB
testcase_09	AC	5 ms 6,820 KB
testcase_10	AC	6 ms 6,820 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	36 ms 6,816 KB
testcase_14	AC	35 ms 6,816 KB
testcase_15	AC	35 ms 6,816 KB
testcase_16	AC	36 ms 6,816 KB
testcase_17	AC	35 ms 6,816 KB
testcase_18	AC	36 ms 6,820 KB
testcase_19	AC	36 ms 6,820 KB
testcase_20	AC	37 ms 6,816 KB
testcase_21	AC	36 ms 6,816 KB
testcase_22	AC	35 ms 6,820 KB
testcase_23	AC	35 ms 6,816 KB
testcase_24	AC	35 ms 6,824 KB
testcase_25	AC	36 ms 6,820 KB
testcase_26	AC	36 ms 6,820 KB
testcase_27	AC	36 ms 6,820 KB
testcase_28	AC	35 ms 6,816 KB
testcase_29	AC	35 ms 6,816 KB
testcase_30	AC	36 ms 6,816 KB
testcase_31	AC	36 ms 6,816 KB
testcase_32	AC	36 ms 6,816 KB
testcase_33	AC	33 ms 6,820 KB
testcase_34	AC	154 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

///////////////////////////////////////////////////////////////////////////////

#include <bits/stdc++.h>
#include <unistd.h>
#include <time.h>
#include <sys/time.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

///////////////////////////////////////////////////////////////////////////////

typedef long long ll;
typedef unsigned long long ull;
typedef __int128_t ll128;
typedef tuple<ll, ll> t2;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;
template <typename T>
using priority_queue_incr = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using binary_search_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define pb push_back
#define V vector
#define S static
#define SP << " " <<

#define rep(i,n) for(ll i=0LL; i<n; ++i)
#define srep(i,s,n) for(ll i=s; i<n; ++i)
#define rrep(i,n) for(ll i=n-1LL; i>=0LL; --i)
#define rfrep(i,f,n) for(ll i=n-1LL; i>=f; --i)
#define cfor(i,x) for(const auto & (i) : (x))
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CIN(x) do { \
        assert(!cin.eof()); \
        cin >> x; \
        assert(!cin.fail()); \
} while(0);
#define E18(x) ((x) * 1'000'000'000'000'000'000LL)
#ifdef DEBUG
#include "../../../template/debug.h"
#else // DEBUG
#define debug_print(...)
#define debug_printf(...)
#endif // DEBUG

///////////////////////////////////////////////////////////////////////////////

ll llin()
{
    ll a; CIN(a); return a;
}

V<ll> llina(ll count)
{
    V<ll> v;
    for (ll i = 0LL; i < count; ++i) {
        ll a; CIN(a); v.push_back(a);
    }
    return v;
}

V<V<ll>> llinaa(ll h, ll w)
{
    V<V<ll>> v(h, V<ll>(w));
    rep (hh, h) rep (ww, w) {
        ll a; CIN(a); v[hh][ww] = a;
    }
    return v;
}

V<t2> llinl2(ll count)
{
    V<t2> v;
    for (ll i = 0LL; i < count; ++i) {
        ll a, b; CIN(a >> b); v.push_back(t2(a, b));
    }
    return v;
}

V<t3> llinl3(ll count)
{
    V<t3> v;
    for (ll i = 0LL; i < count; ++i) {
        ll a, b, c; CIN(a >> b >> c); v.push_back(t3(a, b, c));
    }
    return v;
}

V<t4> llinl4(ll count)
{
    V<t4> v;
    for (ll i = 0LL; i < count; ++i) {
        ll a, b, c, d; CIN(a >> b >> c >> d); v.push_back(t4(a, b, c, d));
    }
    return v;
}

string strin()
{
    string s; CIN(s); return s;
}

V<string> strina(ll count)
{
    V<string> slist(count);
    for (ll i = 0; i < count; ++i) CIN(slist[i]);
    return slist;
}

template <typename T>
void sort(V<T> &v)
{
    sort(v.begin(), v.end());
}

template <typename T>
void sort_reverse(V<T> &v)
{
    sort(v.begin(), v.end(), greater<T>());
}

t2 _ext_gcd(ll a, ll b, ll g)
{
    if (!b) return t2(1, 0);
    ll q = a / b;
    ll r = a % b;
    auto [sx, sy] = _ext_gcd(b, r, g);
    ll x = sy;
    ll y = sx - q * sy;
    return t2(x, y);
}

t2 ext_gcd(ll a, ll b)
{
    return _ext_gcd(a, b, gcd(a, b));
}

// x and mod must be coprime
ll mod_inv(ll x, ll mod)
{
    auto [ret, xxxx] = ext_gcd(x, mod);
    while (ret < 0) ret += mod;
    ret %= mod;
    return ret;
}


S ll mintmod = 1000000007LL;
// S ll mintmod = 998244353LL;

struct mint {
    ll x;

    mint() {
        this->x = 0;
    }

    mint(const mint &other) {
        this->x = other.x;
    }

    mint(ll x) {
        if (x < 0) x = mintmod - (abs(x) % mintmod);
        this->x = x % mintmod;
    }

    void operator=(const mint& a) {
        this->x = a.x;
    }

    void operator=(ll a) {
        if (a < 0) a = mintmod - (abs(a) % mintmod);
        this->x = a % mintmod;
    }

    void operator+=(const mint& a) {
        this->x += a.x;
        if (this->x >= mintmod) this->x -= mintmod;
    }

    void operator+=(ll a) {
        if (a < 0) this->x -= abs(a) % mintmod;
        else this->x += a;
        if (this->x < 0) this->x += mintmod;
        if (this->x >= mintmod) this->x -= mintmod;
        if (this->x >= mintmod) this->x %= mintmod;
    }

    void operator-=(const mint& a) {
        this->x -= a.x;
        if (this->x < 0) this->x += mintmod;
    }

    // a should be small
    void operator-=(ll a) {
        if (a < 0) {
            this->x += abs(a) % mintmod;
            if (this->x >= mintmod) this->x -= mintmod;
            return;
        }
        this->x -= a;
        while (this->x < 0) this->x += mintmod;
    }

    void operator*=(const mint& a) {
        this->x *= a.x;
        this->x %= mintmod;
    }

    void operator*=(ll a) {
        assert(a >= 0);
        this->x *= a % mintmod;
        this->x %= mintmod;
    }

    bool operator==(const mint &a) {
        if (this->x != a.x) return false;
        return true;
    }

    bool operator==(ll a) {
        if (a < 0) a = mintmod - (abs(a) % mintmod);
        if (this->x != a % mintmod) return false;
        return true;
    }

    bool operator!=(const mint &a) {
        return !(*this == a);
    }

    bool operator!=(ll a) {
        return !(*this == a);
    }

    void inv() {
        this->x = mod_inv(this->x, mintmod);
    }
};

void _debug_print_mod(mint p0) {
    if (p0.x == 0) {
        cout << 0 << endl;
        return;
    }
    srep (a, 1, 256) {
        ll ai = mod_inv(a, mintmod);
        srep (b, 1, 256) {
            if (gcd(a, b) > 1) continue;
            mint p1 = b * ai;
            if (p0.x != p1.x) continue;
            cout << b << "/" << a << " ";
        }
    }
    cout << endl;
}

mint operator+(const mint& a, const mint& b) {
    mint ret = a;
    ret.x += b.x;
    if (ret.x >= mintmod) ret.x -= mintmod;
    return ret;
}

mint operator+(const mint& a, ll b) {
    mint ret = a;
    if (b < 0) ret.x -= abs(b) % mintmod;
    else ret.x += b;
    if (ret.x < 0) ret.x += mintmod;
    if (ret.x >= mintmod) ret.x -= mintmod;
    if (ret.x >= mintmod) ret.x %= mintmod;
    return ret;
}

mint operator-(const mint& a, const mint& b) {
    mint ret = a;
    ret.x -= b.x;
    if (ret.x < 0) ret.x += mintmod;
    return ret;
}

// b should be small
mint operator-(const mint& a, ll b) {
    mint ret = a;
    if (b < 0) {
        ret.x += abs(b) % mintmod;
        if (ret.x >= mintmod) ret.x -= mintmod;
        return ret;
    }
    ret.x -= b;
    while (ret.x < 0) ret.x += mintmod;
    return ret;
}

mint operator*(const mint& a, const mint& b) {
    mint ret = a;
    ret.x *= b.x;
    ret.x %= mintmod;
    return ret;
}

mint operator*(const mint& a, ll b) {
    assert(b >= 0);
    mint ret = a;
    ret.x *= b % mintmod;
    ret.x %= mintmod;
    return ret;
}

ostream& operator<<(ostream& os, const mint& a)
{
   os << a.x;
   return os;
}

// O(log(exp))
mint mod_pow(ll base, ll exp, ll mod)
{
    mint ret = 1;

    for ( ; exp; ) {
        if (exp & 1LL) ret *= base;
        base = (base * base) % mod;
        exp >>= 1;
    }

    return ret;
}

// O(log(exp))
mint mod_pow(mint base, ll exp)
{
    mint ret = 1;

    for ( ; exp; ) {
        if (exp & 1LL) ret *= base;
        base = base * base;
        exp >>= 1;
    }

    return ret;
}

void make_factorial(mint factorials[], mint inv_factorials[], ll size)
{
    factorials[0] = 1;
    srep (i, 1, size) factorials[i] = factorials[i-1] * i;

    inv_factorials[size-1] = factorials[size-1];
    inv_factorials[size-1].inv();
    rrep (i, size-1) inv_factorials[i] = inv_factorials[i+1LL] * (i+1LL);
}

#if 0
S mint factorials[XXX SZ];
S mint inv_factorials[XXX SZ];
mint binom(ll x, ll y)
{
    assert(x >= y);
    mint ret = 1;
    ret *= factorials[x];
    ret *= inv_factorials[y];
    ret *= inv_factorials[x-y];
    return ret;
}

make_factorial(factorials, inv_factorials, XXX SZ);
#endif




///////////////////////////////////////////////////////////////////////////////

void _main();
int main()
{
    cout << setprecision(12);
#ifndef DEBUG
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif // DEBUG

    _main();
    return 0;
}

///////////////////////////////////////////////////////////////////////////////

string sf(string s)
{
    rrep (i, s.size()) {
        if (s[i] < '9') {
            s[i]++;
            return s;
        }
        s[i] = '0';
    }
    return '1'+ s;
}

string fd2(string s)
{
    rrep (i, s.size()) {
        ll d = s[i] - '0';
        s[i] = d / 2 + '0';
        if (d & 1) {
            s[i+1] += 5;
        }
    }
    return s;
}

mint fs(string s)
{
    mint d10 = 1;
    mint ret;
    rrep (i, s.size()) {
        ret += d10 * (s[i]-'0');
        d10 *= 10LL;
    }
    return ret;
}

void slv()
{
    string s0 = strin();
    mintmod = llin();

    debug_printf("------------------------------\n");

    string s1 = sf(s0);
    debug_printf("---- s1=%s\n", s1.c_str());

    if (s0[s0.size()-1] % 2 == 0) {
        s0 = fd2(s0);
    }
    else {
        s1 = fd2(s1);
    }

    debug_printf("---- s0=%s s1=%s\n", s0.c_str(), s1.c_str());

    mint ans = 1;
    ans *= fs(s0);
    ans *= fs(s1);
    cout << ans << "\n";
}

void _main()
{
    ll t = llin();
    rep (i, t) slv();
}

///////////////////////////////////////////////////////////////////////////////

yukicoder

結果

テストケース

ソースコード