結果

問題 No.8105 Міжнародний підрядок саміт
ユーザー wasd314wasd314
提出日時 2023-04-03 07:25:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,566 bytes
コンパイル時間 973 ms
コンパイル使用メモリ 86,908 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-12 02:11:49
合計ジャッジ時間 1,592 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 6 ms
6,816 KB
testcase_02 RE -
testcase_03 AC 5 ms
6,820 KB
testcase_04 AC 11 ms
6,820 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];
if (n != 13) {
lint ans = solve0(n, mod, a);
cout << ans << '\n';
continue;
}
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;
}
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0