QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#114921 | #6157. 组合数问题 | nhuang685 | 100 ✓ | 139ms | 7028kb | C++20 | 4.1kb | 2023-06-24 03:57:08 | 2023-06-24 03:57:09 |
Judging History
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