2022杭电多校第7场

contest传送门

战况

这次贼猛，前几题写的也贼快，甚至在前面的时候甚至排到了第3名。

这次我也写了一道题，和曹佬一块讨论出了1002。

这次没有找到字符串题目。

补题

1006-Sumire (数位dp)

题意

计算 $\sum_{i=l}^r f^k(i,B,d)$

其中 $f(x,B,d)$ 表示数字 $d$ 在 $B$ 进制的数字 $x$ 中出现的次数。

思路

数位dp，我们使用 $dp[i][j]$ 表示还剩 $i$ 位要填并且前面已经有 $j$ 个数字 $d$ 的情况下的答案总数(这里指已经进行了 $k$ 次方运算后的结果)

大体上就是数位dp的板子了，但是直接交上去会 $T$ ，因为在这道题里面，可能会有 $10^9$ 进制的数，这时，只是一次循环就会 $T$ 掉，于是，我们需要做亿些优化

我们可以对下一个要枚举的数字进行分类，比如下一位是否等于 $d$ ，是否等于 $0$ ，是否等于上界 $up$ ，然而，这几种情况中间又会有交集，于是，这就变成了一个非常大的 $if / else$ 了，对上面的几种情况进行分类讨论即可。

代码实现要十分细心，此处细节非常多，很容易出错。

代码

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
#pragma GCC optimize(2)
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;
const LL mod=1000000007LL;

LL num[100],dp[70][70];
LL k,b,d,l,r;

LL fastpow(LL jj,LL kk){
	if(jj==0LL) return 0LL;
	LL ret=1;
	while(kk){
		if(kk&1) ret=ret*jj%mod;
		jj=jj*jj%mod;
		kk>>=1;
	}
	return ret;
}

LL dfs(LL now,bool limit,bool nozero,LL sum){
	if(!now) return fastpow(sum,k);
	if(!limit&&nozero&&dp[now][sum]!=-1) return dp[now][sum];
	LL ret=0,up=limit?num[now]:b-1;
	// ret+=dfs(now-1,(limit&&(i==up)),nozero||i,sum+(bool)((nozero||i)&&(i==d)));
	if(d<=up){
		ret+=dfs(now-1,(limit&&(d==up)),nozero||d,sum+(bool)(nozero||d)),ret%=mod;//d
		if(up==0);
		else{
			if(d==0){
				ret+=dfs(now-1,(limit),1,sum),ret%=mod;//up
				ret+=(up-1)*dfs(now-1,0,1,sum),ret%=mod;//other
			}
			else if(d==up){
				ret+=dfs(now-1,0,nozero,sum),ret%=mod;//0
				ret+=(up-1)*dfs(now-1,0,1,sum),ret%=mod;//other
			}
			else{
				ret+=dfs(now-1,0,nozero,sum),ret%=mod;//0
				ret+=dfs(now-1,(limit),1,sum),ret%=mod;//up
				ret+=(up-2)*dfs(now-1,0,1,sum),ret%=mod;//other
			}
		}
	}
	else{
		if(up==0)
			ret+=dfs(now-1,(limit),nozero,sum),ret%=mod;
		else{
			ret+=dfs(now-1,0,nozero,sum),ret%=mod;//0
			ret+=dfs(now-1,(limit),1,sum),ret%=mod;//up
			ret+=(up-1)*dfs(now-1,0,1,sum),ret%=mod;//other
		}
	}

	if(!limit&&nozero) dp[now][sum]=ret;
	return ret;
}

inline LL getans(LL x){
	memset(dp,-1,sizeof(dp));
	LL p=0;
	while(x){
		num[++p]=x%b;
		x/=b;
	}
	return dfs(p,true,false,0LL);
}

inline void solve(){
	scanf("%lld%lld%lld%lld%lld",&k,&b,&d,&l,&r);
	printf("%lld\n",(getans(r)-getans(l-1)+mod)%mod);
}

signed main(){
	LL t;scanf("%lld",&t);
	while(t--)
		solve();
	
	return 0;
}