結果

問題 No.3105 Міжнародний підрядок саміт
ユーザー wasd314wasd314
提出日時 2023-04-03 02:57:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,628 bytes
コンパイル時間 1,036 ms
コンパイル使用メモリ 87,440 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-20 07:03:18
合計ジャッジ時間 1,543 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 6 ms
5,376 KB
testcase_02 WA -
testcase_03 AC 6 ms
5,376 KB
testcase_04 AC 11 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <vector>
using lint = long long;

struct Frac {
    lint num, den;
    Frac(lint num = 0, lint den = 1) : num(num), den(den) {}
    bool operator<(Frac const &other) const
    {
        return num * other.den < den * other.num;
    }
};

lint solve0(int n, lint mod, std::vector<lint> &a)
{
    using namespace std;

    const lint infty = 1LL << 60;
    vector<lint> ansl(1 << n, infty);

    auto dfs = [&](auto f, int i, int bit, lint s) -> void {
        if (i == n) {
            ansl[bit] = min(ansl[bit], abs(s));
            return;
        }
        f(f, i + 1, bit, s);
        f(f, i + 1, bit | 1 << i, s + a[i]);
        f(f, i + 1, bit | 1 << i, s - a[i]);
    };
    dfs(dfs, 0, 0, 0);

    lint ans = 0;
    for (lint e : ansl) ans += e % mod;
    ans %= mod;
    return ans;
}

lint solve1(int, lint mod, std::vector<lint> &a)
{
    using namespace std;

    vector sep = {Frac(1, 36), Frac(1, 34), Frac(1, 33), Frac(1, 32), Frac(1, 31), Frac(1, 30), Frac(1, 29), Frac(1, 28), Frac(1, 27), Frac(1, 26), Frac(1, 25), Frac(1, 24), Frac(1, 23), Frac(1, 22), Frac(1, 21), Frac(1, 20), Frac(1, 19), Frac(1, 18), Frac(1, 17), Frac(1, 16), Frac(1, 15), Frac(2, 29), Frac(1, 14), Frac(2, 27), Frac(1, 13), Frac(2, 25), Frac(1, 12), Frac(2, 23), Frac(1, 11), Frac(2, 21), Frac(1, 10), Frac(2, 19), Frac(1, 9), Frac(2, 17), Frac(1, 8), Frac(2, 15), Frac(3, 22), Frac(1, 7), Frac(3, 20), Frac(2, 13), Frac(3, 19), Frac(1, 6), Frac(3, 17), Frac(2, 11), Frac(3, 16), Frac(1, 5), Frac(3, 14), Frac(2, 9), Frac(3, 13), Frac(1, 4), Frac(3, 11), Frac(2, 7), Frac(3, 10), Frac(4, 13), Frac(1, 3), Frac(4, 11), Frac(3, 8), Frac(2, 5), Frac(3, 7), Frac(4, 9), Frac(1, 2), Frac(4, 7), Frac(3, 5), Frac(2, 3), Frac(3, 4), Frac(4, 5), Frac(5, 6), Frac(1, 1), Frac(5, 4), Frac(4, 3), Frac(3, 2), Frac(5, 3), Frac(2, 1), Frac(5, 2), Frac(3, 1), Frac(4, 1), Frac(5, 1), Frac(1, 0)};
    vector cal = {4096, 4094, 4088, 4080, 4076, 4062, 4040, 4008, 3964, 3920, 3858, 3778, 3696, 3590, 3450, 3274, 3120, 2914, 2752, 2562, 2364, 2170, 2166, 1966, 1954, 1742, 1702, 1450, 1362, 1326, 1134, 1218, 846, 1270, 642, 1338, 366, 360, 1512, 1494, 126, 96, 1708, 1624, -200, -326, 2014, 1744, -400, -766, 2350, 1720, -520, -1312, -1328, 2738, 2690, 1430, -366, -1884, -2004, 3118, 2870, 788, -164, -2444, -2924, -2934, 3274, 3244, 2388, -366, -416, -540, -620, -3422, -4662, -4792};
    vector cdl = {-50094, -50022, -49818, -49554, -49426, -48992, -48332, -47404, -46172, -44984, -43372, -41372, -39404, -36966, -33886, -30190, -27110, -23196, -20280, -17050, -13882, -10972, -10914, -8114, -7952, -5196, -4696, -1672, -660, -264, 1752, 912, 4446, 630, 5968, 400, 7690, 7734, -330, -210, 8682, 8872, -800, -324, 9708, 10380, -1320, -60, 9588, 11174, -1290, 1020, 8860, 11500, 11552, -646, -514, 2846, 7336, 10878, 11148, 904, 1338, 4808, 6236, 9276, 9876, 9888, 3680, 3704, 4346, 6182, 6212, 6274, 6306, 7240, 7550, 7576};
    lint a0 = min(a[0], a.back());
    lint d = abs(a[0] - a[1]);

    int i = lower_bound(sep.begin(), sep.end(), Frac(d, a0)) - sep.begin();
    lint ca = cal[i] % mod;
    lint cd = cdl[i] % mod;
    lint ans = a0 % mod * ca % mod + d % mod * cd % mod;
    ans %= mod;
    ans += mod;
    ans %= mod;
    return ans;
}

int main()
{
    using namespace std;
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        lint mod;
        cin >> n >> mod;
        vector<lint> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        lint ans = (n < 13) ? solve0(n, mod, a) : solve1(n, mod, a);
        cout << ans << '\n';
    }

    return 0;
}
0