学习大神的数位DP模版。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[][][];
int num[];
//dp[i][j][k] 代表前i位余数为j时候 flag的3种情况
int dfs(int pos,int pre,int flag,int bound)//pos代表位置，pre代表余数，
{
int ans = ,end,tflag,tpre,i;
if(pos == -)//flag 1代表上位是1，2代表前面已经有13了，0代表其他的。
return pre == &&flag == ;
if(!bound&&dp[pos][pre][flag] != -)
return dp[pos][pre][flag];
end = bound ? num[pos] : ;
for(i = ;i <= end;i ++)
{
tpre = (pre* + i)%;
tflag = flag;
if(flag == &&i == )
tflag = ;
else if(flag == &&i == )
tflag = ;
else if(flag == &&i != )
tflag = ;
ans += dfs(pos-,tpre,tflag,bound&&i == end);
}
if(!bound)
dp[pos][pre][flag] = ans;
return ans;
}
int judge(int x)
{
int pos = ;
while(x)
{
num[pos++] = x%;
x = x/;
}
return dfs(pos-,,,);
}
int main()
{
int n;
memset(dp,-,sizeof(dp));
while(scanf("%d",&n)!=EOF)
printf("%d\n",judge(n));
return ;
}