UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#149743#286. 集合ympc20051006759ms116572kbC++111.3kb2022-07-22 09:08:452022-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';
}   

Details

小提示:点击横条可展开更详细的信息

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"