yukicoder : No.1811 EQUIV Ten

参加が遅れたこともあり時間内に終わらず。
https://yukicoder.me/problems/no/1811

問題

正整数Nが与えられる。
2^N未満の整数Xのうち、以下を満たすのは何通りか。

• ある非負整数kに対し、floor(X/(2^k))を16で割った余りが10である

解法

Xを2進数表記したとき、"1010"を含んでいれば条件を満たす。
f(a,b) := Xの2進数表記の先頭a桁を定めたとき、末尾b文字が"1010"のprefixと一致する
として、どこかでb=4になるケースを数え上げよう。

int N;
const ll mo=1000000007;

ll dp[202020][5];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	dp[0][0]=1;
	FOR(i,N) {
		// success
		(dp[i+1][1]+=dp[i][0])%=mo;
		(dp[i+1][2]+=dp[i][1])%=mo;
		(dp[i+1][3]+=dp[i][2])%=mo;
		(dp[i+1][4]+=dp[i][3])%=mo;
		(dp[i+1][4]+=2*dp[i][4])%=mo;
		
		//fail
		(dp[i+1][0]+=dp[i][0])%=mo;
		(dp[i+1][1]+=dp[i][1])%=mo;
		(dp[i+1][0]+=dp[i][2])%=mo;
		(dp[i+1][1]+=dp[i][3])%=mo;
	}
	cout<<dp[N][4]<<endl;
}

まとめ

文字列の問題に落とせる、と気づけばそこからは楽。