結果
問題 | No.8105 Міжнародний підрядок саміт |
ユーザー | wasd314 |
提出日時 | 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 |
ソースコード
#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;}