QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425849 | #8747. 朔望 | cmk666 | AC ✓ | 2569ms | 5116kb | C++23 | 11.8kb | 2024-05-30 17:36:26 | 2024-05-30 17:36:26 |
Judging History
answer
/* _ _ _ _ __ __ __
/ \ _ _ | |_ | |__ ___ _ __ _ ___ _ __ ___ | | __ / /_ / /_ / /_
/ _ \ | | | | | __| | '_ \ / _ \ | '__| (_) / __| | '_ ` _ \ | |/ / | '_ \ | '_ \ | '_ \
/ ___ \ | |_| | | |_ | | | | | (_) | | | _ | (__ | | | | | | | < | (_) | | (_) | | (_) |
/_/ \_\ \__,_| \__| |_| |_| \___/ |_| (_) \___| |_| |_| |_| |_|\_\ \___/ \___/ \___/
[Created Time: 2024-05-30 14:46:35]
[Last Modified Time: 2024-05-30 17:36:17] */
#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include"debug.h"
#else
#define D(...) ((void)0)
#endif
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
// ------------------------------
// #define DISABLE_MMAP
// ------------------------------
#if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
inline constexpr int _READ_SIZE = 1 << 18;
inline static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer, _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
}
return *_read_ptr++;
}
#else
#include<sys/mman.h>
inline static const char *_read_ptr = (const char *)mmap(nullptr, 0x7fffffff, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
inline constexpr int _WRITE_SIZE = 1 << 18;
inline static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c)
{
*_write_ptr++ = c;
if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout), _write_ptr = _write_buffer;
}
inline struct _auto_flush
{
inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
template < class T > inline constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T > inline constexpr bool _is_unsigned = numeric_limits < T >::is_integer && !_is_signed < T >;
#if __SIZEOF_LONG__ == 64
template <> inline constexpr bool _is_signed < __int128 > = true;
template <> inline constexpr bool _is_unsigned < __uint128_t > = true;
#endif
inline void read(char &c) { do c = gc(); while ( !isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = gc(); while ( !isgraph(c) ) c = gc();
while ( isgraph(c) ) *s++ = c, c = gc(); *s = 0;
}
inline void read(string &s)
{
char c = gc(); s.clear(); while ( !isgraph(c) ) c = gc();
while ( isgraph(c) ) s.push_back(c), c = gc();
}
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); bool f = true; x = 0;
while ( !isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
if ( f ) while ( isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
else while ( isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); while ( !isdigit(c) ) c = gc();
x = 0; while ( isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
inline void write(const string &s) { for ( char c : s ) pc(c); }
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
while ( digits ) pc(buffer[--digits]);
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10]; int digits = 0;
do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
while ( digits ) pc(buffer[--digits]);
}
template < int N > struct _tuple_io_helper
{
template < class ...T > static inline void _read(tuple < T... > &x) { _tuple_io_helper < N - 1 >::_read(x), read(get<N - 1>(x)); }
template < class ...T > static inline void _write(const tuple < T... > &x) { _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get<N - 1>(x)); }
};
template <> struct _tuple_io_helper < 1 >
{
template < class ...T > static inline void _read(tuple < T... > &x) { read(get<0>(x)); }
template < class ...T > static inline void _write(const tuple < T... > &x) { write(get<0>(x)); }
};
template < class ...T > inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
template < class ...T > inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
template < class T1, class T2 > inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 > inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
template < class T1, class ...T2 > inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T > inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 > inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T > inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T > inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 > inline void print(const T1 &x, const T2 &...y) { write(x), pc(32), print(y...); }
template < class ...T > inline void print_cstr(const char *x, const T *...y) { write_cstr(x), pc(32), print_cstr(y...); }
inline void println() { pc(10); } inline void println_cstr() { pc(10); }
template < class ...T > inline void println(const T &...x) { print(x...), pc(10); }
template < class ...T > inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
} using FastIO::read, FastIO::read_cstr, FastIO::write, FastIO::write_cstr, FastIO::println, FastIO::println_cstr;
template < int P_ > class Modint
{
using MI = Modint;
inline Modint(int x, int) : v(x) {}
inline static int add(int x) { return x < P ? x : x - P; }
inline static int sub(int x) { return x >= 0 ? x : x + P; }
public:
static constexpr int P = P_; int v;
inline Modint() : v(0) {}
inline Modint(const MI &x) : v(x.v) {}
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
inline Modint(T x) : v(sub(x % P)) {}
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
explicit inline operator T()const { return v; }
inline friend bool operator==(const MI &x, const MI &y) { return x.v == y.v; }
inline friend bool operator!=(const MI &x, const MI &y) { return x.v != y.v; }
inline MI &operator=(const MI &x) { v = x.v; return *this; }
inline MI &operator++() { v < P - 1 ? v++ : v = 0; return *this; }
inline MI operator++(int) { MI x = *this; v < P - 1 ? v++ : v = 0; return x; }
inline MI &operator--() { v ? v-- : v = P - 1; return *this; }
inline MI operator--(int) { MI x = *this; v ? v-- : v = P - 1; return x; }
inline MI operator-()const { return MI(v ? P - v : 0, 0); }
inline friend MI operator+(const MI &x, const MI &y) { return MI(add(x.v + y.v), 0); }
inline friend MI operator-(const MI &x, const MI &y) { return MI(sub(x.v - y.v), 0); }
inline friend MI operator*(const MI &x, const MI &y) { return MI((ll)x.v * y.v % P, 0); }
inline friend MI operator/(const MI &x, const MI &y) { return x * y.inv(); }
inline MI &operator+=(const MI &x) { v = add(v + x.v); return *this; }
inline MI &operator-=(const MI &x) { v = sub(v - x.v); return *this; }
inline MI &operator*=(const MI &x) { v = (ll)v * x.v % P; return *this; }
inline MI &operator/=(const MI &x) { return *this *= x.inv(); }
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
inline MI qpow(T y)const
{ MI x(*this), z(1, 0); while ( y ) { if ( y & 1 ) z *= x; if ( y >>= 1 ) x *= x; } return z; }
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
inline friend MI qpow(const MI &x, T y) { return x.qpow(y); }
inline MI inv()const { assert(v); return qpow(P - 2); }
inline friend MI inv(const MI &x) { return x.inv(); }
inline friend istream &operator>>(istream &is, MI &x) { return is >> x.v; }
inline friend ostream &operator<<(ostream &os, const MI &x) { return os << x.v; }
}; using MI = Modint < 1000000007 >;
struct binom
{
MI fac[29], ifac[29];
inline binom()
{
constexpr int n = sizeof(fac) / sizeof(*fac) - 1;
fac[0] = 1; For(i, 1, n) fac[i] = i * fac[i - 1];
ifac[n] = inv(fac[n]); Fol(i, n, 1) ifac[i - 1] = i * ifac[i];
}
} binom;
inline MI fac(int x) { return x >= 0 ? binom.fac[x] : 0; }
inline MI ifac(int x) { return x >= 0 ? binom.ifac[x] : 0; }
inline MI c(int x, int y) { return x >= y && y >= 0 ? fac(x) * ifac(y) * ifac(x - y) : 0; }
struct
{
using T = int; T v[2009]; int l;
inline void clear() { l = 0; }
inline void push(T x) { v[++l] = x; }
inline void build() { sort(v + 1, v + l + 1), l = unique(v + 1, v + l + 1) - v - 1; }
inline int pre(T x)const { return upper_bound(v + 1, v + l + 1, x) - v - 1; }
inline int nxt(T x)const { return lower_bound(v + 1, v + l + 1, x) - v; }
inline int id(T x)const { return nxt(x); }
inline int len()const { return l; }
inline T val(int x)const { return v[x]; }
} d;
int n, t[29], w, l, u[29], cnt[512], mx[512]; MI ivpw[512][609], nw, res[29], ans;
vector < pair < int, int > > f[29], g[29][29];
inline auto factorize(int x)
{
vector < pair < int, int > > z;
for ( int i = 2 ; i * i <= x ; i++ ) if ( !( x % i ) )
for ( z.emplace_back(i, 1), x /= i ; !( x % i ) ; x /= i ) z.back().second++;
if ( x != 1 ) z.emplace_back(x, 1);
return z;
}
inline void d_push(const auto &x) { for ( auto [p, c] : x ) d.push(p); }
inline void d_id(auto &x) { for ( auto &[p, c] : x ) p = d.id(p) - 1; }
int main()
{
read(n);
For(i, 0, n - 1) read(t[i]), d_push(f[i] = factorize(t[i]));
For(i, 0, n - 1) For(j, i + 1, n - 1) d_push(g[i][j] = factorize(t[j] - t[i]));
d.build();
For(i, 0, n - 1) d_id(f[i]);
For(i, 0, n - 1) For(j, i + 1, n - 1) d_id(g[i][j]);
For(i, 0, d.len() - 1)
{
ivpw[i][0] = 1, ivpw[i][1] = inv(MI(d.val(i + 1)));
For(j, 2, 600) ivpw[i][j] = ivpw[i][j - 1] * ivpw[i][1];
}
For(i, 3, ( 1 << n ) - 1) if ( __builtin_popcount(i) != 1 )
{
l = 0; For(j, 0, n - 1) if ( i & ( 1 << j ) ) u[l++] = j;
nw = 2; For(j, 0, l - 2) nw *= t[u[j + 1]] - t[u[j]];
fill(cnt, cnt + d.len(), 0), fill(mx, mx + d.len(), 0);
For(j, 0, l - 2) for ( auto [p, c] : g[u[j]][u[j + 1]] ) cnt[p] += c;
For(j, 0, l - 2)
{
for ( auto [p, c] : g[u[j]][u[j + 1]] ) cnt[p] -= c;
For(k, 0, 1) for ( auto [p, c] : f[u[j + k]] ) cnt[p] += c;
For(j, 0, d.len() - 1) if ( cnt[j] ) mx[j] = max(mx[j], cnt[j]);
for ( auto [p, c] : g[u[j]][u[j + 1]] ) cnt[p] += c;
For(k, 0, 1) for ( auto [p, c] : f[u[j + k]] ) cnt[p] -= c;
}
For(j, 0, d.len() - 1) if ( mx[j] ) nw *= ivpw[j][mx[j]];
res[__builtin_popcount(i)] += nw;
}
Fol(i, n, 2) For(j, i + 1, n) res[i] -= res[j] * c(j, i);
For(i, 2, n) read(w), ans += res[i] * w;
return println(ans.v), 0;
}
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏
详细
Test #1:
score: 100
Accepted
time: 2520ms
memory: 4792kb
input:
20 73415948 190825288 205086969 242726140 280691039 291234110 341933576 379938879 399631744 420807939 421811250 486105558 605031352 645495854 714594262 775221445 793534057 818237037 926135349 940293639 108200337 125078426 163639475 261733041 280562529 287327830 310288774 415301468 419144734 46329977...
output:
153969420
result:
ok single line: '153969420'
Test #2:
score: 0
Accepted
time: 2526ms
memory: 4876kb
input:
20 84235069 157167959 241945024 324983190 344510999 389625308 393693455 492087389 545401834 611823985 699640865 718172624 789215994 804453614 825368584 850396218 864421557 956633895 998178799 998191351 10237096 66048990 113647123 152133403 158116741 170538744 310395982 317219199 388394456 425740854 ...
output:
519880572
result:
ok single line: '519880572'
Test #3:
score: 0
Accepted
time: 2513ms
memory: 5100kb
input:
20 4095671 19344443 19862217 99681209 164768338 179386320 227990671 259927153 291683257 322112421 325703075 386818784 391256396 394175885 530975901 633124435 706843457 768173984 832924754 864889710 181669395 188767026 285808351 330525208 350027130 386025072 475920661 520764065 521827714 550433016 59...
output:
851233434
result:
ok single line: '851233434'
Test #4:
score: 0
Accepted
time: 2566ms
memory: 4804kb
input:
20 18488602 59172425 92169299 108229468 165735372 248082200 359653090 395700282 420721479 428337394 435619427 448440085 536411011 562815310 615404200 639050216 667892289 714428379 894979649 912438198 41226204 51956102 62277661 81215110 107346163 126988480 130550912 189680493 261806109 318225281 3342...
output:
26689156
result:
ok single line: '26689156'
Test #5:
score: 0
Accepted
time: 685ms
memory: 4752kb
input:
20 17244836 19708384 98541920 123177400 150276428 226646416 241427704 275917376 315334144 320261240 376922844 591251520 620814096 709501824 721819564 810507292 854851156 862241800 918903404 992809844 37518403 39154238 51611231 261298439 269489128 290716487 478588543 499510038 547292150 592769093 605...
output:
696242820
result:
ok single line: '696242820'
Test #6:
score: 0
Accepted
time: 459ms
memory: 5116kb
input:
20 19247340 57742020 76989360 96236700 211720740 230968080 288710100 365699460 481183500 519678180 558172860 615914880 673656900 731398920 769893600 808388280 866130300 904624980 962367000 981614340 148910987 301586559 480690975 507474360 553446669 561302272 573740192 625086499 671148743 680592047 6...
output:
20117023
result:
ok single line: '20117023'
Test #7:
score: 0
Accepted
time: 702ms
memory: 4912kb
input:
20 100011990 110013189 113346922 136683053 296702237 313370902 346708232 356709431 403381693 436719023 480057552 486725018 546732212 653411668 853435648 860103114 893440444 913442842 916776575 993452434 1141138 78919305 129681127 130971538 169206258 171357952 287272942 325515992 370177227 409551792 ...
output:
381584175
result:
ok single line: '381584175'
Test #8:
score: 0
Accepted
time: 760ms
memory: 5116kb
input:
20 27 237 711 8937 26811 78447 222543 235341 310809 667629 706023 932427 2002887 2118069 2797281 8184637 8391843 73661733 220985199 662955597 78118579 107551612 147296745 171423408 186934128 200801750 268972463 317394828 385982506 390033240 391001980 437092765 550017817 591715010 680293234 680931512...
output:
783690675
result:
ok single line: '783690675'
Test #9:
score: 0
Accepted
time: 996ms
memory: 4872kb
input:
20 42 70 74 105 370 3108 7770 132764 1394022 3485055 4646740 4912268 14736804 34385876 36842010 42982345 73684020 103157628 257894070 515788140 86890917 99349467 100288573 146388649 202635206 211778581 216066880 259441085 272566210 282517395 350709246 351656224 415344730 437321109 439646931 50091437...
output:
209349219
result:
ok single line: '209349219'
Test #10:
score: 0
Accepted
time: 766ms
memory: 4872kb
input:
20 4 88 94 176 188 376 752 4136 8272 1734416 4769644 9539288 19078576 20379388 56043317 81517552 112086634 224173268 448346536 896693072 25894642 35841446 262580761 270189043 307645170 354483823 407560267 429108535 512245878 556443650 612770928 694158506 707942713 711723446 731755916 769038162 80605...
output:
23272490
result:
ok single line: '23272490'
Test #11:
score: 0
Accepted
time: 1562ms
memory: 4868kb
input:
20 65098209 105270708 130196418 157906062 195294627 315812124 319680266 325491045 390589254 421082832 444772544 455687463 578988894 585883881 631624248 653259674 684259602 806150236 894801018 976473135 3578211 6675920 43758254 129343185 166597720 214323863 321518612 397898341 448294997 459184157 524...
output:
407219779
result:
ok single line: '407219779'
Test #12:
score: 0
Accepted
time: 2042ms
memory: 4752kb
input:
20 10596498 35531952 111942666 145540750 151280704 198810810 267029456 270347450 481991424 488371290 517327338 539044374 553522398 618673506 680417856 707170900 770692758 895379824 956784300 966146082 75262456 81291374 157740574 177382772 224187967 224963690 225088760 329204109 345348134 379665154 4...
output:
681304676
result:
ok single line: '681304676'
Test #13:
score: 0
Accepted
time: 1653ms
memory: 4872kb
input:
20 80 632 4167 86663 143738 173326 175520 195073 1109811 2078199 6632482 6824157 6933040 10706720 21145772 26879006 84583088 106911793 211457720 422915440 3315979 21220087 58651584 91791639 115777919 239960507 323869479 332461958 416544648 435829226 455949270 459939949 546368034 625872179 635845488 ...
output:
261148592
result:
ok single line: '261148592'
Test #14:
score: 0
Accepted
time: 1544ms
memory: 4848kb
input:
20 1 2 48176672 144530016 149491593 240883360 385413376 385853771 398644248 448474779 548135841 597966372 626296736 722650080 747457965 770826752 771707542 797288496 819003424 867180096 265700314 298574772 379948160 392144351 579185844 591466916 600048020 634044117 658216544 752445159 871031259 8828...
output:
783843521
result:
ok single line: '783843521'
Test #15:
score: 0
Accepted
time: 1684ms
memory: 4868kb
input:
20 52975255 99539236 158925765 199078472 298617708 370826785 398156944 481607784 529752550 597235416 602009730 696774652 722411676 796313888 842813622 847604080 895853124 900579335 963215568 995392360 31582213 38258250 53989551 54513361 276550379 311979892 407315184 436245150 439986818 461986609 507...
output:
125576547
result:
ok single line: '125576547'
Test #16:
score: 0
Accepted
time: 2142ms
memory: 5108kb
input:
20 11850300 25460211 56596334 149241960 166636533 172159522 276676732 286633620 318858833 386716931 424025280 465558144 561416940 606797329 612257455 698808600 716837528 758956766 836200260 936917926 115697223 209194613 351537819 388238328 394873710 413102789 499708726 501043270 526994324 550643109 ...
output:
795473875
result:
ok single line: '795473875'
Test #17:
score: 0
Accepted
time: 1587ms
memory: 4868kb
input:
20 1 6 38 165 2252 6756 8547 43395 92237 409035 553422 969155 21515241 48158202 152500973 155788293 251011145 305001946 623153172 753033435 62364241 104631189 122135459 178280275 224992034 244406849 340524077 354749170 371186979 408957787 421677070 447733889 463953933 571618218 609375758 636820622 6...
output:
863256163
result:
ok single line: '863256163'
Test #18:
score: 0
Accepted
time: 1458ms
memory: 4748kb
input:
20 4 6 12 41 123 75412 1131180 1696770 3393540 4211982 6861307 20583921 47735796 102815714 205631428 281313587 308447142 616894284 716036940 843940761 221569314 386443201 416349001 439192190 464847884 501471052 505203171 507661678 523469370 631314320 648371609 664911180 713498516 717838226 743957043...
output:
126775026
result:
ok single line: '126775026'
Test #19:
score: 0
Accepted
time: 2038ms
memory: 4864kb
input:
20 85618618 122323298 156494542 312989084 342474472 366969894 384488652 439315390 469483626 484483804 576732978 611616490 615041546 625978168 768977304 770567562 790767702 938967252 968967608 978586384 9764324 62147886 182790628 217475696 272166868 320202370 383313123 427707975 458261446 464097589 5...
output:
377738451
result:
ok single line: '377738451'
Test #20:
score: 0
Accepted
time: 2192ms
memory: 4800kb
input:
20 122694814 158949021 214948899 241003311 275742527 314625052 352132185 612374904 627908754 651371094 700082174 718667531 729646392 762091551 772255594 831569983 835090095 838887015 868606485 895654928 50409346 58332259 88518028 149421099 324885046 371520732 393185641 434104505 513775676 580591077 ...
output:
73446460
result:
ok single line: '73446460'
Test #21:
score: 0
Accepted
time: 1475ms
memory: 4876kb
input:
20 1 2 3 15 25 67 1354 2895 64725 556635 622425 1250738 107430555 179050925 285184897 423374813 776686886 781761143 846749626 855554691 52564586 75924020 101813623 112630060 264692643 282441830 317809916 346165779 351613946 387601870 431377067 448713701 477419963 504343810 540360291 681378625 762356...
output:
24346695
result:
ok single line: '24346695'
Test #22:
score: 0
Accepted
time: 1873ms
memory: 5100kb
input:
20 28 1034 36182 1007633 2165339 84573223 150710913 169146446 301421826 338292892 353476000 403665354 452132739 530214000 602843652 676585784 706952000 753554565 807330708 904265478 38427228 73053662 177909997 200029866 371781963 423885926 474266217 588987891 597051547 604128809 681125077 698301945 ...
output:
291907103
result:
ok single line: '291907103'
Test #23:
score: 0
Accepted
time: 2021ms
memory: 4744kb
input:
20 83832398 105493778 210987556 247329456 273277876 312542529 412215760 435399654 546555752 625085058 653099481 738456446 741988368 754491582 819833628 824431520 843950224 870799308 937627587 949444002 813092 39296599 96365579 100816027 176992155 217463821 259056001 353829243 401564790 419875211 431...
output:
870217904
result:
ok single line: '870217904'
Test #24:
score: 0
Accepted
time: 2322ms
memory: 4860kb
input:
20 113463 25231072 32387434 72392869 127532412 132360219 154150282 231981720 254951361 266791663 342908997 382370310 462450846 470614112 508352254 637208208 748683189 749912845 764627157 770751410 79474123 85781559 130253327 175923011 179898379 182424902 232171837 254672053 281241978 343446151 35880...
output:
825619513
result:
ok single line: '825619513'
Test #25:
score: 0
Accepted
time: 1603ms
memory: 4864kb
input:
20 1 7 131 167 419 1669 2406 7961 14159 49199 105062 1593587 4588967 18958901 133134054 266268108 574791917 739741542 766357489 815232743 75132504 95506338 109721874 179113940 279978861 429159969 483947498 522561337 533445080 606939901 644719984 658756442 691803777 778980151 784101790 823547478 8415...
output:
365654901
result:
ok single line: '365654901'
Test #26:
score: 0
Accepted
time: 1992ms
memory: 4804kb
input:
20 21 23 1612525 137064625 171617761 187220989 247710518 371565777 374441978 495421036 514853283 561662967 619276295 667043401 748883956 825545195 866986813 936104945 990654234 990842072 47187348 55597667 219846730 314264164 341387925 453892369 464620478 538567661 559371096 560133753 588785515 62513...
output:
563943032
result:
ok single line: '563943032'
Test #27:
score: 0
Accepted
time: 2155ms
memory: 5068kb
input:
20 111885891 223771782 242314790 256016723 310597203 370005253 481203876 484629580 524427178 651074391 668869370 726944370 745905940 768050169 786640767 828640134 887828715 962407752 969259160 969677722 134059160 152713239 159992371 184158411 213477831 225462773 299704329 392008744 462304633 4630877...
output:
343699534
result:
ok single line: '343699534'
Test #28:
score: 0
Accepted
time: 2389ms
memory: 4748kb
input:
20 3987188 13644696 39715727 44281200 61238817 244242127 265156182 280014768 283012263 422265064 478506032 486925571 537903898 573723288 606325985 640454412 712769937 730093912 760612850 771912021 17830946 66533452 83591510 196129719 196364221 359941649 374135532 374161896 382166271 400186502 477216...
output:
190745266
result:
ok single line: '190745266'
Test #29:
score: 0
Accepted
time: 1993ms
memory: 4872kb
input:
20 2 15 2242 18286 54858 605218 7932787 24776331 36784115 74328993 110352345 187398567 222986979 388206062 464284897 668960937 678449378 714110869 776412124 936992835 16777217 77695601 146516769 205544182 260863046 306986807 365462839 386392065 535594531 609733658 723493673 770019964 771487489 84108...
output:
873672926
result:
ok single line: '873672926'
Test #30:
score: 0
Accepted
time: 1702ms
memory: 4900kb
input:
20 3 5 12 65 208 832 3107 15535 20868 408805 18318156 198011067 245765715 491531430 682791627 771204005 778250306 983062860 990055335 990544231 5036229 68655946 89674950 139224419 165933882 170934731 223429295 334637480 551805893 706983063 819420127 879997019 901655136 947675514 964184710 968594631 ...
output:
11960469
result:
ok single line: '11960469'
Test #31:
score: 0
Accepted
time: 2142ms
memory: 5108kb
input:
20 77991051 106682652 209064586 220803853 281146838 418129172 441607706 467946306 533413260 562293676 610626808 627193758 640095912 701919459 796932903 843440514 853195018 853461216 883215412 963934653 61721149 98534671 150634743 155567170 191797685 269955928 328421552 379755897 460153942 471343476 ...
output:
222692161
result:
ok single line: '222692161'
Test #32:
score: 0
Accepted
time: 2569ms
memory: 4804kb
input:
20 22158348 50725386 105270206 116982610 117482288 118456830 133964984 213352101 316541180 321982815 357578256 510714328 516099750 526483342 581516376 688265799 730983869 751405023 865149639 915216890 31859293 123540416 189889888 190274740 195572594 197204537 223248440 329219739 350841025 377919949 ...
output:
408888440
result:
ok single line: '408888440'
Test #33:
score: 0
Accepted
time: 1506ms
memory: 4904kb
input:
20 1 2 3 11 23 227 1259 1289 17929 134081 592471 2308871 26377282 68327447 134987441 506423937 674937205 751601917 814487767 927926660 14876115 49383550 54205833 168665473 217586724 263484051 331172429 339615399 470741813 471955353 487722150 559048829 616748210 723538981 756938006 816776546 89936108...
output:
425255105
result:
ok single line: '425255105'
Test #34:
score: 0
Accepted
time: 1684ms
memory: 4808kb
input:
20 13 37 71 87 229 888 2137 16259 55562 113606 114015 316339 439478 1733939 10439881 19296679 24854376 185531473 619931118 806261782 97788536 193826257 231860187 365529386 367150530 500366568 506811096 506869607 515553374 565090096 618451137 666384537 738809777 854106961 854145582 859830930 89497987...
output:
87796892
result:
ok single line: '87796892'
Test #35:
score: 0
Accepted
time: 2283ms
memory: 4872kb
input:
20 118772643 190098255 209029220 338904601 341867833 434139364 463352738 475090572 479748274 564640744 570294765 627087660 637464824 642610092 683735666 760393020 823715934 926705476 950491275 959496548 5517473 38442661 75757418 81567021 84068311 240560518 242520215 254416613 284909126 334581246 428...
output:
145704425
result:
ok single line: '145704425'
Test #36:
score: 0
Accepted
time: 2537ms
memory: 4880kb
input:
20 80613778 91503062 212156117 283494586 310021146 354353124 395100720 420608188 421327152 615198178 625723186 633477324 634396496 729662332 762901194 822097822 825705552 888976620 889088437 956933502 2407586 18588312 24445838 37676982 56888458 310709397 351452613 380713699 458804770 484064367 48533...
output:
37965627
result:
ok single line: '37965627'
Test #37:
score: 0
Accepted
time: 1516ms
memory: 4752kb
input:
20 1 2 5 9 24 52 97 133 676 4547 10803 5118825 34217297 40933703 196329726 232183218 541122865 695872951 889649722 966790967 90083105 102029449 175761678 207425067 356592375 424338499 522625868 616411984 658212740 680018107 701523030 723563211 741203089 792156752 808352395 901981653 920538603 976576...
output:
809867933
result:
ok single line: '809867933'
Test #38:
score: 0
Accepted
time: 1982ms
memory: 4868kb
input:
20 1 10 13 98 531 1163172 37578869 285002680 418638796 532241815 570005360 640898432 660162347 684006432 691981640 774736976 837277592 897782733 912008576 975498213 91140320 180293736 211230163 250047050 347115429 450047986 479364443 483350552 511815415 519744155 526065076 639746116 647701610 657453...
output:
916578888
result:
ok single line: '916578888'
Test #39:
score: 0
Accepted
time: 2414ms
memory: 4812kb
input:
20 55605352 172108639 208633384 265724196 427530028 485197752 531448392 580408272 612745334 625900152 722869576 728973619 797172588 860543195 865647792 876507276 919118001 942886494 961942563 970395504 437365 141306151 214126805 330114201 361377422 374409785 399798385 450595014 455024993 521550921 5...
output:
268105052
result:
ok single line: '268105052'
Test #40:
score: 0
Accepted
time: 2544ms
memory: 4904kb
input:
20 26815794 41812250 113613678 149369854 243156478 290991270 313181814 351458480 429396848 446310895 553547106 569810172 584884392 589415427 680221861 706401252 755635732 804585437 862569714 878777514 19455836 96171014 136378635 172475488 183024557 221711678 385630266 397481565 503668738 521991518 5...
output:
645820137
result:
ok single line: '645820137'
Test #41:
score: 0
Accepted
time: 2188ms
memory: 4868kb
input:
20 557 8941 40433 157062 471186 663094 13256737 45351995 52518233 110594303 131990382 165420467 221868111 350732317 701464634 730487075 787773495 827102335 849475469 918920791 18609216 49692102 58975929 74054513 94763711 149524982 172048385 267032324 283241712 545551900 614491381 625096185 634445006...
output:
584373027
result:
ok single line: '584373027'
Test #42:
score: 0
Accepted
time: 1934ms
memory: 4844kb
input:
20 5 9 24 118 354 447553 720627 11948452 25308891 28604649 85813947 194453522 200232543 408223732 418195820 437161480 593902831 612335598 874322960 890082188 30323463 65843264 80305948 101848732 121190701 169795166 218875189 227424905 236182010 242299110 281362663 294123402 294644156 387658771 54196...
output:
298324446
result:
ok single line: '298324446'