UVa 11361 Investigating Div-Sum Property (数位DP)

本文主要是介绍UVa 11361 Investigating Div-Sum Property (数位DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVa 11361 Investigating Div-Sum Property

题目大意:

给定a,b,k三个正整数,统计在[a,b]之间的整数n中,有多少n自身是k的倍数,且n的各个数字(十进制)之和也是k的倍数.( $1\leqslant a\leqslant b\leqslant 2^{31}$ )

题目分析:

这是一道典型的数位DP题.
n非常大,若是直接枚举的话会超时,考虑利用加法原理计算方案数.
将数拆分开来,拆成一位一位的,从前往后枚举.那么就会出现形如”32**”这样枚举了部分,还有部分未枚举.可以用三维状态来表示:f(d,m1,m2)表示当前还有d个数未枚举,m1表示前缀各数之和%k,m2表示组成数%k.如之前的数”32**”就应该对应为f(2,5%k,3200%k).
对应的转移方程则有

$f(d,m1,m2)=\sum f(d-1,(m1+i)\% k,m2+i*10^{d-1}\% k|0\leqslant i \leqslant 9)$

所以dp数组需要开多大. $10*10000*10000 \approx 10^{9}?$ 开不下!
但是其实各个位数之和最大为 $1+9*9=82$ ,所以当k>82时,直接输出0.

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int maxn=11;
const int maxk=100+10;int c10[maxn];//c10[i]=10^i void init()
{c10[0]=1;for(int i=1;i<10;i++) c10[i]=c10[i-1]*10;
}int MOD;
int dp[maxn][maxk][maxk];int f(int d,int m1,int m2)//d表示还有多少个数没有枚举,m1表示前缀各数之和%MOD,m2表示组成数%MOD 
{if(!d) return (m1==0&&m2==0)?1:0;//边界,不需要再枚举数 int& ans=dp[d][m1][m2];if(ans>=0) return ans;ans=0;for(int i=0;i<10;i++) ans+=f(d-1,(m1+i)%MOD,(m2+i*c10[d-1])%MOD);return ans;
}int digit(int n)//求数的位数 
{int cnt=0;if(!n) return 1;while(n>0) ++cnt,n/=10;return cnt;
}int sum(int x)
{int l=digit(x),ans=0,L=0,S=0;//L表示当前的左边界,S表示L各数字之和 for(int i=1;i<=l;i++) {while(0ll+L+c10[l-i]-1<=x) {//这一步考虑能否从当前位继续求 //例如:x=3275 当L=3200时,并不能将3200~3299的数都取到,所以要到下一位看3210是否在x以内 //注意直接比较可能会溢出,需现将其转化成long long  ans+=f(l-i,S%MOD,L%MOD);L+=c10[l-i];S++;//更新L,S }}return ans;
}int main()
{init();int T,a,b;scanf("%d",&T);while(T--) {scanf("%d%d%d",&a,&b,&MOD);if(MOD>82) printf("0\n");//其实当MOD>82时,是不可能达到的 else {memset(dp,-1,sizeof(dp));//每次清空 printf("%d\n",sum(b)-sum(a-1));}}return 0;
}