QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#321982#7124. Binomial coefficientToboAC ✓70ms3704kbC++2011.7kb2024-02-06 00:16:222024-02-06 00:16:22

Judging History

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

  • [2024-02-06 00:16:22]
  • 评测
  • 测评结果：AC
  • 用时：70ms
  • 内存：3704kb
查看
  • [2024-02-06 00:16:22]
  • 提交

answer

#include <bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
using i64 = long long;
using u32 = unsigned int;
// using u64 = unsigned long long;
// using i128 = __int128_t;
using namespace std;
const int N = 2e5 + 5;
const int B = 3e6;
// const int M = 2e6 + 5;
// const int base = 13131;
// const int base = 17171;
// const int mod = 998244353;
// const int mod = 1e9 + 7;
// const i64 mod = 1000000000000000003LL;
// const double pi = acos(-1);

u32 num[1005] = {1, 658059649, 2459214593, 1493324929, 24266241, 2194962305, 1142483201,
                 472881793, 1376291841, 2626928001, 583085825, 2072043649, 2915226113, 813106049, 3935139073,
                 854992513, 3500218369, 4202580353, 1467857665, 4270812289, 1990417921, 3064565633,
                 630325505, 2588717697, 1539941377, 553178497, 281691905, 3257792641, 1007938049,
                 4117502849, 3576073473, 842219137, 3548524545, 4026753409, 782684929, 2791081089,
                 3725882881, 3435046785, 3645577473, 3668560513, 399162369, 1201532289, 2433965825,
                 2333806721, 1017446913, 480326529, 301966593, 1940936321, 144918529, 130578817,
                 403696385, 1349098625, 935693825, 3306405761, 1598304513, 3712410241, 2248922113,
                 277022081, 2744940289, 3595053185, 2943752705, 2786478977, 2702753025, 4151144065,
                 1879334913, 1103991169, 330892033, 4239832193, 2209785345, 2678642561, 3078441217,
                 2720266881, 2794253313, 2074615169, 1214615297, 2746564737, 2491888129, 2446025601,
                 2188498177, 3177875073, 161839105, 2652023169, 564271873, 2873347201, 3253190145,
                 1551757185, 3791020289, 692130433, 2035155969, 2299344257, 2137958145, 4083308673,
                 3956820481, 3753933697, 3054169345, 3316096641, 3582365697, 479707521, 1103835905,
                 1544610945, 4065908225, 4220716929, 3736041729, 1922968193, 4266597377, 951209345,
                 1220001537, 3310317697, 3043582465, 2415235969, 1004799233, 270841473, 3550980097,
                 3176978817, 1949584129, 253623425, 352972289, 2095587201, 2913505537, 2117812865,
                 898642945, 2325177729, 2755712769, 427591809, 4047141377, 2724899713, 335355137,
                 2632044161, 67682305, 2153902465, 3101516545, 3295351937, 704316929, 3766302593,
                 1323411713, 1276664449, 521227265, 2126282113, 2450124545, 4025065601, 2672529921,
                 387957633, 1045837057, 1809770113, 1722406913, 1705445761, 264665857, 2079861889,
                 824974849, 642928513, 3260727553, 3694490241, 3134350337, 354522497, 303236865,
                 1217837185, 3214715393, 3994344321, 3136244993, 2098986625, 4220186625, 1831608705,
                 2028966657, 902120577, 714946049, 1315399553, 135518465, 781355649, 148077569, 1304866177,
                 610017025, 595841153, 1378730497, 659157889, 2311611649, 3499693697, 3266054145,
                 2532391297, 4099451649, 4057095297, 374230529, 1488748417, 537719041, 1127195265,
                 152343553, 682345857, 3370465025, 2159077505, 1459542529, 3267300225, 2866904321,
                 1716924033, 3154976769, 3807793537, 2181153537, 2954851457, 4097795585, 1162975105,
                 172361985, 437041793, 3147148289, 2781928833, 4289613569, 1612578945, 3457151489,
                 3228836737, 507155713, 1045644929, 3886954497, 1362848129, 569039617, 1890356353,
                 3295706625, 338079617, 3334414593, 3005862529, 542557185, 3308647809, 3367462657,
                 3251312769, 3076590081, 543767425, 3822300417, 1485856385, 1167020033, 3787489665,
                 3558077185, 863609985, 2262930945, 3309029249, 1433942273, 243722881, 928504833,
                 2262502785, 604012289, 2780311681, 317858305, 3802026881, 4222403841, 3037558401,
                 3585107969, 2491783553, 2558331649, 4169579649, 999468545, 1485889409, 3060879617,
                 740557441, 10023937, 3938461057, 294229761, 199575681, 3770890753, 118713217,
                 1707465985, 1405783681, 2551283713, 1770697089, 1864770305, 3218330753, 3800286721,
                 3458594689, 3920259329, 201398913, 2082081793, 4041555329, 2438115073, 4099039361,
                 550785537, 2378728321, 572454145, 885499521, 2360514561, 1624230273, 1477393153,
                 2304830593, 2075450881, 637210497, 4012081409, 2921214593, 2849711105, 2571785601,
                 2740700929, 1593800833, 3542444545, 1992137601, 817368321, 1476705921, 3012800513,
                 2052383105, 1396200193, 1429079169, 119928321, 1611671425, 3336345857, 310069889,
                 2312911873, 3824119169, 1201987329, 1273794689, 4155933185, 3253908353, 2442208513,
                 3179402881, 213174273, 3055155585, 1621191425, 591076481, 2228686337, 2087010177,
                 1893052673, 957899393, 471684097, 3503588737, 2116941569, 3139020929, 2391251457,
                 1869073281, 1152007425, 1698623105, 2551570433, 337580417, 2152366849, 4085789825,
                 4106757633, 2063226753, 3977169153, 569735809, 1620995073, 1610194305, 1190596353,
                 2894512257, 2543366657, 2132599681, 1241732353, 1329333889, 1438054401, 2489592193,
                 2989726465, 3323284609, 1459174913, 1540321153, 998760705, 3440546433, 1465877505,
                 2438903169, 2717918977, 540268673,
                 317311489, 4044487553, 2711383297, 2071535233, 1167593473, 921256321, 4133270273,
                 2598528129, 2875872769, 518293377, 1547761921, 980396673, 6331393, 1694748033,
                 2403942145, 371257473, 8053249, 3309769601, 1265992961, 3925227137, 1740187649,
                 4222507393, 1288030977, 1911520385, 4061883905, 3292110721, 1329205505, 1779221121,
                 1537324033, 3672696193, 248665857,
                 2387478657, 1615591937, 4223413121, 1200528641, 2595442305, 3155836929, 3803410817,
                 3043943169, 1262261377, 722241025, 1271838593, 343091457, 1542052481, 1763888129,
                 4077780353, 547057409, 2293964929, 844960257, 2490450817, 2514990337,
                 2377148033, 1119574017, 3958933889, 811072257, 650751105, 1446878721, 3047411585,
                 2884387073, 268890753, 686023681, 2910000513, 3299116801, 90716289, 1991125505,
                 2405849985, 914410753, 3270344321, 4221333505, 394109313, 3179352833, 76989569,
                 1940829697, 28895105, 363157761, 2254703233, 2598697985, 169356673, 4209876737,
                 72700033, 759120385, 3969610625, 693757185, 980063873, 3871180801, 1698871681,
                 1558850305, 3835944065, 2204093953, 806223745,
                 1369338113, 3204522625, 3206943745, 150816129, 3279337217, 2239916161, 1443912193,
                 2886765441, 1853029633, 4096241281, 69115905, 3578253697, 244531969, 3337680001,
                 2236671489, 1084430209, 1607960833, 3118348929, 2510760961, 2854378881, 507498241,
                 2297397377, 4045500929, 3452281729, 97260801, 4028941953, 1405073409, 1737288065,
                 3531365121, 2877164673, 2038562305, 863514497, 1079025921, 1996182145, 510149633,
                 3985077633, 189327105, 245143681, 4268919297, 1371192193, 4016385281, 778165889,
                 3584086017, 470942081, 2829415169, 2454398081, 1609766401, 143476609, 4077500673,
                 4132989569, 1500077057,
                 3542912385, 2324823809, 378122369, 2114167297, 938464129, 725501185, 2933847681,
                 2311186433, 4074183041, 2433649409, 2069380225, 950283777, 3219283841, 2013450497,
                 938836609, 1185575937, 1527883137, 2619021057, 2696333441, 1876212225, 2154097537,
                 3109510401, 1906052737, 1881341953, 3957076353, 2344067841, 1722111105, 60114433,
                 1501001601, 3476809985, 1003657857, 3861613569, 2234957185, 1071918849, 2904809601,
                 3555054081, 723125121,
                 2578478337, 1989748353, 2294552577, 119622017, 2560670465, 1412590721, 3234225665,
                 3578564481, 4172611841, 32486017, 938255361, 1369167233, 1978484481, 1003550849,
                 2855725569, 940514177, 3427372289, 3184934529, 3550818305, 1151754625, 3083457281,
                 1140819073, 1882682881, 862037889, 4100856065, 2320288385, 1005435905, 3225480577,
                 1043750657, 1287524481, 4073193985, 2806264705, 1361224961, 1196643969, 1355171841,
                 2758506881, 3912428289, 906796161, 300453377, 1941356417, 3261542657, 3572097665,
                 4063155201, 3508929921, 2562684673, 3756730497, 2912492033, 2025409409, 675003649,
                 319843969, 2580481, 644911489, 752616193, 710521985, 2782504449, 2521552769,
                 1654671617, 3787913857, 1521478657, 2219515265, 2240319233, 4116201601, 3668587009,
                 2892915585, 1368708353, 554534529, 3788011521, 3400903041, 2193955585, 551996545,
                 738901505, 2602626945, 3575210241, 2967736961, 1970340865,
                 3652203905, 76654337, 2365937793, 2046511617, 1113815937, 3442339073,
                 1900715649, 4121530369, 2436546945, 3941479169, 431219841, 2759579137, 2184578945,
                 433223937, 1111566977, 1114774529, 3512028545, 366657281, 2800906369, 2341233153,
                 983077761, 2600928513, 63420033, 1003137025, 2046810497, 1700219649, 348191873,
                 254602753, 1267408769, 818647297, 2514371201, 3249746945, 1798989185, 3110328065,
                 1126140033, 257784321, 2500701057, 3139443969, 3632582273, 3022766081, 2231693697,
                 4060111617, 302912641, 1813906945, 4146083713, 436513025, 2881182337, 4080290817,
                 2808053121, 4012699393, 1636606081, 91132417, 1371718529, 762918145, 4018267777,
                 1590482945, 2991196545, 2431220481, 295382145, 3142524417, 2230669185, 3581788417,
                 2212000385, 3606406145, 2244253057, 3073771265, 37337217,
                 1841277441, 1891097473, 4061285633, 1220476545, 1001254913, 30351745, 1108513537,
                 325600385, 4240455169, 4111099777, 1664538881, 506825345, 1828092929, 107588993,
                 293543681, 623300737, 1213252097, 4058837889, 149644545, 3829143169, 1255081985,
                 1939093889, 91990785, 393567361, 812731905, 1197440897, 3274699009, 2060624513,
                 3040318465, 693028225, 4261951233, 3394496641, 2502023681, 3579972481,
                 1912896769, 3254333057, 2351964161, 127488385, 3676619521, 499283073, 1449289217,
                 2079627137, 4117301505, 2578430593, 2948115457, 4000570753, 2094092033, 4055957633, 1};
