QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168319#7124. Binomial coefficientCrysflyAC ✓74ms3820kbC++179.2kb2023-09-08 09:26:412023-09-08 09:26:42

Judging History

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

  • [2023-09-08 09:26:42]
  • 评测
  • 测评结果:AC
  • 用时:74ms
  • 内存:3820kb
  • [2023-09-08 09:26:41]
  • 提交

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"