欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-24 19:12:48
题目链接看起来似乎是很裸的数位dp不难想到我们需要维护一个数位前缀和sumnsumnsumn用于计算f(x)f(x)f(x)我们还需要记录当前枚举值f(x)%mf(x)\%mf(x)%m的值我们还需要记录x%mx\%mx%m的值但是这样复杂度超标我们发现可以直接维护f(x)−xf(x)-xf(x)−x的值,因为模数相同如果第lenlenlen位选择的是iii由于我们维护了len−1位时的f(x)−x由于我们维护了len-1位时的f(x)-x由于我们维护了len−1位时的f(x)−x那么此时...

题目链接

看起来似乎是很裸的数位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 len1f(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)+sumni)(x+i10len)

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

#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

相关标签: icpc dp真题