Codeforces 261C Maxim and Matrix

問題

問題文中の擬似コードにしたがって(m+1)x(m+1)の行列を埋めたとき、
最後の行に現れる1の数がtに等しいようなmのうち、
m≦nを満たすものはいくつあるか求めよ。

行列の埋め方は要約すると以下の通り。
1行目は右上だけを1にする。
a[i][j] = a[i-1][j-1] ^ a[i-1][j+1]（ただしはみ出たところは0と考える）

制約条件

n, t≦10^12

方針

実験。
ixiの行列の最後の行の1の数をf(i)として、f(i)を出力してみると、全部2^xになっている。
じゃあ2^xのxだけ出力してみる。

すると、i = 2^k-1のときに必ず0になっていて、
じゃあ1ずらして、iとf(i+1)の表を作ってみると、なんかfはビットカウント-1になっている。

つまり f(i) = 2 ^ (bit(i+1) - 1)

なので、要するにn以下の整数のうち立っているビットの個数が一定の個数の
数は何個か求める問題になって、これは適当に桁DPすればいい。

ソースコード

int m, d[70];
ll dp[70][70][2]; //pos, bit, sml

int main(){
	/*
	int a[500][500];
	a[0][0] = 1;
	for(int i = 1; i < 500; i++) rep(j, i+1){
		if(j == 0) a[i][j] = a[i-1][j+1];
		else if(j == i) a[i][j] = a[i-1][j-1];
		else a[i][j] = a[i-1][j+1] ^ a[i-1][j-1];
	}
	rep(i, 100){
		int s = 0;
		rep(j, i+1) s += a[i][j];
		cerr<<i<<" "<<s<<" "<<__builtin_ctz(s)<<endl;
	}
	f(n) = 1 << (bit(n+1) - 1)
	n+1以下の整数で、tailzero(t)+1とbit数が等しいものを数えればいい
	*/
	
	ll n, t;
	cin >> n >> t;
	n++;
	for(; n; n /= 2) d[m++] = n % 2;
	reverse(d, d + m);
	
	int bit = __builtin_ctzll(t) + 1;
	if(__builtin_popcountll(t) != 1){
		cout << 0 << endl;
		return 0;
	}
	
	dp[0][0][0] = 1;
	rep(i, m) rep(j, i + 1) rep(k, 2) if(dp[i][j][k]){
		rep(l, 2){
			int nk = k || l < d[i];
			if(!nk && l > d[i]) continue;
			dp[i + 1][j + l][nk] += dp[i][j][k];
		}
	}
	cout << dp[m][bit][0] + dp[m][bit][1] - (t == 1) << endl;
	
	return 0;
}