#938604 (C++23) No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ

• 問題: No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
• ユーザー: sgfc
• 提出日時: 2023-12-16 02:15:39
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 280 ms / 3,000 ms
• コード長: 5,536 bytes
• コンパイル時間: 5,888 ms
• コンパイル使用メモリ: 327,080 KB
• 実行使用メモリ: 6,676 KB
• 最終ジャッジ日時: 2023-12-16 02:15:51
• 合計ジャッジ時間: 10,849 ms
• ジャッジサーバーID （参考情報）: judge15 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,676 KB
testcase_01	AC	10 ms; 6,676 KB
testcase_02	AC	26 ms; 6,676 KB
testcase_03	AC	99 ms; 6,676 KB
testcase_04	AC	63 ms; 6,676 KB
testcase_05	AC	22 ms; 6,676 KB
testcase_06	AC	84 ms; 6,676 KB
testcase_07	AC	84 ms; 6,676 KB
testcase_08	AC	31 ms; 6,676 KB
testcase_09	AC	59 ms; 6,676 KB
testcase_10	AC	82 ms; 6,676 KB
testcase_11	AC	28 ms; 6,676 KB
testcase_12	AC	101 ms; 6,676 KB
testcase_13	AC	114 ms; 6,676 KB
testcase_14	AC	102 ms; 6,676 KB
testcase_15	AC	96 ms; 6,676 KB
testcase_16	AC	98 ms; 6,676 KB
testcase_17	AC	98 ms; 6,676 KB
testcase_18	AC	114 ms; 6,676 KB
testcase_19	AC	120 ms; 6,676 KB
testcase_20	AC	118 ms; 6,676 KB
testcase_21	AC	116 ms; 6,676 KB
testcase_22	AC	267 ms; 6,676 KB
testcase_23	AC	273 ms; 6,676 KB
testcase_24	AC	280 ms; 6,676 KB
testcase_25	AC	260 ms; 6,676 KB
testcase_26	AC	269 ms; 6,676 KB
testcase_27	AC	17 ms; 6,676 KB
testcase_28	AC	18 ms; 6,676 KB
testcase_29	AC	225 ms; 6,676 KB
testcase_30	AC	2 ms; 6,676 KB
testcase_31	AC	104 ms; 6,676 KB

ソースコード

#include "bits/stdc++.h"

#include <stdio.h>
#include <math.h>

#include "atcoder/all"
#include <float.h>

//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
// std::fixed << std::setprecision(10) <<

using namespace std;
using namespace atcoder;

using ll = long long;
using ull = unsigned long long;
using mint = modint998244353;
using mint2 = modint1000000007;

const double eps = 1e-9;

#define REP(i, n) for (ll i = 0; i < ll(n); ++i)
#define REPI(i, init, n) for (ll i = init; i < ll(n); ++i)
#define REPD(i, init) for (ll i = init; i >=0; --i)
#define REPDI(i, init, n) for (ll i = init; i >=n; --i)
#define REPE(i, c) for (const auto& i : c)
#define TCASE() ll _ttt; cin >> _ttt; while(_ttt--)

using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>;
#define VL(a, n) vector<ll> a; a.assign(n, 0);
#define VLI(a, n) vector<ll> a; a.assign(n, 0); for(auto& x : a) cin >> x;
#define VSI(a, n) vector<string> a; a.assign(n, ""); for(auto& x : a) cin >> x;
#define VVLI(a, n, m, init) vector<vector<ll>> a(n); for(auto& x : a) x.assign(m, init);
using vd = vector<double>;
using pl = pair<ll, ll>;

struct uv { ll u; ll v; ll c; };
#define VUVI(a, n) vector<uv> a; a.assign(n, {0, 0, 1}); for(auto& x : a) {cin >> x.u >> x.v; x.u--; x.v--;}
#define VUVCI(a, n) vector<uv> a; a.assign(n, {0, 0, 0}); for(auto& x : a) {cin >> x.u >> x.v >> x.c; x.u--; x.v--;}
vvl to_edge(const ll n, const vector<uv>& v) { vvl ret(n); for (auto& x : v) ret[x.u].push_back(x.v); return ret; }
vvl to_edge_d(const ll n, const vector<uv>& v) { vvl ret(n); for (auto& x : v) { ret[x.u].push_back(x.v); ret[x.v].push_back(x.u); } return ret; }

