Codeforces #788 : Div2 F. Jee, You See?

正答者の多かった回。
https://codeforces.com/contest/1670/problem/F

問題

整数N,L,R,Zが与えられる。

N要素の非負整数列Aのうち、総和がL以上R未満で、xorがZとなるものは何通りか。

解法

2進数で下位の桁から0/1を合わせていこう。
各桁で1となる要素数を0～1総当たりしていけばよい。
その際繰り上がりは高々Nまで考えればよいので、O(N^2*log(Z))程度で解ける。

ll N;
ll L,R,Z;

ll dp[100][1050][2];
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 hoge(ll v) {
	ZERO(dp);
	dp[0][0][0]=1;
	
	int i,x,y;
	FOR(i,61) {
		FOR(x,1010) {
			FOR(y,N+1) {
				if(y%2==((Z>>i)%2)) {
					ll a=comb(N,y);
					if((x+y)%2==0&&(v>>i)%2) {
						(dp[i+1][(x+y)/2][0]+=a*dp[i][x][0])%=mo;
						(dp[i+1][(x+y)/2][0]+=a*dp[i][x][1])%=mo;
					}
					else if((x+y)%2&&(v>>i)%2==0) {
						(dp[i+1][(x+y)/2][1]+=a*dp[i][x][0])%=mo;
						(dp[i+1][(x+y)/2][1]+=a*dp[i][x][1])%=mo;
					}
					else {
						(dp[i+1][(x+y)/2][0]+=a*dp[i][x][0])%=mo;
						(dp[i+1][(x+y)/2][1]+=a*dp[i][x][1])%=mo;
					}
				}
			}
		}
	}
	
	return dp[61][0][0];
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R>>Z;
	cout<<(hoge(R)+mo-hoge(L-1))%mo<<endl;
}

まとめ

わりと典型な気がする。