https://www.lydsy.com/JudgeOnline/problem.php?id=1799
https://blog.csdn.net/wust_zzwh/article/details/52100392
(偷偷告诉你,这个oj是单组测试,然后memset什么的都是浮云了)
约束:一个数是它自己数位和的倍数,直接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的关系!!!
typedef long long ll;
ll dp[20][163][163][2];
int a[20];
ll dfs(int pos,int sum,int val,int mod,bool limit)
{
if(sum-9*pos-9>0) return 0;//最坏的情况,这一位及后面的全部为9都不能达到0那就直接GG,这个剪枝不会影响ac
if(pos==-1) return sum==0 && val==0;
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]);
}
dp[pos][sum][val][limit]=ans;
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
ll ans=0;
for(int i=1;i<=pos*9;i++)//上限就是每一位都是9
{
memset(dp,-1,sizeof dp);
ll tmp=dfs(pos-1,i,0,i,true);
ans+=tmp;
}
return ans;
}
https://www.cnblogs.com/zhouzhendong/p/7255700.html
给出a,b,求出[a,b]中各位数字之和能整除原数的数的个数。
Input
Output
Sample Input
10 19
Sample Output
3
HINT
【约束条件】1 ≤ a ≤ b ≤ 10^18
https://blog.csdn.net/wust_zzwh/article/details/52100392
(偷偷告诉你,这个oj是单组测试,然后memset什么的都是浮云了)
约束:一个数是它自己数位和的倍数,直接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的关系!!!
typedef long long ll;
ll dp[20][163][163][2];
int a[20];
ll dfs(int pos,int sum,int val,int mod,bool limit)
{
if(sum-9*pos-9>0) return 0;//最坏的情况,这一位及后面的全部为9都不能达到0那就直接GG,这个剪枝不会影响ac
if(pos==-1) return sum==0 && val==0;
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]);
}
dp[pos][sum][val][limit]=ans;
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
ll ans=0;
for(int i=1;i<=pos*9;i++)//上限就是每一位都是9
{
memset(dp,-1,sizeof dp);
ll tmp=dfs(pos-1,i,0,i,true);
ans+=tmp;
}
return ans;
}
https://www.cnblogs.com/zhouzhendong/p/7255700.html
1.所有的位数之和<9*18=162
2.所以,dp[i][j][k][m]表示有i位(允许有前导0),数位和为k,模数为m,前i位与模数的模为j的符合条件的数的个数。这样要炸空间,怎么办!!其实这个dp的最后一维可以省去,因为对于不同的m值,dp互不相干。这样还是要超时的,有5亿多。于是就要卡常数,具体见代码里面的枚举的上下界。
2.所以,dp[i][j][k][m]表示有i位(允许有前导0),数位和为k,模数为m,前i位与模数的模为j的符合条件的数的个数。这样要炸空间,怎么办!!其实这个dp的最后一维可以省去,因为对于不同的m值,dp互不相干。这样还是要超时的,有5亿多。于是就要卡常数,具体见代码里面的枚举的上下界。
因为考虑到直接dp不可行,我们先枚举数字之和,共有9*18种,f[i][j][k][2]表示长度为i数字之和为j,模当前枚举的数字之和为k的是否严格小于该数的种类数。
那么f[i][j][k]-->f[i+1][j+p][(k*10+p)%mod]大概就是这样,因为取模的时候模0了,所以WA了一发。