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

Problem 290 「デジタル・シグネチャー(数字の特徴)」 †
0 ≤ n < 10^18 であり n の桁の合計が 137n の桁の合計と等しいような整数 n はいくつあるか.

n=0に注意すればあとは１桁単位の漸化式で一発です。
試行錯誤時間３時間
計算時間３秒。
最後に出る数字が答え。

#include<stdio.h>
#include<iostream>
#include<map>
//1 1
//2 3
//3 32
//4 305
//5 2901
//6 27954
int f(int n){
	int res=0;
	while(n>0){
		res+=(n%10);
		n/=10;
	}
	 return res;
}
__int64 dp[200][200][200],next[200][200][200];

 
int main(){
	__int64 memo[200];
	for(int i=0;i<200;i++){
		memo[i]=f(i);
	}
	memset(dp,0,sizeof(dp));
	__int64 ans=1;
 	dp[0][0][0]=1;
	for(int i=0;i<18;i++){
		memset(next,0,sizeof(next));
		for(int j=0;j<200;j++){
			for(int k=0;k<200;k++){
				for(int l=0;l<200;l++){
					if(dp[j][k][l]==0)continue;
 					__int64 f=l;
					__int64 s=dp[j][k][l];
					for(int n=1;n<=9;n++){
						int p=j+n*137;
						int p2=p%10+k;
						int p3=f+n;
						next[p/10][p2][p3]+=s;	
					}
				}
			}
		}
		for(int j=0;j<200;j++){
			for(int k=0;k<200;k++){
				for(int l=0;l<200;l++){
					int n1=memo[j]+k;
					int n2=l;
					if(next[j][k][l]>0){
						if(n1==n2){
							ans+=next[j][k][l];
						}
					}
					next[j/10][k+j%10][l]+=dp[j][k][l];
				}
			}
		}
		memcpy(dp,next,sizeof(next));
		std::cout<<ans<<"\n";
	}
}