結果

問題 No.3105 Міжнародний підрядок саміт
ユーザー wasd314wasd314
提出日時 2023-04-16 19:42:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 9 ms / 3,153 ms
コード長 3,566 bytes
コンパイル時間 1,195 ms
コンパイル使用メモリ 88,288 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-20 07:10:26
合計ジャッジ時間 1,333 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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

struct Frac {
    lint num, den;
    Frac(lint num, lint den) : 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 pow2_mod(lint e, lint mod)
{
    if (e == 0) return 1 % mod;
    lint h = pow2_mod(e / 2, mod);
    h = h * h % mod;
    if (e & 1) h = h * 2 % mod;
    return h % mod;
}

int main()
{
    using namespace std;
    int t;
    cin >> t;

    const vector<Frac> sep = {{1, 36}, {1, 34}, {1, 33}, {1, 32}, {1, 31}, {1, 30}, {1, 29}, {1, 28}, {1, 27}, {1, 26}, {1, 25}, {1, 24}, {1, 23}, {1, 22}, {1, 21}, {1, 20}, {1, 19}, {1, 18}, {1, 17}, {1, 16}, {1, 15}, {2, 29}, {1, 14}, {2, 27}, {1, 13}, {2, 25}, {1, 12}, {2, 23}, {1, 11}, {2, 21}, {1, 10}, {2, 19}, {1, 9}, {2, 17}, {1, 8}, {2, 15}, {3, 22}, {1, 7}, {3, 20}, {2, 13}, {3, 19}, {1, 6}, {3, 17}, {2, 11}, {3, 16}, {1, 5}, {3, 14}, {2, 9}, {3, 13}, {1, 4}, {3, 11}, {2, 7}, {3, 10}, {4, 13}, {1, 3}, {4, 11}, {3, 8}, {2, 5}, {3, 7}, {4, 9}, {1, 2}, {4, 7}, {3, 5}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {1, 1}, {5, 4}, {4, 3}, {3, 2}, {5, 3}, {2, 1}, {5, 2}, {3, 1}, {4, 1}, {5, 1}, {1, 0}};
    const 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};
    const 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};

    while (t--) {
        int n;
        lint mod;
        cin >> n >> mod;
        vector<lint> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        lint a0 = min(a[0], a.back());
        lint d = abs(a[0] - a[1]);
        if (d == 0) {
            lint ans = pow2_mod(n - 1, mod) * a0 % mod;
            cout << ans << '\n';
            continue;
        }
        if (n != 13) {
            lint ans = solve0(n, mod, a);
            cout << ans << '\n';
            continue;
        }

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

    return 0;
}
0