kmjp's blog

競技プログラミング参加記です

yukicoder : No.685 Logical Operations

本番なかなか解が合わず手間取った。
https://yukicoder.me/problems/no/685

問題

正整数Nが与えられる。
(x,y)の整数対のうち、0≦x≦y≦Nかつ(x and y)<(x xor y)<(x or y)を満たすものは何通りあるか。

解法

x,yが1bitの場合、不等号を満たす条件を考える。
(x and y)<(x xor y)が生じるのは、x!=yの場合である。
そこでx≦yという条件で考えると、yの最上位ビットにおいて、xの同じビットが0であればよい。

つぎに(x xor y)<(x or y)が生じるのはx=y=1の場合のみである。
yの最上位ビットと同じ位置においてxのビットは0であることは確定しているので、それより下のビットでx=y=1となる箇所が1か所でもあれば、以下のビットはなんであれ条件を満たす。

この2つの考察を元に、DPなりメモ化再帰で上のビットから決めていくことを考えよう。
yについて以下0/1任意の値を取れるか、もしくは「N以下」の条件により0/1の値が制限されるかを考慮しつつ、桁DPでx,yに0/0,0/1,1/0,1/1の値を取ったときの遷移を考えていく。

ll N;
ll mo=1000000007;

map<ll,ll> M[2],R[2];

ll hoge2(ll a,int lead) {
	if(a==0) return 0;
	if(R[lead].count(a)) return R[lead][a];
	ll ret=0;
	
	if(lead==1) {
		if(N&a) {
			// 11
			ret+=((N&(a-1))+1)%mo*(a%mo)%mo;
			// 10
			ret+=hoge2(a>>1,1);
			// 00,01
			ret+=2*hoge2(a>>1,0);
		}
		else {
			// 00,01
			ret+=2*hoge2(a>>1,1);
		}
	}
	else {
		// 11
		ret+=a%mo*(a%mo)%mo;
		// 10,01,00
		ret+=3*hoge2(a>>1,0);
	}
	
	//cout<<"R"<<lead<<" "<<a<<" "<<ret%mo<<endl;
	return R[lead][a]=ret%mo;
}


ll hoge1(ll a,int lead) {
	if(a==0) return 0;
	if(M[lead].count(a)) return M[lead][a];
	ll ret=0;
	
	if(lead==1) {
		if(N&a) {
			// 10
			ret+=hoge2(a>>1,1);
			// 00
			ret+=hoge1(a>>1,0);
		}
		else {
			// 00
			ret+=hoge1(a>>1,1);
		}
	}
	else {
		// 00
		ret+=hoge1(a>>1,0);
		// 10
		ret+=hoge2(a>>1,0);
	}
	//cout<<"M"<<lead<<" "<<a<<" "<<ret%mo<<endl;
	return M[lead][a]=ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cout<<hoge1(1LL<<60,1)<<endl;
	return;
	ll ret=0;
	for(i=1;i<=N;i++) {
		for(y=1;2*y<=i;y<<=1) if(i&y) ret+=y;
		cout<<ret<<endl;
	}
	cout<<ret<<endl;
	for(y=0;y<=N;y++) {
		int num=0;
		for(x=0;x<=y;x++) {
			if((x&y)<(x^y) && (x^y)<(x|y)) {
				//cout<<x<<" "<<y<<"   "<<(x&y)<<" "<<(x^y)<<" "<<(x|y)<<endl;
				num++;
			}
		}
		cout<<y<<" "<<num<<" "<<__builtin_popcount(y)<<endl;
	}
}

まとめ

桁DP系、ほんと説明がめんどい。