QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424604#8747. 朔望wsyearTL 2906ms83244kbC++175.1kb2024-05-29 14:01:152024-05-29 14:01:16

Judging History

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

  • [2024-05-29 14:01:16]
  • 评测
  • 测评结果:TL
  • 用时:2906ms
  • 内存:83244kb
  • [2024-05-29 14:01:15]
  • 提交

answer

// Author: Klay Thompson
// Problem: I. 朔望
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("Ofast")

#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], c1[maxn], c2[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, m) {
      c1[i] = facs[id[i]];
      for (auto &[x, y] : c1[i]) {
        if (x < maxv) x = idx[x];
        else x = lower_bound(ALL(w), x) - w.begin() + 1;
      }
    }
    rep (i, 1, m - 1) {
      c2[i] = dfac[id[i]][id[i + 1]];
      for (auto &[x, y] : c2[i]) {
        if (x < maxv) x = idx[x];
        else x = lower_bound(ALL(w), x) - w.begin() + 1;
      }
    }
    rep (i, 1, tot) cnt[i] = mx[i] = 0;
    rep (i, 1, m - 1) {
      for (auto [x, y] : c2[i]) cnt[x] += y;
    }
      for (auto [x, y] : c1[1]) cnt[x] += y;
    rep (i, 1, m - 1) {
      for (auto [x, y] : c2[i]) cnt[x] -= y;
      for (auto [x, y] : c1[i + 1]) cnt[x] += y;
      rep (i, 1, tot) chkmx(mx[i], cnt[i]);
      for (auto [x, y] : c1[i]) cnt[x] -= y;
      for (auto [x, y] : c2[i]) 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';
}

詳細信息

Test #1:

score: 100
Accepted
time: 2538ms
memory: 70416kb

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: 2468ms
memory: 83244kb

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: 2391ms
memory: 71524kb

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: 2564ms
memory: 55724kb

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: 1846ms
memory: 8080kb

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: 1570ms
memory: 6888kb

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: 2121ms
memory: 8808kb

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: 12492kb

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: 2220ms
memory: 20808kb

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: 1643ms
memory: 22292kb

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: 2591ms
memory: 50940kb

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: 2906ms
memory: 56004kb

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: 2454ms
memory: 28416kb

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: 1842ms
memory: 53508kb

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: 2628ms
memory: 39956kb

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

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: