Problem 290 「デジタル・シグネチャー(数字の特徴)」 †
0 ≤ n < 10^18 であり n の桁の合計が 137n の桁の合計と等しいような整数 n はいくつあるか.
n=0に注意すればあとは1桁単位の漸化式で一発です。
試行錯誤時間3時間
計算時間3秒。
最後に出る数字が答え。
#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";
}
}
最終更新:2015年12月16日 17:38