#985876 (cLay) No.2772 Appearing Even Times

• 問題: No.2772 Appearing Even Times
• ユーザー: tails
• 提出日時: 2024-06-05 12:17:22
• 言語: cLay (20240420-1)
• 結果: AC
• 実行時間: 2 ms / 4,000 ms
• コード長: 687 bytes
• コンパイル時間: 4,829 ms
• コンパイル使用メモリ: 177,004 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-05 12:17:29
• 合計ジャッジ時間: 6,115 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB

ソースコード

#define MD 998244353
string@n;
ll l=n.size();
unsigned b=0;
rep(i,l){
	int c=n[i]-'0';
	b^=1<<c;
}
int a=__builtin_popcount(b);
Mint d[11]{1},f[11]{1},g=Mint(9)/10,z=!b-g;
rep(k,1,11){
	f[k]=f[k-1]*k/(11-k);
}
rrep(i,l){
	int c=n[i]-'0';
	a+=b&1<<c?-1:1;
	b^=1<<c;
	if(~l&1){
		int a0=0,a1=0;
		rep(j,!i,c){
			(b&1<<j?a1:a0)+=1;
		}
		if(a){
			z+=d[a-1]*f[a-1]*a1;
		}
		if(a<10){
			z+=d[a+1]*f[a+1]*a0;
		}
	}
	if(l-i&1){
		z+=d[0]*g;
		d[1]=d[0]*10+d[2]*2;
		d[3]=d[2]*8+d[4]*4;
		d[5]=d[4]*6+d[6]*6;
		d[7]=d[6]*4+d[8]*8;
		d[9]=d[8]*2+d[10]*10;
	}else{
		d[0]=d[1];
		d[2]=d[1]*9+d[3]*3;
		d[4]=d[3]*7+d[5]*5;
		d[6]=d[5]*5+d[7]*7;
		d[8]=d[7]*3+d[9]*9;
		d[10]=d[9];
	}
}
wt(z);