Codeforces #631 Div1 B. Dreamoon Likes Sequences

750ptなのでBの割にちょっと楽。
http://codeforces.com/contest/1329/problem/B

問題

整数Dが与えられる。
1～Dの範囲の整数で構築される整数列Aのうち、

• Aが真に単調増加
• BをAのprefix xorとしたときBも真に単調増加

となるようなものは何通りか。

解法

AのMSBが単調増加になっていればよい。
そこで、
f(d) := Aの末尾のMSBがd bit目であるような組み合わせ
を求め、その後ろにもっとMSBが大きな値を追加することを考えて行けばよい。

int T;
ll D,M;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	cin>>T;
	while(T--) {
		cin>>D>>M;
		ll dp[33]={};
		
		ll ret=0;
		dp[0]=1;
		for(i=1;i<=32;i++) {
			
			ll num=0;
			if(D<=((1LL<<i)-1)) {
				num=D-((1LL<<(i-1))-1);
			}
			else {
				num=(1LL<<i)-(1LL<<(i-1));
			}
			FOR(x,i) (dp[i]+=dp[x]*num)%=M;
			ret+=dp[i];
			
			if(D<=(1LL<<i)-1) break;
		}
		cout<<ret%M<<endl;
		
	}
}

まとめ

Dの範囲大きいのに、なんでmodの値を可変にしたんだろうな。