题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3652
题目大意:给你一个数R,让你求[1, R]有多少个数,包含连续的13数字并且能够整除13。
包含13这个状态很好处理,前面的那道不要62就处理过这种情况。但是这个整除的状态就比较难表示。
后来学习了一种表示方法:用余数表示。例如:143
pos=2时 mod2=1
pos=1时 mod1=(mod2 * 10+4)%13=1
pos=0时 mod0=(mod3 * 10+3)%13=0
所以143能被13整除。
这利用了mod的性质:
( preSum * 10^pos + next ) % MOD
= ( preSum * 10 ^ pos % MOD + next % MOD )
所以整除转化成余数就可以保存状态了。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int a[20];
LL dp[20][20][3];
//ok:0 没有出现13 并且上一位不是1
//ok:1 没有出现13 并且上一位是1
//ok:2 出现过13
LL dfs(int pos, int mod, int ok, int mt)
{
if(pos==-1)
{
if(ok==2&&mod==0)
{
return 1;
}
else
{
return 0;
}
}
if(!mt&&dp[pos][mod][ok]!=-1)
{
return dp[pos][mod][ok];
}
int Len=mt?a[pos]:9;
LL ans=0;
for(int i=0;i<=Len;i++)
{
if(i==1)
{
ans+=dfs(pos-1, (mod*10+i)%13, ok==2?2:1, mt&&i==a[pos]);
}
else if(i==3)
{
ans+=dfs(pos-1, (mod*10+i)%13, ok==2?2:(ok==1?2:0), mt&&i==a[pos]);
}
else
{
ans+=dfs(pos-1, (mod*10+i)%13, ok==2?2:0, mt&&i==a[pos]);
}
}
if(!mt)
{
dp[pos][mod][ok]=ans;
}
return ans;
}
LL slove(LL x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1, 0, 0, true);
}
int main()
{
LL R;
memset(dp, -1, sizeof(dp));
while(scanf("%lld",&R)!=EOF)
{
printf("%lld\n", slove(R));
}
return 0;
}