結果
| 問題 | No.8105 Міжнародний підрядок саміт |
| コンテスト | |
| ユーザー |
 wasd314
|
| 提出日時 | 2026-08-21 19:03:05 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 3,153 ms |
| + 206µs | |
| コード長 | 4,876 bytes |
| 記録 | |
| コンパイル時間 | 4,231 ms |
| コンパイル使用メモリ | 278,884 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-08-21 19:03:12 |
| 合計ジャッジ時間 | 4,127 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 4 |
ソースコード
#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <atcoder/all>
#include "atcoder/math.hpp"
int main() {
using namespace std;
using i64 = long long;
using A = array<i64, 4>;
vector<vector<A>> data{
{},
{},
{
{1, 0, 2, 2},
},
{
{1, 1, 2, 8},
{1, 0, 4, 6},
},
{},
{
{1, 2, 0, 44},
{1, 1, 4, 42},
{2, 1, 8, 38},
{4, 1, 14, 26},
{1, 0, 16, 18},
},
{},
{
{1, 3, -24, 180},
{1, 2, -18, 178},
{1, 1, 10, 164},
{3, 2, 14, 160},
{2, 1, 26, 142},
{5, 2, 30, 134},
{3, 1, 34, 124},
{4, 1, 40, 106},
{5, 1, 46, 82},
{6, 1, 48, 72},
{7, 1, 56, 24},
{9, 1, 62, -18},
{1, 0, 64, -36},
},
{},
{},
{},
{
{1, 4, -896, 2252}, {1, 3, -784, 2224}, {1, 2, -304, 2064},
{2, 3, 4, 1910}, {3, 4, 436, 1622}, {1, 1, 484, 1586},
{5, 4, -370, 2440}, {4, 3, -354, 2420}, {3, 2, -72, 2044},
{5, 3, 308, 1474}, {2, 1, 536, 1094}, {7, 3, -146, 2458},
{5, 2, -32, 2192}, {8, 3, 428, 1042}, {3, 1, 506, 834},
{10, 3, 6, 2334}, {7, 2, 36, 2234}, {11, 3, 436, 834},
{4, 1, 454, 768}, {13, 3, 120, 2104}, {9, 2, 126, 2078},
{5, 1, 418, 764}, {11, 2, 222, 1744}, {6, 1, 390, 820},
{13, 2, 302, 1348}, {7, 1, 386, 802}, {15, 2, 346, 1082},
{8, 1, 386, 782}, {17, 2, 418, 526}, {9, 1, 430, 424},
{19, 2, 480, -26}, {10, 1, 484, -64}, {11, 1, 586, -1084},
{12, 1, 666, -1964}, {13, 1, 730, -2732}, {14, 1, 780, -3382},
{15, 1, 826, -4026}, {16, 1, 868, -4656}, {17, 1, 904, -5232},
{18, 1, 944, -5912}, {19, 1, 970, -6380}, {20, 1, 990, -6760},
{21, 1, 1004, -7040}, {22, 1, 1008, -7124}, {23, 1, 1016, -7300},
{25, 1, 1022, -7438}, {1, 0, 1024, -7488},
},
{},
{
{1, 5, -4792, 7576}, {1, 4, -4662, 7550}, {1, 3, -3422, 7240},
{2, 5, -620, 6306}, {1, 2, -540, 6274}, {3, 5, -416, 6212},
{2, 3, -366, 6182}, {3, 4, 2388, 4346}, {4, 5, 3244, 3704},
{1, 1, 3274, 3680}, {6, 5, -2934, 9888}, {5, 4, -2924, 9876},
{4, 3, -2444, 9276}, {3, 2, -164, 6236}, {5, 3, 788, 4808},
{7, 4, 2870, 1338}, {2, 1, 3118, 904}, {9, 4, -2004, 11148},
{7, 3, -1884, 10878}, {5, 2, -366, 7336}, {8, 3, 1430, 2846},
{11, 4, 2690, -514}, {3, 1, 2738, -646}, {13, 4, -1328, 11552},
{10, 3, -1312, 11500}, {7, 2, -520, 8860}, {11, 3, 1720, 1020},
{4, 1, 2350, -1290}, {13, 3, -766, 11174}, {9, 2, -400, 9588},
{14, 3, 1744, -60}, {5, 1, 2014, -1320}, {16, 3, -326, 10380},
{11, 2, -200, 9708}, {17, 3, 1624, -324}, {6, 1, 1708, -800},
{19, 3, 96, 8872}, {13, 2, 126, 8682}, {20, 3, 1494, -210},
{7, 1, 1512, -330}, {22, 3, 360, 7734}, {15, 2, 366, 7690},
{8, 1, 1338, 400}, {17, 2, 642, 5968}, {9, 1, 1270, 630},
{19, 2, 846, 4446}, {10, 1, 1218, 912}, {21, 2, 1134, 1752},
{11, 1, 1326, -264}, {23, 2, 1362, -660}, {12, 1, 1450, -1672},
{25, 2, 1702, -4696}, {13, 1, 1742, -5196}, {27, 2, 1954, -7952},
{14, 1, 1966, -8114}, {29, 2, 2166, -10914}, {15, 1, 2170, -10972},
{16, 1, 2364, -13882}, {17, 1, 2562, -17050}, {18, 1, 2752, -20280},
{19, 1, 2914, -23196}, {20, 1, 3120, -27110}, {21, 1, 3274, -30190},
{22, 1, 3450, -33886}, {23, 1, 3590, -36966}, {24, 1, 3696, -39404},
{25, 1, 3778, -41372}, {26, 1, 3858, -43372}, {27, 1, 3920, -44984},
{28, 1, 3964, -46172}, {29, 1, 4008, -47404}, {30, 1, 4040, -48332},
{31, 1, 4062, -48992}, {32, 1, 4076, -49426}, {33, 1, 4080, -49554},
{34, 1, 4088, -49818}, {36, 1, 4094, -50022}, {1, 0, 4096, -50094},
},
};
auto solve = [&](int n, i64 a, i64 d, i64 mod) {
if (d == 0) return a * atcoder::pow_mod(2, n - 1, mod) % mod;
for (const auto &x : data[n]) {
if (d * x[0] >= a * x[1]) return (a * x[2] + d * x[3]) % mod;
}
return 0ll;
};
int t;
cin >> t;
while (t--) {
i64 n, p;
cin >> n >> p;
vector<i64> a(n);
for (auto &e : a) cin >> e;
if (a[1] < a[0]) ranges::reverse(a);
cout << solve(n, a[0], a[1] - a[0], p) << "\n";
}
}