結果
| 問題 | No.2649 [Cherry 6th Tune C] Anthem Flower |
| ユーザー |
 mjtai
|
| 提出日時 | 2024-02-23 22:35:13 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 485 ms / 2,000 ms |
| コード長 | 9,069 bytes |
| コンパイル時間 | 3,659 ms |
| コンパイル使用メモリ | 237,504 KB |
| 最終ジャッジ日時 | 2025-02-19 20:20:11 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 35 |
ソースコード
///////////////////////////////////////////////////////////////////////////////#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 coprimell 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 smallvoid 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 smallmint 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 0S 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 DEBUGios::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();}///////////////////////////////////////////////////////////////////////////////