i64 n, k;
const u32 full = ((1ull << 32) - 1);
u32 inv(u32 x)
{
    u32 y = 1, now = x;
    for (int i = 1; i <= 31; i++)
        if (now >> i & 1)
            now += (x << i), y += (1ll << i);
    return y;
}
u32 cal(i64 n)
{
    n &= full;
    n = (n + 1) / 2;
    i64 t = n / B;
    u32 res = num[t];
    t *= B;
    for (i64 i = t + 1; i <= n; i++)
        res *= ((i - 1) * 2 + 1);
    return res;
}
u32 Fac(i64 n)
{
    u32 res = 1;
    while (n)
    {
        res *= cal(n);
        n >>= 1;
    }
    return res;
}
void solve()
{
    cin >> n >> k;
    int cnt2 = 0;
    for (int i = 0; i < 60; i++)
        cnt2 += (k >> i & 1) + ((n - k) >> i & 1) - (n >> i & 1);
    u32 ans = (i64)Fac(n) * inv(Fac(k)) * inv(Fac(n - k));
    for (int i = 1; i <= cnt2; i++)
        ans <<= 1;
    cout << ans << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    cout << fixed << setprecision(10);
    while (t--)
        solve();
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3632kb

input:

4 2

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 17ms
memory: 3560kb

input:

1000000000 500000000

output:

4209467392

result:

ok 1 number(s): "4209467392"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

1 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

9 5

output:

126

result:

ok 1 number(s): "126"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

4 4

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

4 1

output:

4

result:

ok 1 number(s): "4"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

8 0

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

7 4

output:

35

result:

ok 1 number(s): "35"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

5 1

output:

5

result:

ok 1 number(s): "5"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

10 5

output:

252

result:

ok 1 number(s): "252"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10 6

output:

210

result:

ok 1 number(s): "210"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

1 0

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

548 208

output:

550244848

result:

ok 1 number(s): "550244848"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

101 28

output:

3988840380

result:

ok 1 number(s): "3988840380"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

847 396

output:

111661020

result:

ok 1 number(s): "111661020"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

401 145

output:

4003233343

result:

ok 1 number(s): "4003233343"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

850 61

output:

541571168

result:

ok 1 number(s): "541571168"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

108 99

output:

2975642540

result:

ok 1 number(s): "2975642540"

Test #19:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

662 518

output:

1562442705

result:

ok 1 number(s): "1562442705"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

407 352

output:

1857174828

result:

ok 1 number(s): "1857174828"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

665 521

output:

3796194819

result:

ok 1 number(s): "3796194819"

Test #22:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

26 9

output:

3124550

result:

ok 1 number(s): "3124550"

Test #23:

score: 0
Accepted
time: 14ms
memory: 3552kb

input:

963837006 398758493

output:

2663079936

result:

ok 1 number(s): "2663079936"

Test #24:

score: 0
Accepted
time: 16ms
memory: 3632kb

input:

948507270 651192831

output:

1309671424

result:

ok 1 number(s): "1309671424"

Test #25:

score: 0
Accepted
time: 11ms
memory: 3640kb

input:

492986047 78933312

output:

2793371648

result:

ok 1 number(s): "2793371648"

Test #26:

score: 0
Accepted
time: 8ms
memory: 3704kb

input:

37464824 5920383

output:

181051392

result:

ok 1 number(s): "181051392"

Test #27:

score: 0
Accepted
time: 8ms
memory: 3608kb

input:

22135089 14539440

output:

3296657408

result:

ok 1 number(s): "3296657408"

Test #28:

score: 0
Accepted
time: 13ms
memory: 3620kb

input:

566613866 50184316

output:

3916726272

result:

ok 1 number(s): "3916726272"

Test #29:

score: 0
Accepted
time: 13ms
memory: 3616kb

input:

111092642 39294742

output:

569751552

result:

ok 1 number(s): "569751552"

Test #30:

score: 0
Accepted
time: 13ms
memory: 3640kb

input:

95762907 32448440

output:

2495508480

result:

ok 1 number(s): "2495508480"

Test #31:

score: 0
Accepted
time: 12ms
memory: 3616kb

input:

640241684 192946548

output:

1937432576

result:

ok 1 number(s): "1937432576"

Test #32:

score: 0
Accepted
time: 10ms
memory: 3644kb

input:

319645572 171079186

output:

2273689600

result:

ok 1 number(s): "2273689600"

Test #33:

score: 0
Accepted
time: 59ms
memory: 3644kb

input:

384118565739435739 279926992599854816

output:

0

result:

ok 1 number(s): "0"

Test #34:

score: 0
Accepted
time: 70ms
memory: 3592kb

input:

514630002561139050 342562804355107180

output:

2281701376

result:

ok 1 number(s): "2281701376"

Test #35:

score: 0
Accepted
time: 64ms
memory: 3688kb

input:

868513480532585464 620744630807193085

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 61ms
memory: 3640kb

input:

999024917354288774 174010839407941486

output:

0

result:

ok 1 number(s): "0"

Test #37:

score: 0
Accepted
time: 50ms
memory: 3556kb

input:

129536354175992084 40540657051530392

output:

2281701376

result:

ok 1 number(s): "2281701376"

Test #38:

score: 0
Accepted
time: 63ms
memory: 3680kb

input:

260047790997695395 184944531326445719

output:

1733853184

result:

ok 1 number(s): "1733853184"

Test #39:

score: 0
Accepted
time: 63ms
memory: 3636kb

input:

613931268969141809 232151379477837372

output:

0

result:

ok 1 number(s): "0"

Test #40:

score: 0
Accepted
time: 62ms
memory: 3604kb

input:

744442705790845119 697457906037415869

output:

0

result:

ok 1 number(s): "0"

Test #41:

score: 0
Accepted
time: 70ms
memory: 3688kb

input:

874954142612548430 747007213605125645

output:

0

result:

ok 1 number(s): "0"

Test #42:

score: 0
Accepted
time: 61ms
memory: 3644kb

input:

303530821616940606 71471793601986185

output:

0

result:

ok 1 number(s): "0"
English 繁體中文 简体中文

Server Time: 2024-12-02 20:13:55 | OpenSource Project