UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149803#286. 集合dcyt1009470ms234364kbC++111.8kb2022-07-22 11:53:572022-07-22 13:34:28

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define fi first
#define se second
 
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
 
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

const int N = 1e7 + 5;
const ll P = 998244353;

ll qpow(ll a, ll b)
{
    ll res = 1;
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1) res = res * a % P;
    return res;
}

ll fac[N], ivf[N];

void init(int n)
{
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % P;
    ivf[n] = qpow(fac[n], P - 2);
    for (int i = n - 1; i >= 0; i--)
        ivf[i] = ivf[i + 1] * (i + 1) % P;
}

ll C(int n, int m)
{
    return n < m ? 0 : fac[n] * ivf[m] % P * ivf[n - m] % P;
}

ll n, t;
int k;

ll ans[N];

int main()
{
    init(1e7);
    scanf("%lld%d%lld", &n, &k, &t);
    if (t == 1)
    {
        puts("1");
        return 0;
    }
    ll it1 = qpow((t + P - 1) % P, P - 2);
    ans[1] = (qpow(t, n + 1) + P - t) % P * it1 % P;
    ll C = n, C1 = 1, C2 = 1;
    for (int i = 2; i <= k; i++)
    {
        ll c1 = 0, c2 = 0;
        if (n >= i) C = C * (n - i + 1) % P;
        else C = 0;
        if (n - 1 >= i - 1) c1 = C1 = C1 * ((n - 1) - (i - 1) + 1) % P;
        else C1 = 0;
        if (i == 2) c2 = 1;
        else if (n - 1 >= i - 2) c2 = C2 = C2 * ((n - 1) - (i - 2) + 1) % P;
        else C2 = 0;
        c1 = c1 * ivf[i - 1] % P;
        c2 = c2 * ivf[i - 2] % P;
        ans[i] = (ans[i - 1] + (P - c1) * t % P + (P - c2) * t % P) % P * it1 % P;
    }
    C = C * ivf[k] % P;
    printf("%lld\n", ans[k] * qpow(C, P - 2) % P);
}

详细

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

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 103ms
memory: 157436kb

input:

974358060 9789202 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 109ms
memory: 157436kb

input:

974374867 9782669 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 123ms
memory: 157436kb

input:

974391674 9257635 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 105ms
memory: 157440kb

input:

974408481 9732602 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 102ms
memory: 157436kb

input:

974425288 9207568 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 111ms
memory: 157440kb

input:

974442095 9682535 1

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 126ms
memory: 157440kb

input:

974458902 9157501 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 139ms
memory: 157436kb

input:

974475709 9632468 1

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 111ms
memory: 157440kb

input:

974492516 9625935 1

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 113ms
memory: 157436kb

input:

974509323 9100901 1

output:

1

result:

ok 1 number(s): "1"

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 132ms
memory: 164140kb

input:

939830 855862 952890428

output:

769580874

result:

ok 1 number(s): "769580874"

Test #12:

score: 0
Accepted
time: 131ms
memory: 164824kb

input:

956637 943184 988243671

output:

729644598

result:

ok 1 number(s): "729644598"

Test #13:

score: 0
Accepted
time: 111ms
memory: 164436kb

input:

973444 893280 974942969

output:

376458332

result:

ok 1 number(s): "376458332"

Test #14:

score: 0
Accepted
time: 132ms
memory: 164632kb

input:

990251 918400 910471776

output:

601893966

result:

ok 1 number(s): "601893966"

Test #15:

score: 0
Accepted
time: 112ms
memory: 164376kb

input:

907057 885478 996995510

output:

279439643

result:

ok 1 number(s): "279439643"

Test #16:

score: 0
Accepted
time: 120ms
memory: 164448kb

input:

923864 894832 932524317

output:

754485259

result:

ok 1 number(s): "754485259"

Test #17:

score: 0
Accepted
time: 134ms
memory: 164176kb

input:

940671 859705 919223615

output:

735360983

result:

ok 1 number(s): "735360983"

Test #18:

score: 0
Accepted
time: 132ms
memory: 164608kb

input:

957478 915557 954576858

output:

846297917

result:

ok 1 number(s): "846297917"

Test #19:

score: 0
Accepted
time: 143ms
memory: 164916kb

input:

974285 954471 941276156

output:

519140979

result:

ok 1 number(s): "519140979"

Test #20:

score: 0
Accepted
time: 160ms
memory: 164956kb

input:

991092 960406 927975454

output:

393800468

result:

ok 1 number(s): "393800468"

Subtask #3:

score: 30
Accepted

Test #21:

score: 30
Accepted
time: 371ms
memory: 234364kb

input:

974694200 9844034 2

output:

717614679

result:

ok 1 number(s): "717614679"

Test #22:

score: 0
Accepted
time: 377ms
memory: 233972kb

input:

974727814 9793967 2

output:

903396834

result:

ok 1 number(s): "903396834"

Test #23:

score: 0
Accepted
time: 278ms
memory: 229872kb

input:

