#1177800 (C++23(gcc16)) No.8105 Міжнародний підрядок саміт

• 問題: No.8105 Міжнародний підрядок саміт
• ユーザー: wasd314
• 提出日時: 2026-08-20 22:40:54
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 3,634 bytes
• コンパイル時間: 1,662 ms
• コンパイル使用メモリ: 232,888 KB
• 実行使用メモリ: 9,728 KB
• 最終ジャッジ日時: 2026-08-20 22:41:00
• 合計ジャッジ時間: 3,245 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	WA * 2 RE * 2

ソースコード

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cstdlib>
#include <format>
#include <iostream>
#include <map>
#include <random>
#include <vector>

struct availability {
    using i64 = long long;
    using u64 = unsigned long long;
    std::array<u64, 3> bit;
    static constexpr i64 oo = 1e9;
    availability() {}
    availability(std::bitset<192> set) : bit{} {
        for (int i = 0; i < 3; ++i)
            for (int b = 0; b < 64; ++b)
                bit[i] |= u64(set.test(i * 64 + b)) << b;
    }
    i64 le(int p, i64 offset) const {
        p -= offset;
        int q = p / 64, r = p % 64;
        if (r != 63) {
            auto x = bit[q] << (63 - r);
            if (x) return offset + p - std::countl_zero(x);
            --q;
        }
        for (int i = q; i >= 0; --i) {
            if (bit[i]) return offset + i * 64 + 63 - std::countl_zero(bit[i]);
        }
        return oo;
    }
    i64 ge(int p, i64 offset) const {
        p -= offset;
        int q = p / 64, r = p % 64;
        if (r) {
            auto x = bit[q] >> r;
            if (x) return offset + p + std::countr_zero(x);
            ++q;
        }
        for (int i = q; i < 3; ++i) {
            if (bit[i]) return offset + i * 64 + std::countr_zero(bit[i]);
        }
        return oo;
    }
};

int main() {
    using namespace std;
    using lint = long long;
    constexpr lint oo = 1e18;

    auto build = [&](int n) {
        const int n2 = 1 << n;
        const int nn = n + 1;
        const int mid = n * (n + 1) / 2;
        vector available(nn, vector<bitset<192>>(n2));
        available[0][0].set(mid);
        for (int i = 0; i < n; ++i) {
            for (int sub = 0; sub < (1 << i); ++sub) {
                int bit = 1 << i | sub;
                for (int p = 0; p < popcount((unsigned)bit); ++p) {
                    available[p + 1][bit] |= available[p][sub] << i;
                    available[p][bit] |= available[p][sub] >> i;
                }
            }
        }
        vector availabilities(nn, vector<availability>(n2));

        for (int bit = 1; bit < n2; ++bit) {
            for (int p = 0; p <= popcount((unsigned)bit); ++p) {
                availabilities[p][bit] = availability(available[p][bit]);
            }
        }
        return availabilities;
    };
    map<int, decltype(build(13))> cache;
    for (int n : {2, 3, 5, 7, 11, 13}) cache[n] = build(n);

    auto solve = [&] {
        int n;
        lint mod;
        cin >> n >> mod;
        vector<lint> a(n);
        for (auto &e : a) cin >> e;
        if (n <= 1) return 0ll;
        if (a[1] < a[0]) ranges::reverse(a);
        lint a0 = a[0], d = a[1] - a[0];
        if (d == 0) return (a0 << n - 1) % mod;

        const auto &availabilities = cache[n];
        lint ans = 0;
        const int n2 = 1 << n;
        const int mid = n * (n + 1) / 2;
        for (int bit = 1; bit < n2; ++bit) {
            lint ansi = oo;
            int bc = popcount((unsigned)bit);
            for (int p = 0; p <= bc; ++p) {
                lint ca = 2 * p - bc;
                int x0 = -ca * a0 / d;
                if (x0 < 0 && -ca * a0 % d) x0--;
                const auto &av = availabilities[p][bit];
                lint xl = av.le(x0, -mid);
                lint xr = av.ge(x0 + 1, -mid);
                lint sl = abs(ca * a0 + xl * d);
                lint sr = abs(ca * a0 + xr * d);
                ansi = min({ansi, sl, sr});
            }
            ans += ansi;
        }
        return ans % mod;
    };
    int t = 1;
    cin >> t;
    for (int ti = 0; ti < t; ++ti) cout << solve() << "\n";
}