2022杭电多校七 F-Sumire（数位DP+实用技巧）

题目链接：杭电多校7 - Virtual Judge

vjudge上题目显示的有问题，我下面附上官方题目：

样例输入： 

3
2 2 0 1 5
1 4 3 11 45
10 14 11 19 198

样例输出：

6
19
1049

题意：多组样例，每组样例给出五个数k,b,d,l,r，其中b是代表b进制，f(i,b,d)代表在b进制下i的数位中出现数字d的个数。求

 分析：定义f[i][j][1/0][1/0]表示已经统计了前i位有j位是d且当前位有/无限制，有/无前导0的方案数

一开始我按照普通的数位DP思路求解，但是总是超时，然后仔细分析了一下，发现了原来的数位DP还可以具体根据题目优化一下。

比如这道题，我一开始是分两种情况来进行动态转移：

枚举当前填的数字

一种情况是当前有前导0且当前位置填0。

另一种情况就是当前位置填无前导0或者当前位置不填0，这两个合成一种情况即可。

dfs代码是这样写的：

long long dfs(int pos,int cnt,int limit,int lead)
{
	if(pos==0) return (cnt==tt);
	if(!limit&&!lead&&f[pos][cnt]!=-1) return f[pos][cnt];
	int up=limit?a[pos]:(b-1);
	long long ans=0;
	for(int i=0;i<=up;i++)
	{
		if(lead&&i==0) ans+=dfs(pos-1,cnt,limit&&(i==a[pos]),lead);
		else ans+=dfs(pos-1,cnt+(i==d),limit&&(i==a[pos]),0); 
	}
	if(!limit&&!lead) f[pos][cnt]=ans;
	return ans;
}

后来对这样的代码进行了很多优化发现还是超时，仔细分析了一下才发现当前位置如果不填d或者up或者0，那么填其他任何数字都是一样的，因为只有d才会对最后的答案造成影响，而up会对下一次可以取的数字造成影响，而0可以对前导0造成影响，所以对于一种情况，如果我们可以在0~up中做出选择，去掉d、up、0之外的数选哪个都是一样的，我们可以直接计算一下这样的数字的个数，然后直接令ans+可选数字个数*dfs(pos-1，cnt，0，0)即可，因为选的数既不是上限也不是0，所以会去掉限制和前导0，而且由于选的数不是d，那么也不会对答案造成贡献，所以我们就可以把很多次重复的计算直接一次算出来，这样的话就会极大地优化时间，从而就可以ac，有同学可能会问：我们都记忆化了，算一次和算十次有什么本质区别吗，算完一次之后再算就直接访问数组就可以了啊，为什么这样还会节省时间呢？可以这么想假如说我们刚才讨论的那种不是up和d和0的情况有10000种，那么我们就需要访问10000次数组，这样算下来复杂度会高很多，而我们之前的数位DP题目一般进制数都很少，或者说一般都是10进制的，而这道题b的上界是1e9，这个数还是很大的，所以我们这种优化对于进制数比较大的问题还是很有用的。

这个技巧近适用于贡献与某位数字有直接关系的题目中。

细节见代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
long long k,b,d;
const int N=65,mod=1e9+7;
long long f[N][N][2][2];//f[i][j][1/0][1/0]表示已经统计了前i位有j位是d且当前位有/无限制，有/无前导0的方案数 
long long a[N],tt;
long long qpow(long long a,long long b)
{
	if(a==0) return 0;//题目中要求0^0=0
	long long ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
long long dfs(int pos,int cnt,int limit,int lead)
{
	if(!pos) return qpow(cnt,k);
	if(f[pos][cnt][limit][lead]!=-1) return f[pos][cnt][limit][lead];
	int up=limit?a[pos]:(b-1);
	long long ans=0;
	if(d==up)
	{
		if(lead)
		{
			ans+=dfs(pos-1,cnt,0,1);//有前导0且填0
			ans+=dfs(pos-1,cnt+1,limit,0);//有前导0填d 
			ans+=(up-1)*dfs(pos-1,cnt,0,0)%mod;//有前导0但不填up和0 
		}
		else
		{
			ans+=dfs(pos-1,cnt+1,limit,0);//无前导0填d
			ans+=up*dfs(pos-1,cnt,0,0)%mod;//无前导0但不填d
		} 
		ans%=mod;
	}
	else if(d==0)
	{
		if(lead)
		{
			ans+=dfs(pos-1,cnt,0,1);//有前导0且填0
			ans+=dfs(pos-1,cnt,limit,0);//有前导0且填up
			ans+=(up-1)*dfs(pos-1,cnt,0,0)%mod;//有前导0但不填up和d 
		}
		else
		{
			ans+=dfs(pos-1,cnt+1,0,0);//无前导0且填d
			ans+=dfs(pos-1,cnt,limit,0);//无前导0且填up
			ans+=(up-1)*dfs(pos-1,cnt,0,0)%mod;//无前导0且不填up和d 
		} 
		ans%=mod;
	}
	else if(up>d)//d不等于up和0,但是要保证up大于d 
	{
		if(lead)
		{
			ans+=dfs(pos-1,cnt,0,1);//有前导0且填0
			ans+=dfs(pos-1,cnt+1,0,0);//有前导0且填d
			ans+=dfs(pos-1,cnt,limit,0);//有前导0且填up
			ans+=(up-2)*dfs(pos-1,cnt,0,0)%mod;//有前导0但不填up和d和0 
		}
		else
		{
			ans+=dfs(pos-1,cnt+1,0,0);//无前导0且填d
			ans+=dfs(pos-1,cnt,limit,0);//无前导0且填up
			ans+=(up-1)*dfs(pos-1,cnt,0,0)%mod;//无前导0但不填up和d
		} 
		ans%=mod;
	}
	else//up
	{
		if(lead)
		{
			ans+=dfs(pos-1,cnt,0,1);//有前导0且填0
			ans+=dfs(pos-1,cnt,limit,0);//有前导0且填up
			ans+=(up-1)*dfs(pos-1,cnt,0,0)%mod;//有前导0但不填0和up 
		}
		else
		{
			ans+=dfs(pos-1,cnt,limit,0);//无前导0且填up
			ans+=up*dfs(pos-1,cnt,0,0)%mod;//无前导0但不填up 
		}
		ans%=mod;
	}
	return f[pos][cnt][limit][lead]=ans;
}
long long solve(long long x)
{
	memset(f,-1,sizeof f);
	int pos=0;
	while(x)
	{
		a[++pos]=x%b;
		x/=b;
	}
	return dfs(pos,0,1,1);
}
int main()
{
	int T;
	cin>>T;
	long long l,r;
	while(T--)
	{
		scanf("%lld%lld%lld%lld%lld",&k,&b,&d,&l,&r);
		printf("%lld\n",(solve(r)-solve(l-1)+mod)%mod);
	}
	return 0;
}