本文共 1285 字，大约阅读时间需要 4 分钟。
题意:统计区间 [1,n] 中含有 '13' 且模 13 为 0 的数字有多少个。
分析：由 （HDU 2089 不要62）和（CF 55D - Beautiful numbers）想到该题做法，dp[i][j][f][mod],长度为i,前缀是否为1，是否已符合条件，余数为mod的数字个数。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef pair PII;typedef long long ll;#define lson l,m,rt<<1#define pi acos(-1.0)#define rson m+1,r,rt<<11#define All 1,N,1#define read freopen("in.txt", "r", stdin)const ll INFll = 0x3f3f3f3f3f3f3f3fLL;const int INF= 0x7ffffff;const int mod = 1000000007;ll dp[15][2][2][13],n;int bit[15];ll dfs(int i,int j,int f,int mod,int e){ if(i==0)return f&&(mod%13==0)?1:0; if(!e&&dp[i][j][f][mod]!=-1)return dp[i][j][f][mod]; int u=e?bit[i]:9; ll num=0; for(int v=0;v<=u;++v) { int tm=(mod*10+v)%13; if(f)num+=dfs(i-1,v==1,1,tm,e&&(v==u)); else num+=dfs(i-1,v==1,j&&v==3,tm,e&&(v==u)); } return e?num:dp[i][j][f][mod]=num;}ll solve(ll x){ int len=0; while(x){ bit[++len]=x%10; x/=10; } return dfs(len,0,0,0,1);}int main(){ memset(dp,-1,sizeof(dp)); while(~scanf("%I64d",&n)){ printf("%I64d\n",solve(n)); }return 0;}
转载于:https://www.cnblogs.com/zsf123/p/4675434.html