QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424599#8747. 朔望wsyearTL 2888ms79924kbC++175.4kb2024-05-29 13:56:162024-05-29 13:56:16

Judging History

你现在查看的是最新测评结果

  • [2024-05-29 13:56:16]
  • 评测
  • 测评结果:TL
  • 用时:2888ms
  • 内存:79924kb
  • [2024-05-29 13:56:16]
  • 提交

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 = 300;
const int maxv = 50000000;

int n, m, a[maxn], b[maxn], id[maxn], cnt[maxn], mx[maxn], idx[maxv], 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]);
    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) if (w[i - 1] < maxv) idx[w[i - 1]] = i;
    rep (i, 1, tot) cnt[i] = mx[i] = 0;
    rep (i, 1, m - 1) {
      for (auto [x, y] : dfac[id[i]][id[i + 1]]) {
        if (x < maxv) x = idx[x];
        else 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]]) {
        if (x < maxv) x = idx[x];
        else x = lower_bound(ALL(w), x) - w.begin() + 1;
        cnt[x] -= y;
      }
      if (i == 1) {
        for (auto [x, y] : facs[id[i]]) {
        if (x < maxv) x = idx[x];
        else x = lower_bound(ALL(w), x) - w.begin() + 1;
          cnt[x] += y;
        }
      }
      for (auto [x, y] : facs[id[i + 1]]) {
        if (x < maxv) x = idx[x];
        else 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]]) {
        if (x < maxv) x = idx[x];
        else x = lower_bound(ALL(w), x) - w.begin() + 1;
        cnt[x] -= y;
      }
      for (auto [x, y] : dfac[id[i]][id[i + 1]]) {
        if (x < maxv) x = idx[x];
        else 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: 100
Accepted
time: 2821ms
memory: 68292kb

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: 2774ms
memory: 79924kb

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: 2723ms
memory: 68388kb

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: 2888ms
memory: 56560kb

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: 1869ms
memory: 8724kb

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: 1569ms
memory: 7200kb

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: 2127ms
memory: 8100kb

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: 2002ms
memory: 10980kb

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: 2114ms
memory: 19716kb

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: 1632ms
memory: 22140kb

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: 2664ms
memory: 49972kb

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: -100
Time Limit Exceeded

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:


result: