2 条题解
-
0
#include<stdio.h> #include<string.h> int dp[11][91][91][91]; int a[11],len; int dfs(int dep,int sum,int num,int mod,bool lim){ if(!dep)return sum==mod&&!num; if(!lim&&~dp[dep][sum][num][mod])return dp[dep][sum][num][mod]; int res=0; const int up=lim?a[dep]:9; for(int i=0;i<=up;++i) if(sum+i<=mod)res+=dfs(dep-1,sum+i,((num<<3)+(num<<1)+i)%mod,mod,lim&(i==a[dep])); if(!lim)dp[dep][sum][num][mod]=res; return res; } inline int solve(int n){ len=0; for(int i=n;i;i/=10)a[++len]=i%10; int res=0; for(int i=9*len;i;--i) res+=dfs(len,0,0,i,1); return res; } int l,r; int main(){ memset(dp,-1,sizeof(dp)); while(~scanf("%d%d",&l,&r)) printf("%d\n",solve(r)-solve(l-1)); return 0; } -
0
#include<stdio.h> #include<string.h> int dp[11][91][91][91]; int a[11],len; int dfs(int dep,int sum,int num,int mod,bool lim){ if(!dep)return sum==mod&&!num; if(!lim&&~dp[dep][sum][num][mod])return dp[dep][sum][num][mod]; int res=0; const int up=lim?a[dep]:9; for(int i=0;i<=up;++i) if(sum+i<=mod)res+=dfs(dep-1,sum+i,((num<<3)+(num<<1)+i)%mod,mod,lim&(i==a[dep])); if(!lim)dp[dep][sum][num][mod]=res; return res; } inline int solve(int n){ len=0; for(int i=n;i;i/=10)a[++len]=i%10; int res=0; for(int i=9*len;i;--i) res+=dfs(len,0,0,i,1); return res; } int l,r; int main(){ memset(dp,-1,sizeof(dp)); while(~scanf("%d%d",&l,&r)) printf("%d\n",solve(r)-solve(l-1)); return 0; }
- 1
信息
- ID
- 1397
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 65
- 已通过
- 18
- 上传者