首页 > 代码库 > HYSBZ - 1799 self 同类分布
HYSBZ - 1799 self 同类分布
self 同类分布
HYSBZ - 1799
给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。Sample Input
10 19
Sample Output
3
Hint
【约束条件】1 ≤ a ≤ b ≤ 10^18
约束：一个数是它自己数位和的倍数，直接dp根本找不到状态，枚举数位和，因为总就162,然后问题就变成了一个数%mod=0，mod是枚举的，想想状态：dp[pos][sum][val]，当前pos位上数位和是sum,val就是在算这个数%mod,（从高位算 *10+i），因为我们枚举的数要保证数位和等于mod，还要保证这个数是mod的倍数，很自然就能找到这些状态，显然对于每一个mod，val不能保证状态唯一，这是你要是想加一维dp[pos][sum][val][mod],记录每一个mod的状态(这里sum可以用减法，然而val不行，就只能加一维)，那你就想太多了，这样是会超时的(因为状态太多，记忆化效果不好)。这里直接对每一个mod，memset一次就能ac。下面的代码还把limit的当做了状态，因为每次都要初始化，所以能这样，memset在多组外面是不能这样的，不过奇葩的，这代码，如果不把limit当状态，还是在!limit 条件下记录dp，提交一发，时间竟然更短了，可能是每次memset的关系！！！
——引自wust_wenhao
#include<cstdio>#include<cstring>using namespace std;typedef long long ll;const int N=18+2,M=162+1;ll a[N],dp[N][M][M][2];ll dfs(int pos,int sum,int val,int mod,bool limit){ if(sum-9*pos>0) return 0; //最坏的情况，这一位及后面的全部为9都不能达到0那就直接GG，这个剪枝不会影响ac if(!pos) return !sum && !val; if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++){ if(sum-i<0) break; ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit && i==a[pos]); } return dp[pos][sum][val][limit]=ans;}ll solve(ll x){ int pos=0;ll ans=0; for(;x;x/=10) a[++pos]=x%10; for(int i=1;i<=pos*9;i++){//上限就是每一位都是9 memset(dp,-1,sizeof dp); ans+=dfs(pos,i,0,i,true); } return ans;}int main(){ for(ll a,b;~scanf("%lld%lld",&a,&b);){ printf("%lld\n",solve(b)-solve(a-1)); } return 0;}
HYSBZ - 1799 self 同类分布
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。