QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425759 | #8747. 朔望 | cmk666 | WA | 2825ms | 3716kb | C++23 | 11.9kb | 2024-05-30 16:43:41 | 2024-05-30 16:43:41 |
Judging History
answer
/* _ _ _ _ __ __ __
/ \ _ _ | |_ | |__ ___ _ __ _ ___ _ __ ___ | | __ / /_ / /_ / /_
/ _ \ | | | | | __| | '_ \ / _ \ | '__| (_) / __| | '_ ` _ \ | |/ / | '_ \ | '_ \ | '_ \
/ ___ \ | |_| | | |_ | | | | | (_) | | | _ | (__ | | | | | | | < | (_) | | (_) | | (_) |
/_/ \_\ \__,_| \__| |_| |_| \___/ |_| (_) \___| |_| |_| |_| |_|\_\ \___/ \___/ \___/
[Created Time: 2024-05-30 14:46:35]
[Last Modified Time: 2024-05-30 16:43:34] */
#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], cur[512], mx[512]; MI ivpw[512][30], nw, res[29], ans;
vector < pair < int, int > > f[29], g[29][29]; bitset < 512 > ucnt, ucur, umx;
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, 29) ivpw[i][j] = ivpw[i][j - 1] * ivpw[i][1];
}
#define F(i, bs) for ( int i = bs._Find_first() ; i != 512 ; i = bs._Find_next(i) )
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]];
F(j, ucnt) cnt[j] = cur[j] = 0; ucnt.reset();
For(j, 0, l - 2) for ( auto [p, c] : g[u[j]][u[j + 1]] ) ucnt.set(p), cnt[p] += c; umx = ucnt;
For(j, 0, l - 2)
{
ucur.reset(); F(k, ucnt) cur[k] = cnt[k];
for ( auto [p, c] : g[u[j]][u[j + 1]] ) cur[p] -= c;
For(k, 0, 1) for ( auto [p, c] : f[u[j + k]] ) ucur.set(p), cur[p] += c;
F(k, ucnt) mx[k] = max(mx[k], cur[k]);
F(k, ucur) mx[k] = max(mx[k], cur[k]), cur[k] = 0; umx |= ucur;
}
F(j, umx) nw *= ivpw[j][mx[j]], mx[j] = 0;
res[__builtin_popcount(i)] += nw;
}
#undef F
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: 0
Wrong Answer
time: 2825ms
memory: 3716kb
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:
186236663
result:
wrong answer 1st lines differ - expected: '153969420', found: '186236663'