結果

問題 No.2383 Naphthol
ユーザー tailstails
提出日時 2023-07-19 17:35:25
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,998 bytes
コンパイル時間 839 ms
コンパイル使用メモリ 24,320 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 16:19:01
合計ジャッジ時間 1,064 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
6,812 KB
testcase_01 AC 0 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 0 ms
6,940 KB
testcase_05 AC 0 ms
6,944 KB
testcase_06 AC 0 ms
6,940 KB
testcase_07 AC 0 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 0 ms
6,940 KB
testcase_10 AC 0 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 0 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 0 ms
6,940 KB
testcase_16 AC 0 ms
6,940 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:72:17: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
   72 |                 write(1,k==2||k==3||k==4?"3":"1",1);
      |                 ^~~~~
main.c:82:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
   82 |         _exit(0);
      |         ^~~~~
main.c:82:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({long _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define wt(v) ({ulong _z=v;do*--wp=_z%10+48;while(_z/=10);})
#define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);})
#define MD 998244353

typedef unsigned long ulong;

ulong fac(ulong n){
	static unsigned const fac8[]={
        1,941747501,776540593,210672823,690071003, 46617525,213768760,693968959,
 80489582,706932617,794151417,465499254,696674125,679081391,691448896,713797428,
275558954,609927147,557311239,831274938,893291440,167105676,415665360,192812445,
680052439,557094195,688128904,792752264,192208002,847923750, 28263099,728717984,
491684840,336918851,633366503,758306641,296930470,699020919,910172402,905192639,
792232676,535935445,410591335,810793504,856039476,765650325,702144816,374640872,
197994359,320889851,883115987,151590670,245098264,286989423,729221238,511226407,
874957813,979489918,228248737,453190470,223927796,852989243, 50287712,509033048,
243625084, 40159580,655302994,829942035,299277458, 86622874,109276119, 75894103,
424113548,567421291,676588086,620367716,815463188, 44143218,810930880,   499782,
416513770, 59750787,280879191,113328955,910641127,542089438,873391271, 49111081,
422655771,749741439,838916518,825928836,422316600,445140078,135792920,796315921,
334523653,505750213,745454889,284439669,264422227,488144299,264594887,332021570,
256723915,768304408,506153085,533770970,929732704,471614028,243021423, 36822049,
195608626,792193516,215245367,588445499, 10232161,974583034,843169718, 33517339,
744867256,422042779,971678608,929209828,740055526,129980885,404829672,225807005,
528205456,240143253,706174821,263068586,794757329,221639463,240967815, 20047837,
331134934,127470054,793695956,210565051,959206504,138448490,667121261,136048183,
226620404,692730832,887464126,715216840,786895056,680299255,592465564,104271019,
241786040,302567286,781777622,695362768,267443112, 60985765,733684226,937002588,
298149860,170166008,805749567, 79282620,437665466,386653062,754588014,265310082,
 81266867,109466639,595236940,591251736,755288980,912652888,460141120,759221877,
825572784, 18194464,368427783,571463817,553552793,218414240,  8897606,791219964,
987232136,626678298,363848504, 23298153,623570515,506916981,151639897,269752482,
341219264,108067268,360379612,245950594,
	};
	ulong z=fac8[n>>10];
	for(;n&1023;--n){
		z=z*n%MD;
	}
	return z;
}

int inverse(int a){
	int b=MD;
	int u=1;
	int v=0;
	int s,t;
	while(b){
		t=a/b;
		s=b; b=a-t*b; a=s;
		s=v; v=u-t*v; u=s;
	}
	if(u<0){
		u+=MD;
	}
	return u;
}

ulong c(ulong n,ulong r){
	return fac(n)*inverse(fac(n-r)*fac(r)%MD);
}

int main(){
	rd_init();
	ulong n=rd();
	ulong k=rd();
	if(n==1){
		write(1,k==2||k==3||k==4?"3":"1",1);
	}else{
		ulong z=c(n*2+4,k);
		if(~k&1){
			z+=c(n+2,k/2)*3;
		}else if(n&1){
			z+=c(n+1,k/2)*2;
		}
		wt1(z%MD*748683265%MD);
	}
	_exit(0);
}
0