yukicoder : No.1410 A lot of Bit Operations

これも考察重め？
https://yukicoder.me/problems/no/1410

問題

S[i]という演算子は、2つのブール値を取り、ブール値を返す演算子を示す。
入力が4通りあるが、S[0]～S[15]でそれぞれの出力パターン2^4通りを列挙している。

指定されたいくつかのiに対し、以下の和を答えよ。

• 整数Nが与えられる。2^N未満の非負整数(P,Q,R)のうち、((P S[i] Q)-R)*((P S[15-i] Q)-R)が0以下

解法

P,Qを定めると、Rが(P S[i] Q)と(P S[15-i] Q)の区間内に含まれれば条件を満たす。
(P S[i] Q)と(P S[15-i] Q)はちょうど各ビット反転した値となるので、最上位bitは片方が1、片方は0となる。
あとは最上位bit以外で各ビットが0,1になるケースを数え上げて行く。

ll N;
string K;
const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll ret=0;
	FOR(i,8) if(K[i]=='o') {
		if(N==0) {
			ret++;
		}
		else {
			x=__builtin_popcount(i)-__builtin_popcount(15-i);
			ret+=modpow(2,2*N)+modpow(2,3*N-1);
			if(N>=2) {
				(ret+=x*x*modpow(2,2*N-4)%mo*(modpow(2,N-1)-1))%=mo;
			}
			
		}
	}
	cout<<ret%mo<<endl;
}

まとめ

問題設定が不自然なので、余り好きなタイプの問題ではないな…。