Codeforces #997 : Div2 F2. Xor of Median (Hard Version)

意外にコードが短い
https://codeforces.com/contest/2056/problem/F2

問題

整数列Aが良いとは、以下の条件を満たすものとする。

• 2値i,jがともにAに現れる場合、i＜jならAに現れる頻度もiの方が少ない。

巨大な整数Nと、Mが与えられる。
N要素の数列Aのうち、各要素が0～(M-1)のいずれかを取るもので良い整数列に対し、中央値のxorを答えよ。

解法

求めるのはxorなので、並べ替え方が偶数通りあるようなものは解に寄与しない。
また、Lucasの定理より、Nの2進数表記のうち、各bitは、Aの各値の登場頻度に対応づく。
このうちMSBに対応づく値は当然ながらA中で最多頻度となるため、中央値にもなる。

よって、Nのうち2進数表記で立っているbitがn個あり、Aにm通りの値が登場するとすると、そのようなm通りの選び方は第2種スターリング数の要領で計算できる。
また、第2種スターリング数の偶奇は簡単な式で計算できる。

あとはmを総当たりしよう。

int T,K,M;
string S;
int dp[1<<20];

//第2種スターリング数の偶奇
//https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
int stirling2_odd(ll n,ll r) {
	return ((n-r)&((r-1)/2))==0;
}

int lucas(ll N,ll K) { // C(N,K)の偶奇
	if(K<0 || K>N) return 0;
	return ((~N)&K)==0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>K>>M>>S;
		// bit数
		int n=count(ALL(S),'1');
		int nl=__lg(n)+1;
		int n2=1<<nl;
		FOR(i,n2) dp[i]=0;
		FOR(i,n) dp[i]=stirling2_odd(n,i+1);
		FOR(i,nl) FOR(j,n2) if(j&(1<<i)) dp[j]^=dp[j^(1<<i)];
		
		int ret=0;
		FOR(i,min(n2,M)) if(dp[i]) {
			int num=(M-1-i)>>nl;
			if((num&1)==0) ret^=i;
			if(num%4==0) ret^=num<<nl;
			if(num%4==1) ret^=1<<nl;
			if(num%4==2) ret^=(num+1)<<nl;
		}
		/*
		//数
		for(i=1;i<=min(n,M);i++) if(stirling2_odd(n,i)) {
			for(int j=i-1;j<M;j++) if(lucas(j,i-1)) ret^=j;
		}
		*/
		cout<<ret<<endl;
	
	}
}

まとめ

スターリング数の偶奇の計算方法知らなかった。