Codeforces Round #631 (Div. 2) D. Dreamoon Likes Sequences （位运算&组合数学）

Codeforces Round #631 (Div. 2) D. Dreamoon Likes Sequences （位运算&组合数学）

题目传送门

题意：给定d,mod,求所有满足ai在[1,d]且异或运算后bi<bi+1的所有数组A的个数。

思路：

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int t;
	cin>>t;
	while(t--){
		ll d,mod,k=1,ans=1;
		cin>>d>>mod;
		while(k<=d){
			ans=ans*(min((k<<1)-1,d)-k+2)%mod;
			k<<=1;
		}
		cout<<(ans-1+mod)%mod<<endl; 
	}
	return 0;
}