ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149743 | #286. 集合 | ympc2005 | 100 | 6759ms | 116572kb | C++11 | 1.3kb | 2022-07-22 09:08:45 | 2022-07-22 13:30:58 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10, mod = 998244353;
int n, m, x, fac[N], inv[N], val[N];
int fpow_(int a, int b, int res = 1) {
for (; b; b >>= 1, a = 1ll*a*a%mod) {
if (b&1) {
res = 1ll*res*a%mod;
}
}
return res;
}
int C_(int n, int k) {
if (n < k) {
return 0;
}
int res = inv[k];
for (int i = 0; i < k; i++) {
res = 1ll*res*(n - i)%mod;
}
return res;
}
int main() {
cin>>n>>m>>x;
if (x == 1) {
cout<<1<<'\n';
exit(0);
}
fac[0] = 1;
for (int i = 1; i <= m; i++) {
fac[i] = 1ll*fac[i - 1]*i%mod;
}
inv[m] = fpow_(fac[m], mod - 2);
for (int i = m; i; i--) {
inv[i - 1] = 1ll*inv[i]*i%mod;
}
val[0] = 1;
for (int i = 1; i <= m; i++) {
val[i] = 1ll*val[i - 1]*(n + 2 - i)%mod;
}
int ans = fpow_(x, n + 1);
for (int i = 0, y = 1; i < m; i++) {
ans = (ans - 1ll*y*val[i]%mod*inv[i])%mod;
y = 1ll*y*(x - 1)%mod;
}
ans = 1ll*ans*fpow_(fpow_(x - 1, mod - 2), m)%mod;
ans = (ans - C_(n, m - 1))%mod;
ans = 1ll*ans*fpow_(C_(n, m), mod - 2)%mod;
cout<<(ans%mod + mod)%mod<<'\n';
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 1208kb
input:
974358060 9789202 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 1204kb
input:
974374867 9782669 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 1204kb
input:
974391674 9257635 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 1208kb
input:
974408481 9732602 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 1208kb
input:
974425288 9207568 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 1208kb
input:
974442095 9682535 1
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 1208kb
input:
974458902 9157501 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 1204kb
input:
974475709 9632468 1
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 1204kb
input:
974492516 9625935 1
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 1204kb
input:
974509323 9100901 1
output:
1
result:
ok 1 number(s): "1"
Subtask #2:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 20ms
memory: 11240kb
input:
939830 855862 952890428
output:
769580874
result:
ok 1 number(s): "769580874"
Test #12:
score: 0
Accepted
time: 35ms
memory: 12268kb
input:
956637 943184 988243671
output:
729644598
result:
ok 1 number(s): "729644598"
Test #13:
score: 0
Accepted
time: 28ms
memory: 11680kb
input:
973444 893280 974942969
output:
376458332
result:
ok 1 number(s): "376458332"
Test #14:
score: 0
Accepted
time: 33ms
memory: 11980kb
input:
990251 918400 910471776
output:
601893966
result:
ok 1 number(s): "601893966"
Test #15:
score: 0
Accepted
time: 29ms
memory: 11592kb
input:
907057 885478 996995510
output:
279439643
result:
ok 1 number(s): "279439643"
Test #16:
score: 0
Accepted
time: 33ms
memory: 11704kb
input:
923864 894832 932524317
output:
754485259
result:
ok 1 number(s): "754485259"
Test #17:
score: 0
Accepted
time: 27ms
memory: 11288kb
input:
940671 859705 919223615
output:
735360983
result:
ok 1 number(s): "735360983"
Test #18:
score: 0
Accepted
time: 27ms
memory: 11940kb
input:
957478 915557 954576858
output:
846297917
result:
ok 1 number(s): "846297917"
Test #19:
score: 0
Accepted
time: 35ms
memory: 12400kb
input:
974285 954471 941276156
output:
519140979
result:
ok 1 number(s): "519140979"
Test #20:
score: 0
Accepted
time: 28ms
memory: 12468kb
input:
991092 960406 927975454
output:
393800468
result:
ok 1 number(s): "393800468"
Subtask #3:
score: 30
Accepted
Test #21:
score: 30
Accepted
time: 291ms
memory: 116572kb
input:
974694200 9844034 2
output:
717614679
result:
ok 1 number(s): "717614679"
Test #22:
score: 0
Accepted
time: 313ms
memory: 115984kb
input:
974727814 9793967 2
output:
903396834
result:
ok 1 number(s): "903396834"
Test #23:
score: 0
Accepted
time: 330ms
memory: 109836kb
input:
974744621 9268933 2
output:
293082936
result:
ok 1 number(s): "293082936"
Test #24:
score: 0
Accepted
time: 316ms
memory: 109756kb
input:
974761428 9262400 2
output:
568471499
result:
ok 1 number(s): "568471499"
Test #25:
score: 0
Accepted
time: 304ms
memory: 109172kb
input:
974795042 9212333 2
output:
174349571
result:
ok 1 number(s): "174349571"
Test #26:
score: 0
Accepted
time: 324ms
memory: 114740kb
input:
974811849 9687300 2
output:
54692201
result:
ok 1 number(s): "54692201"
Test #27:
score: 0
Accepted
time: 282ms
memory: 108584kb
input:
974828656 9162266 2
output:
178547426
result:
ok 1 number(s): "178547426"
Test #28:
score: 0
Accepted
time: 313ms
memory: 114152kb
input:
974845463 9637233 2
output:
848853881
result:
ok 1 number(s): "848853881"
Test #29:
score: 0
Accepted
time: 286ms
memory: 107920kb
input:
974879077 9105666 2
output:
939782679
result:
ok 1 number(s): "939782679"
Test #30:
score: 0
Accepted
time: 300ms
memory: 113488kb
input:
974895884 9580633 2
output:
341052536
result:
ok 1 number(s): "341052536"
Subtask #4:
score: 20
Accepted
Test #31:
score: 20
Accepted
time: 31ms
memory: 12348kb
input:
974912691 950001 982518805
output:
127609714
result:
ok 1 number(s): "127609714"
Test #32:
score: 0
Accepted
time: 29ms
memory: 12020kb
input:
974929498 922425 969218103
output:
988959503
result:
ok 1 number(s): "988959503"
Test #33:
score: 0
Accepted
time: 38ms
memory: 12868kb
input:
974946305 994850 904746910
output:
652493805
result:
ok 1 number(s): "652493805"
Test #34:
score: 0
Accepted
time: 28ms
memory: 12228kb
input:
974979919 939698 926799451
output:
297254489
result:
ok 1 number(s): "297254489"
Test #35:
score: 0
Accepted
time: 35ms
memory: 11904kb
input:
974996726 912122 913498749
output:
3872843
result:
ok 1 number(s): "3872843"
Test #36:
score: 0
Accepted
time: 34ms
memory: 12020kb
input:
975013533 922374 948851992
output:
824700719
result:
ok 1 number(s): "824700719"
Test #37:
score: 0
Accepted
time: 29ms
memory: 12868kb
input:
975030340 994799 935551290
output:
910283886
result:
ok 1 number(s): "910283886"
Test #38:
score: 0
Accepted
time: 33ms
memory: 12552kb
input:
975047147 967223 970904533
output:
524094901
result:
ok 1 number(s): "524094901"
Test #39:
score: 0
Accepted
time: 32ms
memory: 12224kb
input:
975063954 939647 957603831
output:
976518923
result:
ok 1 number(s): "976518923"
Test #40:
score: 0
Accepted
time: 39ms
memory: 11904kb
input:
975080761 912071 944303129
output:
671474890
result:
ok 1 number(s): "671474890"
Subtask #5:
score: 10
Accepted
Test #41:
score: 10
Accepted
time: 329ms
memory: 116040kb
input:
975097568 9798732 979656372
output:
511951684
result:
ok 1 number(s): "511951684"
Test #42:
score: 0
Accepted
time: 294ms
memory: 109892kb
input:
975114375 9273698 966355670
output:
258620932
result:
ok 1 number(s): "258620932"
Test #43:
score: 0
Accepted
time: 331ms
memory: 115456kb
input:
975131182 9748665 901884477
output:
680834727
result:
ok 1 number(s): "680834727"
Test #44:
score: 0
Accepted
time: 288ms
memory: 109224kb
input:
975164796 9217098 923937018
output:
420034109
result:
ok 1 number(s): "420034109"
Test #45:
score: 0
Accepted
time: 324ms
memory: 114796kb
input:
975181603 9692065 910636316
output:
969346798
result:
ok 1 number(s): "969346798"
Test #46:
score: 0
Accepted
time: 300ms
memory: 108640kb
input:
975198410 9167031 945989559
output:
153740899
result:
ok 1 number(s): "153740899"
Test #47:
score: 0
Accepted
time: 311ms
memory: 114204kb
input:
975215217 9641998 932688857
output:
617915726
result:
ok 1 number(s): "617915726"
Test #48:
score: 0
Accepted
time: 310ms
memory: 113616kb
input:
975248831 9591931 954741398
output:
414830040
result:
ok 1 number(s): "414830040"
Test #49:
score: 0
Accepted
time: 292ms
memory: 113544kb
input:
975265638 9585398 990094641
output:
300778334
result:
ok 1 number(s): "300778334"
Test #50:
score: 0
Accepted
time: 297ms
memory: 107388kb
input:
975282445 9060364 976793939
output:
153955626
result:
ok 1 number(s): "153955626"