template <class T = long long> using pql = priority_queue<T>;
template <class T = long long> using pqg = priority_queue<T, vector<T>, greater<T>>;
using vm = vector<mint>; using vvm = vector<vm>;

void yn(bool f) { std::cout << (f ? "Yes" : "No") << endl; };
template<class T> void ov(const T& v) { for (auto it = v.begin(); it != v.end(); it++) { if (it != v.begin()) cout << " "; cout << *it; } };
template<> void ov(const vm& v) { for (auto it = v.begin(); it != v.end(); it++) { if (it != v.begin()) cout << " "; cout << it->val(); } };

const ll llhuge = 1LL << 60; //十分でかいが多少足しても溢れない数値
auto gmax(const auto& a, const auto& b) { return a > b ? a : b; };
auto gmin(const auto& a, const auto& b) { return a < b ? a : b; };
bool chmin(auto& a, const auto& b) { const auto olda = a; a = gmin(a, b); return olda != a; }
bool chmax(auto& a, const auto& b) { const auto olda = a; a = gmax(a, b); return olda != a; }
template<class T> void mysort(T& v) { std::sort(begin(v), end(v)); };
template<class T, class U> void mysort(T& v, U pr) { std::sort(begin(v), end(v), pr); };
template<class T> void myrev(T& v) { std::reverse(begin(v), end(v)); };
template<class T, class K = T::key_type, class V = T::mapped_type> [[nodiscard]] V myat(const T& mp, const K& key) { return mp.find(key) == mp.end() ? V() : mp.at(key); }
long long ceil(const long long a, const long long b) { return (a + b - 1) / b; }

vector<map<ll, ll>> dpf(const vl& g, const vl& h, const ll m) {
    vector<map<ll, ll>> dp(15);

    dp[0][0] = 1;
    REP(i, 14) {
        vector<map<ll, ll>> dp2(15);
        REP(j, i + 2) {
            REPE(e, dp[j]) dp2[j][(e.first + h[i]) % m] += e.second;
            if (j > 0) {
                REPE(e, dp[j - 1]) dp2[j][(e.first + g[i]) % m] += e.second;
            }
        }
        dp = move(dp2);
    }

    return dp;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);

    ll m;
    cin >> m;
    VLI(g1, 14);
    VLI(g2, 14);
    VLI(h1, 14);
    VLI(h2, 14);

    auto mp1 = dpf(g1, h1, m);
    auto mp2 = dpf(g2, h2, m);

    vector<map<ll, ll>> mps2(15);
    REP(i, 15) {
        ll sum2 = 0;
        REPE(e, mp2[i]) {sum2 += e.second; mps2[i][e.first] = sum2;}
    }

    ll q;
    cin >> q;
    REP(i, q) {
        ll k, x;
        cin >> k >> x;

        ll ans = 0;
        REP(j, 15) {
            if (k - j < 0 || k - j >= 15) continue;

            ll j2 = k - j;
            REPE(e, mp1[j]) {
				ll mn = x - e.first;
                ll ov = m - e.first;
                //z >= x - e && z < m - e

                //y以上の要素の合計
                const auto f = [&](ll y) {
                    if (mps2[j2].empty()) return 0LL;

                    ll sub = 0;
                    auto it = mps2[j2].lower_bound(y);
                    if (it != mps2[j2].begin()) { it--; sub = it->second; }
                    return mps2[j2].rbegin()->second - sub;
				};
                //y未満の要素の合計
                const auto f2 = [&](ll y) {
                    if (mps2[j2].empty()) return 0LL;

                    ll sub = 0;
                    auto it = mps2[j2].lower_bound(y);
                    if (it != mps2[j2].begin()) { it--; sub = it->second; }
                    return sub;
                };

                ll sum2 = 0;
                if (mn >= 0) {
                    //mn以上ov未満の数値の合計を求める
                    sum2 = f(mn) - f(ov);
                }
                if (mn < 0) {
                    // z + e > m + x
                    //0以上ov未満+mn+m以上の要素
                    sum2 = f(mn + m);
                    sum2 += f2(ov);
                }
				
				ans += e.second * sum2;
			}
		}
        cout << ans << endl;
	}

    return 0;
}