QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114921#6157. 组合数问题nhuang685100 ✓139ms7028kbC++204.1kb2023-06-24 03:57:082023-06-24 03:57:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 03:57:09]
  • 评测
  • 测评结果:100
  • 用时:139ms
  • 内存:7028kb
  • [2023-06-24 03:57:08]
  • 提交

answer

/**
 * @file qoj6157F1.cpp
 * @author nhuang685
 * @brief
 * @date 2023-06-23
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr \
  if (false) std::cerr
#endif

std::pair<int64_t, int64_t> exEucl(int64_t a, int64_t b) {
  if (a < b) {
    auto [x, y] = exEucl(b, a);
    return {y, x};
  }
  if (b == 0) {
    assert(a == 1);
    return {1, 0};
  }
  auto [x, y] = exEucl(b, a % b);
  return {y, x - (a / b) * y};
}

template <class Md>
class Mod {
 private:
  using T = typename std::decay<decltype(Md::value)>::type;
  T val = 0;

 public:
  template <class U>
  static T normalize(U val) {
    if (val <= -Md::value || Md::value <= val) val %= Md::value;
    if (val < 0) val += Md::value;
    return static_cast<T>(val);
  }

  Mod() : val(0) {}
  template <class U>
  Mod(U _val) {
    val = normalize(_val);
  }

  // addition
  Mod &operator+=(Mod b) {
    val += b.val;
    if (val >= Md::value) val -= Md::value;
    return *this;
  }
  friend Mod operator+(Mod a, Mod b) { return (a += b); }
  Mod &operator++() { return (*this += 1); }
  Mod operator++(int) {
    Mod res = *this;
    ++(*this);
    return res;
  }

  // subtraction
  Mod &operator-=(Mod b) {
    val -= b.val;
    if (val < 0) val += Md::value;
    return *this;
  }
  friend Mod operator-(Mod a, Mod b) { return (a -= b); }
  Mod &operator--() { return (*this -= 1); }
  Mod operator--(int) {
    Mod res = *this;
    --(*this);
    return res;
  }

  // multiplication
  Mod &operator*=(Mod b) {
    val = static_cast<T>(static_cast<int64_t>(val) * b.val % Md::value);
    return *this;
  }
  friend Mod operator*(Mod a, Mod b) { return (a *= b); }

  // division
  template <class U>
  Mod binpow(U b) const {
    // assumes Mod(0).binpow(0) == 1
    Mod res = 1, a = *this;
    while (b > 0) {
      if (b % 2 == 1) res *= a;
      a *= a;
      b /= 2;
    }
    return res;
  }
  Mod inv() const {
    return Mod(
        exEucl(static_cast<int64_t>(val), static_cast<int64_t>(Md::value))
            .first);
  }
  Mod operator/=(Mod b) { return (*this *= b.inv()); }
  friend Mod operator/(Mod a, Mod b) { return (a /= b); }

  // comparison
  bool operator==(Mod b) const { return (val == b.val); }
  // strong_ordering operator<=>(Mod b) { return (val <=> b.val); }
  bool operator!=(Mod b) const { return (val != b.val); }
  bool operator<(Mod b) const { return (val < b.val); }
  bool operator>(Mod b) const { return (val > b.val); }
  bool operator<=(Mod b) const { return (val <= b.val); }
  bool operator>=(Mod b) const { return (val >= b.val); }

  // io
  friend std::istream &operator>>(std::istream &in, Mod &a) {
    int64_t val;
    cin >> val;
    a = Mod(val);
    return in;
  }
  friend std::ostream &operator<<(std::ostream &out, const Mod &a) {
    out << a.val;
    return out;
  }

  // conversion
  explicit operator T() const { return val; }
  const T &operator()() const { return val; }
  Mod operator-() const { return Mod(-val); }
};

struct Md {
  static int value;
};
int Md::value;
int &p = Md::value;
using Mint = Mod<Md>;

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int n, xx, m;
  cin >> n >> xx >> p >> m;
  Mint x = xx;

  std::vector<Mint> a(m + 1);
  for (int i = 0; i <= m; ++i) cin >> a[i];

  std::vector<std::vector<Mint>> st(m + 1, std::vector<Mint>(m + 1));
  st[0][0] = 1;
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= i; ++j) {
      st[i][j] = st[i - 1][j - 1] + j * st[i - 1][j];
    }
  }

  std::vector<Mint> fall(m + 1);
  fall[0] = 1;
  for (int i = 1; i <= m; ++i) fall[i] = fall[i - 1] * (n - i + 1);

  Mint ans = 0;
  for (int i = 0; i <= m; ++i) {
    Mint l = 0;
    for (int j = 0; j <= i; ++j)
      l += st[i][j] * fall[j] * x.binpow(j) * (1 + x).binpow(n - j);
    ans += a[i] * l;
  }
  cout << ans << '\n';
}

詳細信息

Test #1:

score: 5
Accepted
time: 55ms
memory: 6948kb

input:

1000 643189585 831941236 1000
621444125 324708497 619770455 112615814 800909697 461794889 380815971 872773343 314541774 472606930 636420887 783552328 794270098 539204140 23007446 139105268 406306323 866123427 218553206 804461683 30473072 117201808 568299563 477252115 324883663 342559946 1371621 5042...

output:

692083420

result:

ok 1 number(s): "692083420"

Test #2:

score: 5
Accepted
time: 51ms
memory: 7028kb

input:

1000 503195138 513597392 1000
722484910 931359038 343065489 981840058 521519661 226445599 530176715 770414408 102322476 673203111 507109164 694874631 741867637 279337383 424160545 294330405 82544373 48857855 815232637 669279005 52910855 214526933 849319059 181639810 172299266 889272850 596357056 666...

output:

318265902

result:

ok 1 number(s): "318265902"

Test #3:

score: 5
Accepted
time: 55ms
memory: 6976kb

input:

1000 906011316 702916476 1000
426378198 448666835 928428034 473805142 373675324 45261623 502895126 736498316 231472510 191865836 242418084 544276235 444104055 477445639 356224464 953908838 306690394 584707561 294817458 752251380 852722174 469468566 503286490 871710527 705395858 404720545 938309838 1...

output:

186621654

result:

ok 1 number(s): "186621654"

Test #4:

score: 5
Accepted
time: 1ms
memory: 3428kb

input:

100000 677812091 277 0
807583683

output:

71

result:

ok 1 number(s): "71"

Test #5:

score: 5
Accepted
time: 1ms
memory: 3444kb

input:

100000 981163973 25889 0
973863137

output:

12731

result:

ok 1 number(s): "12731"

Test #6:

score: 5
Accepted
time: 1ms
memory: 3504kb

input:

100000 835568175 7401731 0
906329707

output:

3064835

result:

ok 1 number(s): "3064835"

Test #7:

score: 5
Accepted
time: 1ms
memory: 3464kb

input:

1000000000 790947092 627519428 0
60710186

output:

272191242

result:

ok 1 number(s): "272191242"

Test #8:

score: 5
Accepted
time: 0ms
memory: 3500kb

input:

1000000000 650690291 731646919 0
877581470

output:

15529275

result:

ok 1 number(s): "15529275"

Test #9:

score: 5
Accepted
time: 1ms
memory: 3544kb

input:

1000000000 797047750 618934290 3
961481438 877843421 701730260 298899

output:

420699238

result:

ok 1 number(s): "420699238"

Test #10:

score: 5
Accepted
time: 0ms
memory: 3512kb

input:

1000000000 864318301 584940599 3
633737140 774981490 625591778 241085537

output:

198331859

result:

ok 1 number(s): "198331859"

Test #11:

score: 5
Accepted
time: 1ms
memory: 3512kb

input:

1000000000 848364348 882312605 4
170103640 631151726 271592928 185866004 334973069

output:

52190000

result:

ok 1 number(s): "52190000"

Test #12:

score: 5
Accepted
time: 1ms
memory: 3552kb

input:

1000000000 632003439 731204527 5
528931262 239172080 749520006 43675943 695916953 6562492

output:

614687549

result:

ok 1 number(s): "614687549"

Test #13:

score: 5
Accepted
time: 132ms
memory: 6984kb

input:

1000000000 1 766455601 1000
558055814 109246028 38835513 947196933 242586123 147273834 256441677 15594213 98941360 755103145 463954471 169688646 98806912 642927659 621211739 713955885 391698389 163712447 588561728 647301220 39465644 800390415 324148500 871577287 613523228 342178732 36750461 26345791...

output:

657791066

result:

ok 1 number(s): "657791066"

Test #14:

score: 5
Accepted
time: 135ms
memory: 6972kb

input:

1000000000 1 873712850 1000
278171983 164635568 206054551 341466272 947345526 592513430 491563677 341146136 935528892 632574736 565810285 515879482 994979438 164263680 189449944 440718937 492084059 497263419 573679235 699086245 659495381 975774703 586571408 481989509 489369682 258500183 253174606 94...

output:

357599008

result:

ok 1 number(s): "357599008"

Test #15:

score: 5
Accepted
time: 135ms
memory: 6988kb

input:

1000000000 1 801809934 1000
326406661 169791972 761656767 15280008 186815446 186117411 265403224 308467755 392051233 725260841 341791121 418439521 777844152 419969954 730027819 343615863 568299464 475588222 277121423 761476244 202455418 960116443 484950749 866814884 28710946 434807477 996165424 7697...

output:

762344818

result:

ok 1 number(s): "762344818"

Test #16:

score: 5
Accepted
time: 135ms
memory: 6920kb

input:

1000000000 1 605325981 1000
300766868 885995664 277533356 168649814 892768488 291744630 646838712 856019873 59320837 572912057 690027481 880187770 374756433 903619161 122904149 844522459 95811969 772786363 239314288 992117811 387289152 145852010 767518940 830315681 766920764 440439657 93192393 76897...

output:

58895801

result:

ok 1 number(s): "58895801"

Test #17:

score: 5
Accepted
time: 135ms
memory: 7000kb

input:

1000000000 957733823 809081300 1000
533363221 638929575 443006622 286508611 691905309 228596664 175904171 410178708 451046889 127797916 415935615 570618723 800660185 563213999 903523847 668436995 933625911 861427774 755608174 362042286 314119712 895203661 417507948 153273866 167248092 956338547 3406...

output:

674756796

result:

ok 1 number(s): "674756796"

Test #18:

score: 5
Accepted
time: 139ms
memory: 6964kb

input:

1000000000 610363186 847371151 1000
665297781 786213968 431288588 909998294 800117192 27065236 692646918 881650665 265579161 44215444 99633849 582605709 402479473 972764887 466468004 538706661 251804078 454620935 67255325 783865759 693395798 583174943 305918899 503101381 981809034 107696 736321655 4...

output:

634262459

result:

ok 1 number(s): "634262459"

Test #19:

score: 5
Accepted
time: 132ms
memory: 6960kb

input:

1000000000 534756891 543527658 1000
702340808 598102723 853329752 572034620 975329351 617733109 230679944 829852779 503128018 355746866 443120420 51627950 127579068 106567561 79644532 703345646 306545813 302226744 726078059 118130342 68034745 998675817 12288173 368910305 490224052 374647055 27100878...

output:

149744150

result:

ok 1 number(s): "149744150"

Test #20:

score: 5
Accepted
time: 139ms
memory: 6940kb

input:

1000000000 909107105 657355356 1000
90722426 58432815 680303429 656802978 821714069 81032229 404049008 508394045 815033128 537356713 111806335 80898026 295991237 78868790 550351734 549534112 766404863 359634541 285022912 417815753 284604425 900505912 411877558 12589604 66352005 634143645 90909857 16...

output:

236596968

result:

ok 1 number(s): "236596968"

Extra Test:

score: 0
Extra Test Passed