QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#168319 | #7124. Binomial coefficient | Crysfly | AC ✓ | 74ms | 3820kb | C++17 | 9.2kb | 2023-09-08 09:26:41 | 2023-09-08 09:26:42 |
Judging History
answer
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
typedef unsigned int ui;
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,k;
ui inv(ui x){
ui y=1,now=x;
For(i,1,31)
if(now>>i&1) now+=(x<<i),y+=(1ll<<i);
return y;
}
ui qp(ui x,int y){
ui res=1;
while(y){
if(y&1)res*=x;
x*=x,y>>=1;
}
return res;
}
int B=3000000;
const ui tab[1145141]={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};
ui calc(int n){
n&=((1ull<<32)-1);
n=(n+1)/2;
int t=n/B; ui res=tab[t];
t*=B; For(i,t+1,n) res*=((i-1)*2+1);
return res;
}
ui Fac(int n){
int nn=n;
ui res=1;
while(n){
res*=calc(n);
n/=2;
}
return res;
}
signed main()
{
// freopen("tab.out","w",stdout);
// ui V=-1;
// cout<<"const ui tab[1145141]={1,";
// ui now=1;
// For(i,1,2147483648){
// now*=((i-1)*2+1);
// if(i%B==0)cout<<now<<",";
// }
// cout<<now<<"};\n";
n=read(),k=read();
int pws=0;
For(i,0,62)
pws+=(k>>i&1)+((n-k)>>i&1)-(n>>i&1);
if(pws>32){
puts("0");
exit(0);
}
ui res=Fac(n)*inv(Fac(k))*inv(Fac(n-k));
For(i,1,pws) res*=2;
cout<<res;
return 0;
}
/*
1
11
101
1111
10001
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3716kb
input:
4 2
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 13ms
memory: 3600kb
input:
1000000000 500000000
output:
4209467392
result:
ok 1 number(s): "4209467392"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
9 5
output:
126
result:
ok 1 number(s): "126"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
4 4
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
4 1
output:
4
result:
ok 1 number(s): "4"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
8 0
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
7 4
output:
35
result:
ok 1 number(s): "35"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
5 1
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
10 5
output:
252
result:
ok 1 number(s): "252"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
10 6
output:
210
result:
ok 1 number(s): "210"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
548 208
output:
550244848
result:
ok 1 number(s): "550244848"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
101 28
output:
3988840380
result:
ok 1 number(s): "3988840380"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
847 396
output:
111661020
result:
ok 1 number(s): "111661020"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
401 145
output:
4003233343
result:
ok 1 number(s): "4003233343"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
850 61
output:
541571168
result:
ok 1 number(s): "541571168"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
108 99
output:
2975642540
result:
ok 1 number(s): "2975642540"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
662 518
output:
1562442705
result:
ok 1 number(s): "1562442705"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
407 352
output:
1857174828
result:
ok 1 number(s): "1857174828"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
665 521
output:
3796194819
result:
ok 1 number(s): "3796194819"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
26 9
output:
3124550
result:
ok 1 number(s): "3124550"
Test #23:
score: 0
Accepted
time: 10ms
memory: 3652kb
input:
963837006 398758493
output:
2663079936
result:
ok 1 number(s): "2663079936"
Test #24:
score: 0
Accepted
time: 16ms
memory: 3820kb
input:
948507270 651192831
output:
1309671424
result:
ok 1 number(s): "1309671424"
Test #25:
score: 0
Accepted
time: 8ms
memory: 3712kb
input:
492986047 78933312
output:
2793371648
result:
ok 1 number(s): "2793371648"
Test #26:
score: 0
Accepted
time: 5ms
memory: 3716kb
input:
37464824 5920383
output:
181051392
result:
ok 1 number(s): "181051392"
Test #27:
score: 0
Accepted
time: 5ms
memory: 3636kb
input:
22135089 14539440
output:
3296657408
result:
ok 1 number(s): "3296657408"
Test #28:
score: 0
Accepted
time: 14ms
memory: 3604kb
input:
566613866 50184316
output:
3916726272
result:
ok 1 number(s): "3916726272"
Test #29:
score: 0
Accepted
time: 13ms
memory: 3720kb
input:
111092642 39294742
output:
569751552
result:
ok 1 number(s): "569751552"
Test #30:
score: 0
Accepted
time: 10ms
memory: 3796kb
input:
95762907 32448440
output:
2495508480
result:
ok 1 number(s): "2495508480"
Test #31:
score: 0
Accepted
time: 13ms
memory: 3740kb
input:
640241684 192946548
output:
1937432576
result:
ok 1 number(s): "1937432576"
Test #32:
score: 0
Accepted
time: 14ms
memory: 3796kb
input:
319645572 171079186
output:
2273689600
result:
ok 1 number(s): "2273689600"
Test #33:
score: 0
Accepted
time: 55ms
memory: 3736kb
input:
384118565739435739 279926992599854816
output:
0
result:
ok 1 number(s): "0"
Test #34:
score: 0
Accepted
time: 74ms
memory: 3732kb
input:
514630002561139050 342562804355107180
output:
2281701376
result:
ok 1 number(s): "2281701376"
Test #35:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
868513480532585464 620744630807193085
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
999024917354288774 174010839407941486
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 46ms
memory: 3756kb
input:
129536354175992084 40540657051530392
output:
2281701376
result:
ok 1 number(s): "2281701376"
Test #38:
score: 0
Accepted
time: 67ms
memory: 3660kb
input:
260047790997695395 184944531326445719
output:
1733853184
result:
ok 1 number(s): "1733853184"
Test #39:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
613931268969141809 232151379477837372
output:
0
result:
ok 1 number(s): "0"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
744442705790845119 697457906037415869
output:
0
result:
ok 1 number(s): "0"
Test #41:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
874954142612548430 747007213605125645
output:
0
result:
ok 1 number(s): "0"
Test #42:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
303530821616940606 71471793601986185
output:
0
result:
ok 1 number(s): "0"