首页 > 代码库 > BZOJ1799 self 同类分布 数位dp
BZOJ1799 self 同类分布 数位dp
BZOJ1799self 同类分布
题意
给出a,b,求出[a,b]中各位数字之和能整除原数的数的个数。
【约束条件】1 ≤ a ≤ b ≤ 10^18
题解
1.所有的位数之和<9*18=162
2.所以,dp[i][j][k][m]表示有i位(允许有前导0),数位和为k,模数为m,前i位与模数的模为j的符合条件的数的个数。这样要炸空间,怎么办!!其实这个dp的最后一维可以省去,因为对于不同的m值,dp互不相干。这样还是要超时的,有5亿多。于是就要卡常数,具体见代码里面的枚举的上下界。
代码
#include <cstring> #include <algorithm> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; typedef long long LL; LL L,R; LL dp[20][163][163]; int a[20],mod; LL dfs(int d,int ds,int c,bool full){ if (d==0) return (ds==0&&c==0)?1:0; if (!full&&dp[d][ds][c]!=-1) return dp[d][ds][c]; LL ans=0; int tp=min(ds,full?a[d]:9); for (int i=max(0,ds-9*(d-1));i<=tp;i++) ans+=dfs(d-1,ds-i,(c*10+i)%mod,full&&i==tp); if (!full) return dp[d][ds][c]=ans; return ans; } LL solve(LL n){ if (n==0) return 0; int d=0; while (n>0) a[++d]=n%10,n/=10; LL ans=0; for (int i=1;i<=d*9;i++){ memset(dp,-1,sizeof dp); mod=i; ans+=dfs(d,i,0,1); } return ans; } int main(){ freopen("self.in","r",stdin); freopen("self.out","w",stdout); scanf("%lld%lld",&L,&R); printf("%lld",solve(R)-solve(L-1)); fclose(stdin);fclose(stdout); return 0; }
BZOJ1799 self 同类分布 数位dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。