2019-2020 ICPC Asia Hong Kong Regional Contest J题

题意：给定一个数x（$x<=10^{5000}$），$d(x,i)$表示$x$的第$i$位数字，令$f(x)={\sum }_{i=1}^{k-1}{\sum }_{j=i+1}^{k}d(x,i)\ast d(x,j)$。
求$[L,R]$中，满足$x\equiv f(x)modm$的$x$个数。
$L,R<=10^{5000}，m<=60$

思考：
这道题很明显$f(x)$的意义是任意两位数位的积，而且x很大。很容易联想到数位dp。
所谓数位dp，其实就是优雅的暴力。用dp数组保存状态，以记忆化的方式保存那些会反复用到的值。
这里用$dp[i][j][k][l]$表示前$i$位数位，前缀和为$j$，前$i$位数位的$f(x)$为$k$，前$i$位的x为$l$。我们稍微计算一下空间$5000\ast 60\ast 60\ast 60=1e8$，好像空间已经超了。考虑如何优化一下。
由于我们只关注$f(x)$与$x$的差值，那么可以将最后两维合并为一维。使用$dp[i][j][k]$代表前$i$位数位，前缀和为$j$，前$i$位数位的$f(x)-x$为$k$。
这里附上代码：

int dfs(int now, int psum, int div, int tp){
	if(now == len + 1) return div == 0;
	if(dp[now][psum][div] != -1 && !tp) return dp[now][psum][div];
	int res = 0;
	For(i, 0, tp ? a[now] : 9)
		res = (res + dfs(now+1, (psum + i) % m, (div + i * (psum -  ten[now] + m)) % m, tp && (i==a[now]))) % mod;
	if(!tp) dp[now][psum][div] = res;
	return res;
}

这里$dp[i][j][k]$记录的是当前第$i$位没有限制的条件下（大小限制），这个状态的后续状态的方案数。因为有限制的时候，由于限制，后面的数位不能都取到$9$，后续状态的方案数也和没有限制的不一样，且这个不一样的方案数只会被用一遍。而没有限制的则可以被使用多遍，故记忆化保存没有限制的。当然，也可以增加一维专门用来保存是否是限制状态，这个也是可行的。

#include<bits/stdc++.h>
#define For(aa, bb, cc) for(int aa=(bb); aa<=(int)(cc); ++aa)
#define Forr(aa, bb, cc) for(int aa=(bb); aa>=(int)(cc); --aa)
using namespace std;
const int maxn=5e3+10,mod=1e9+7;
int m;
int dp[maxn][61][61];//前i位, 前缀为j, fx与x差为 k
int ten[maxn];
int a[maxn], len;

int dfs(int now, int psum, int div, int tp){
	if(now == len + 1) return div == 0;
	if(dp[now][psum][div] != -1 && !tp) return dp[now][psum][div];
	int res = 0;
	For(i, 0, tp ? a[now] : 9)
		res = (res + dfs(now+1, (psum + i) % m, (div + i * (psum -  ten[now] + m)) % m, tp && (i==a[now]))) % mod;
	if(!tp) dp[now][psum][div] = res;
	return res;
}

int solve(){
	ten[len] = 1 % m;
	Forr(i, len - 1, 1) ten[i] = ten[i + 1] * 10 % m;
	For(i, 1, len + 1) For(j, 0, m - 1) For(k, 0, m - 1) dp[i][j][k] = -1;
	return dfs(1, 0, 0, 1);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int _;
	scanf("%d", &_);
	while(_--){
		char s[maxn];
		int lenl, lenr, L[maxn], R[maxn];
		scanf("%s", s+1);
		lenl = strlen(s+1);
		For(i, 1, lenl) L[i] = s[i] - '0';
		scanf("%s", s+1);
		lenr = strlen(s+1);
		For(i, 1, lenr) R[i] = s[i] - '0';
		int pos = lenl; 
		--L[pos];
		while(L[pos] < 0) L[pos] += 10, --L[pos-1], --pos;
		if(!L[1]){
			--lenl;
			For(i, 1, lenl) L[i] = L[i+1];
		}
		//For(i, 1, lenr) cout << R[i]; cout << endl;
		//For(i, 1, lenl) cout << L[i]; cout << endl;
		scanf("%d", &m);
		len = lenr;
		For(i, 1, len) a[i] = R[i];
		int r = solve();
		len = lenl;
		For(i, 1, len) a[i] = L[i];
		int l = solve();
		printf("%d\n", (r - l + mod) % mod);
	}
	return 0;
}