原以为很好的理解了数位dp,结果遇到一个新的问题还是不会分析,真的是要多积累啊。
解决13的倍数,可以根据当前余数来推,所以把当前余数记为一个状态就可以了。
#include<bits/stdc++.h>
using namespace std; int dp[][][][];
int b[]; int dfs(int pos,int preok,int rem,int th,int pre)
{
if (pos==-)
{
if (rem==&&th==) return ;
else return ;
}
if (preok&&dp[pos][rem][th][pre]!=-) return dp[pos][rem][th][pre];
int up=preok?:b[pos];
int ans=;
for (int i=;i<=up;i++)
{
ans+=dfs(pos-,i<b[pos]||preok,(rem*+i)%,pre==&&i==||th,i);
}
if (preok) dp[pos][rem][th][pre]=ans;
return ans;
} int solve(int n)
{
int cnt=;
do {
b[cnt++]=n%;
n/=;
}while (n);
return dfs(cnt-,,,,);
} int main()
{
memset(dp,-,sizeof(dp));
int n;
while (~scanf("%d",&n))
{
printf("%d\n",solve(n));
}
return ;
}