2019hongkongicpc J – Junior Mathematician(压缩状态的数位DP)

题目链接

看起来似乎是很裸的数位dp

不难想到我们需要维护一个数位前缀和 s u m n sumn sumn用于计算 f ( x ) f(x) f(x)

我们还需要记录当前枚举值 f ( x ) % m f(x)\%m f(x)%m的值

我们还需要记录 x % m x\%m x%m的值

但是这样复杂度超标

我们发现可以直接维护 f ( x ) − x f(x)-x f(x)−x的值,因为模数相同

如果第 l e n len len位选择的是 i i i

由 于 我 们 维 护 了 l e n − 1 位 时 的 f ( x ) − x 由于我们维护了len-1位时的f(x)-x 由于我们维护了len−1位时的f(x)−x

那 么 此 时 转 移 就 是 ( f ( x ) + s u m n ∗ i ) − ( x + i ∗ 1 0 l e n ) 那么此时转移就是(f(x)+sumn*i)-(x+i*10^{len}) 那么此时转移就是(f(x)+sumn∗i)−(x+i∗10len)

这样优化掉一维度,就可以了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=3e5+10;
char l[maxn],r[maxn];
ll dp[5009][75][75];
int ppow[5009],a[5009],en,n,m;
int dfs(int len,int limit,int nowmod,int sumn)
{
//nowmod是当前数对m的和,he是前缀和, 
	if( len==0 )	return !nowmod;
	if( !limit&&dp[len][nowmod][sumn]!=-1 )
		return dp[len][nowmod][sumn];
	ll last=limit?a[len]:9,ans=0;
	for(int i=0;i<=last;i++)
	{
		int fx=nowmod+sumn*i-i*ppow[len-1]+m;
		ans+=dfs(len-1,limit&&(i==a[len]),(fx%m+m)%m,(sumn+i)%m);
	}
	ans=(ans%mod+mod)%mod;
	if( !limit )	dp[len][nowmod][sumn]=ans;
	return ans;
}
int solve(char b[])
{
	en=strlen(b+1);
	for(int i=0;i<=en;i++)
	for(int j=0;j<m;j++)
	for(int q=0;q<m;q++)
		dp[i][j][q]=-1;
	for(int i=1;i<=en;i++)
		a[i]=b[en-i+1]-'0';
	return dfs(en,1,0,0);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	ppow[0]=1;
	int t; cin >> t;
	while( t-- )
	{
		cin >> (l+1) >> (r+1);
		cin >> m;
		int rr=strlen(r+1);
		for(int i=1;i<=rr;i++)	ppow[i]=ppow[i-1]*10%m;
		int en=strlen(l+1);
		l[en]--;
		for(int i=en;i>=1;i--)
			if( l[i]<'0' )	l[i]+=10,l[i-1]--;
			else	break;
		cout << ( solve(r)-solve(l)+mod )%mod << '\n';
	}
}

本文地址：https://blog.csdn.net/jziwjxjd/article/details/108567471