974744621 9268933 2

output:

293082936

result:

ok 1 number(s): "293082936"

Test #24:

score: 0
Accepted
time: 288ms
memory: 229820kb

input:

974761428 9262400 2

output:

568471499

result:

ok 1 number(s): "568471499"

Test #25:

score: 0
Accepted
time: 253ms
memory: 229424kb

input:

974795042 9212333 2

output:

174349571

result:

ok 1 number(s): "174349571"

Test #26:

score: 0
Accepted
time: 281ms
memory: 233136kb

input:

974811849 9687300 2

output:

54692201

result:

ok 1 number(s): "54692201"

Test #27:

score: 0
Accepted
time: 313ms
memory: 229040kb

input:

974828656 9162266 2

output:

178547426

result:

ok 1 number(s): "178547426"

Test #28:

score: 0
Accepted
time: 314ms
memory: 232744kb

input:

974845463 9637233 2

output:

848853881

result:

ok 1 number(s): "848853881"

Test #29:

score: 0
Accepted
time: 252ms
memory: 228596kb

input:

974879077 9105666 2

output:

939782679

result:

ok 1 number(s): "939782679"

Test #30:

score: 0
Accepted
time: 259ms
memory: 232308kb

input:

974895884 9580633 2

output:

341052536

result:

ok 1 number(s): "341052536"

Subtask #4:

score: 20
Accepted

Test #31:

score: 20
Accepted
time: 125ms
memory: 164880kb

input:

974912691 950001 982518805

output:

127609714

result:

ok 1 number(s): "127609714"

Test #32:

score: 0
Accepted
time: 129ms
memory: 164660kb

input:

974929498 922425 969218103

output:

988959503

result:

ok 1 number(s): "988959503"

Test #33:

score: 0
Accepted
time: 136ms
memory: 165232kb

input:

974946305 994850 904746910

output:

652493805

result:

ok 1 number(s): "652493805"

Test #34:

score: 0
Accepted
time: 128ms
memory: 164800kb

input:

974979919 939698 926799451

output:

297254489

result:

ok 1 number(s): "297254489"

Test #35:

score: 0
Accepted
time: 112ms
memory: 164584kb

input:

974996726 912122 913498749

output:

3872843

result:

ok 1 number(s): "3872843"

Test #36:

score: 0
Accepted
time: 128ms
memory: 164660kb

input:

975013533 922374 948851992

output:

824700719

result:

ok 1 number(s): "824700719"

Test #37:

score: 0
Accepted
time: 138ms
memory: 165228kb

input:

975030340 994799 935551290

output:

910283886

result:

ok 1 number(s): "910283886"

Test #38:

score: 0
Accepted
time: 137ms
memory: 165012kb

input:

975047147 967223 970904533

output:

524094901

result:

ok 1 number(s): "524094901"

Test #39:

score: 0
Accepted
time: 116ms
memory: 164800kb

input:

975063954 939647 957603831

output:

976518923

result:

ok 1 number(s): "976518923"

Test #40:

score: 0
Accepted
time: 170ms
memory: 164580kb

input:

975080761 912071 944303129

output:

671474890

result:

ok 1 number(s): "671474890"

Subtask #5:

score: 10
Accepted

Test #41:

score: 10
Accepted
time: 305ms
memory: 234008kb

input:

975097568 9798732 979656372

output:

511951684

result:

ok 1 number(s): "511951684"

Test #42:

score: 0
Accepted
time: 263ms
memory: 229904kb

input:

975114375 9273698 966355670

output:

258620932

result:

ok 1 number(s): "258620932"

Test #43:

score: 0
Accepted
time: 299ms
memory: 233616kb

input:

975131182 9748665 901884477

output:

680834727

result:

ok 1 number(s): "680834727"

Test #44:

score: 0
Accepted
time: 288ms
memory: 229464kb

input:

975164796 9217098 923937018

output:

420034109

result:

ok 1 number(s): "420034109"

Test #45:

score: 0
Accepted
time: 249ms
memory: 233172kb

input:

975181603 9692065 910636316

output:

969346798

result:

ok 1 number(s): "969346798"

Test #46:

score: 0
Accepted
time: 273ms
memory: 229072kb

input:

975198410 9167031 945989559

output:

153740899

result:

ok 1 number(s): "153740899"

Test #47:

score: 0
Accepted
time: 247ms
memory: 232788kb

input:

975215217 9641998 932688857

output:

617915726

result:

ok 1 number(s): "617915726"

Test #48:

score: 0
Accepted
time: 289ms
memory: 232392kb

input:

975248831 9591931 954741398

output:

414830040

result:

ok 1 number(s): "414830040"

Test #49:

score: 0
Accepted
time: 267ms
memory: 232340kb

input:

975265638 9585398 990094641

output:

300778334

result:

ok 1 number(s): "300778334"

Test #50:

score: 0
Accepted
time: 236ms
memory: 228240kb

input:

975282445 9060364 976793939

output:

153955626

result:

ok 1 number(s): "153955626"