プロジェクトオイラー問162 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20162
Problem 162 「16進数」 †
16進法では, 数は以下の16個の数字によって表される

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

16進数の AF は, 10進法での 10x16 + 15 = 175 と等しい.

3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A の全てが現れている.
10進数で書くときと同様に, 先頭の0は書かないことにする.

0, 1, A がそれぞれ少なくとも1回は現れるような16桁までの16進数はいくつ存在するか?
16進数で答えよ.

(A,B,C,D,E,F は大文字とし, 先頭や末尾の16進数であることを表す記号や先頭の0は許されない. つまり, 1A3F ならOK. 1a3f, 0x1a3f, $1A3F, #1A3F, 0000001A3Fは許されない. )

難しい問題ではありませんが
先頭0を許さないというルールが厄介で力技の漸化式になりました。
一応定数時間で終わる漸化式を１６回ループに収めたので計算量はＢｉｇＯ（16）です。

後で正答者掲示板を見たら謎の定数を使ったスマートな解法が色々あったようです。
やっぱ俺未熟だな。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<list>
unsigned __int64 dp[17][2][2][2],dp2[17][2][2];
char xs[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};


void toHex(unsigned __int64 n){
	std::list<char> ls;
	while(n>0){
		ls.push_front(xs[(int)(n%16)]);
		n/=16;
	}
	std::list<char>::iterator it;
	for(it=ls.begin();it!=ls.end();it++)printf("%c",(*it));
}

int main(){
	memset(dp,0,sizeof(dp));
	memset(dp2,0,sizeof(dp2));
	dp[0][0][0][0]=1;
	for(int i=1;i<=16;i++){
		int p=i-1;
		dp[i][0][0][0]=dp[p][0][0][0]*13;
		
		dp[i][0][0][1]=dp[p][0][0][0]+dp[p][0][0][1]*14;
		dp[i][0][1][0]=dp[p][0][0][0]+dp[p][0][1][0]*14;
		dp[i][1][0][0]=dp[p][1][0][0]*14+dp2[p][0][0]*13;
		
		dp[i][0][1][1]=dp[p][0][0][1]+dp[p][0][1][0]+dp[p][0][1][1]*15;
		dp[i][1][0][1]=dp[p][1][0][0]+dp[p][1][0][1]*15+dp2[p][0][1]*14+dp2[p][0][0];
		dp[i][1][1][0]=dp[p][1][0][0]+dp[p][1][1][0]*15+dp2[p][1][0]*14+dp2[p][0][0];
		dp[i][1][1][1]=dp[p][1][0][1]+dp[p][1][1][0]+dp[p][1][1][1]*16+dp2[p][0][1]+dp2[p][1][0]+dp2[p][1][1]*15;

		dp2[i][0][0]=dp2[p][0][0]+dp[p][0][0][0];
		dp2[i][0][1]=dp2[p][0][1]+dp[p][0][0][1];
		dp2[i][1][0]=dp2[p][1][0]+dp[p][0][1][0];
		dp2[i][1][1]=dp2[p][1][1]+dp[p][0][1][1];
	}
	std::cout<<dp[16][1][1][1]<<"\n";
	toHex(dp[16][1][1][1]);
}