yukicoder : No.1426 Got a Covered OR

物語部分、何か元ネタがあるのかな。
https://yukicoder.me/problems/no/1426

問題

整数列Bが与えられる。
B[i]は未指定か指定であり、指定の場合A[0]～A[i]のORの値が取られる。

Bを構築するような正整数列Aは何通りか。

解法

Aが正というのが厄介。
B[i]=-1である領域を無視し、

• B[x]!=-1
• B[y]!=-1
• B[x+1]～B[y-1]=-1

となる(x,y)のペア毎に考える。

• B[x]で0、B[y]で0となるビットは、A[x+1]～A[y]のどこでも0
• B[x]で0、B[y]で1となるビットは、A[x+1]～A[y]のどこかで1が立たなければならない
• B[x]で1、B[y]で1となるビットは、A[x+1]～A[y]値は任意

あとはA[i]=0が許可されないため、包除原理の要領でA[i]=0となるiの個数を総当たりしながら、上記を満たすA[x+1]～A[y]の組み合わせを数え上げよう。

int N;
int B[101010];
const ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

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;
	FOR(i,N) cin>>B[i+1];
	
	ll ret=1;
	int pre=0;
	for(i=1;i<=N;i++) if(B[i]!=-1) {
		int C[2][2]={};
		FOR(j,30) {
			C[(B[pre]>>j)&1][(B[i]>>j)&1]++;
		}
		
		if(C[1][0]) {
			ret=0;
		}
		else {
			x=C[0][1];
			y=C[1][1];
			ll pat=0;
			FOR(j,x+1) {
				ll p=comb(x,j)*modpow((1LL<<(x+y-j))-1,i-pre)%mo;
				if(j%2==1) {
					pat+=mo-p;
				}
				else {
					pat+=p;
				}
			}
			ret=ret*(pat%mo)%mo;
		}
		
		pre=i;
	}
	
	cout<<ret<<endl;
	
}

まとめ

yukicoderも記事にしてない問題が溜まってきたな…。
典型90は公式解説もあるし書かなくていいか。