QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424586 | #8747. 朔望 | wsyear | TL | 0ms | 0kb | C++17 | 5.3kb | 2024-05-29 13:38:55 | 2024-05-29 13:38:55 |
answer
// Author: Klay Thompson
// Problem: I. 朔望
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
template <int P>
class mod_int {
using Z = mod_int;
private:
static int mo(int x) { return x < 0 ? x + P : x; }
public:
int x;
int val() const { return x; }
mod_int() : x(0) {}
template <class T>
mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
bool operator==(const Z &rhs) const { return x == rhs.x; }
bool operator!=(const Z &rhs) const { return x != rhs.x; }
Z operator-() const { return Z(x ? P - x : 0); }
Z pow(long long k) const {
Z res = 1, t = *this;
while (k) {
if (k & 1) res *= t;
if (k >>= 1) t *= t;
}
return res;
}
Z &operator++() {
x < P - 1 ? ++x : x = 0;
return *this;
}
Z &operator--() {
x ? --x : x = P - 1;
return *this;
}
Z operator++(int) {
Z ret = x;
x < P - 1 ? ++x : x = 0;
return ret;
}
Z operator--(int) {
Z ret = x;
x ? --x : x = P - 1;
return ret;
}
Z inv() const { return pow(P - 2); }
Z &operator+=(const Z &rhs) {
(x += rhs.x) >= P && (x -= P);
return *this;
}
Z &operator-=(const Z &rhs) {
(x -= rhs.x) < 0 && (x += P);
return *this;
}
Z &operator*=(const Z &rhs) {
x = 1ULL * x * rhs.x % P;
return *this;
}
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o) \
friend T operator o(const Z &lhs, const Z &rhs) {\
Z res = lhs; \
return res o## = rhs; \
}
setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
};
const int P = 1e9 + 7;
using Z = mod_int<P>;
const int maxn = 25;
int n, m, a[maxn], b[maxn], id[maxn], cnt[maxn], mx[maxn], tot;
Z w[maxn], fac[maxn], ivf[maxn];
vector<pii> facs[maxn], dfac[maxn][maxn];
Z binom(int x, int y) {
if (x < 0 || y < 0 || x < y) return 0;
return fac[x] * ivf[y] * ivf[x - y];
}
ll LCM(ll x, ll y) { return x / gcd(x, y) * y; }
int main() {
fac[0] = 1;
rep (i, 1, maxn - 1) fac[i] = fac[i - 1] * i;
ivf[maxn - 1] = fac[maxn - 1].inv();
per (i, maxn - 1, 1) ivf[i - 1] = ivf[i] * i;
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> n;
rep (i, 1, n) cin >> a[i];
rep (i, 1, n) {
int val = a[i];
for (int w = 2; w * w <= val; w++) {
if (val % w != 0) continue;
int cnt = 0;
while (val % w == 0) cnt++, val /= w;
facs[i].emplace_back(w, cnt);
}
if (val > 1) facs[i].emplace_back(val, 1);
}
rep (i, 1, n) rep (j, i + 1, n) {
int val = a[j] - a[i];
for (int w = 2; w * w <= val; w++) {
if (val % w != 0) continue;
int cnt = 0;
while (val % w == 0) cnt++, val /= w;
dfac[i][j].emplace_back(w, cnt);
}
if (val > 1) dfac[i][j].emplace_back(val, 1);
}
rep (i, 2, n) cin >> w[i].x;
rep (i, 2, n) {
rep (j, 1, i - 1) w[i] -= w[j] * binom(i, j);
}
Z ans = 0;
rep (S, 1, (1 << n) - 1) {
if (__builtin_popcount(S) == 1) continue;
m = 0;
rep (i, 1, n) if (S >> (i - 1) & 1) b[++m] = a[i], id[m] = i;
Z prd = 1;
rep (i, 1, m - 1) prd *= (b[i + 1] - b[i]);
// ll lcm = 1;
// rep (i, 1, m - 1) lcm = LCM(lcm, prd.val() / (b[i + 1] - b[i]) * b[i] * b[i + 1]);
vector<int> w;
rep (i, 1, m) for (auto [x, y] : facs[id[i]]) w.emplace_back(x);
rep (i, 1, m - 1) for (auto [x, y] : dfac[id[i]][id[i + 1]]) w.emplace_back(x);
sort(ALL(w)), w.erase(unique(ALL(w)), w.end());
tot = SZ(w);
rep (i, 1, tot) cnt[i] = mx[i] = 0;
rep (i, 1, m - 1) {
for (auto [x, y] : dfac[id[i]][id[i + 1]]) {
x = lower_bound(ALL(w), x) - w.begin() + 1;
cnt[x] += y;
}
}
rep (i, 1, m - 1) {
for (auto [x, y] : dfac[id[i]][id[i + 1]]) {
x = lower_bound(ALL(w), x) - w.begin() + 1;
cnt[x] -= y;
}
for (auto [x, y] : facs[id[i]]) {
x = lower_bound(ALL(w), x) - w.begin() + 1;
cnt[x] += y;
}
for (auto [x, y] : facs[id[i + 1]]) {
x = lower_bound(ALL(w), x) - w.begin() + 1;
cnt[x] += y;
}
rep (i, 1, tot) chkmx(mx[i], cnt[i]);
for (auto [x, y] : facs[id[i]]) {
x = lower_bound(ALL(w), x) - w.begin() + 1;
cnt[x] -= y;
}
for (auto [x, y] : facs[id[i + 1]]) {
x = lower_bound(ALL(w), x) - w.begin() + 1;
cnt[x] -= y;
}
for (auto [x, y] : dfac[id[i]][id[i + 1]]) {
x = lower_bound(ALL(w), x) - w.begin() + 1;
cnt[x] += y;
}
}
Z lcm = 1;
rep (i, 1, tot) lcm *= Z(w[i - 1]).pow(mx[i]);
ans += Z(prd) / lcm * ::w[m];
}
cout << (ans * 2).val() << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
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...