HDU ACM 4507 吉哥系列故事——恨七不成妻 ->数位DP

HDU ACM 4507 吉哥系列故事——恨7不成妻 ->数位DP

题意：如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——

1、整数中某一位是7；
2、整数的每一位加起来的和是7的整数倍；
3、这个整数是7的整数倍；
现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
分析：数位DP，关键内容如下。

(pre0+i)%7用于处理各个位数之和时候为7的倍数，(pre1*10+i)%7用于处理这个数是否为7的倍数。

#include<iostream>
using namespace std;

const __int64 mod=1000000007;

struct Node
{
	__int64 c;   //和7无关的数的个数
	__int64 sum; //和7无关的数的和
	__int64 sqsum; //和7无关的数的平方和
};

Node dp[20][10][10];  //分别表示待处理数的位数，各位数字和是7的倍数，数本身是7的倍数
int bit[20];          //存储待处理数的每位
__int64 p[20];        //p[i]=10^i,p[0]=1

void init()
{
	int i,j,k;

	p[0]=1;
	for(i=1;i<20;i++)
		p[i]=(p[i-1]*10)%mod;

	for(i=0;i<20;i++)
		for(j=0;j<10;j++)
			for(k=0;k<10;k++)
				dp[i][j][k].c=-1;
}

Node DFS(int pos,int pre0,int pre1,bool fg)
{
	Node ans,tmp;
	int end,i;

	if(pos==-1)      //数位已处理完，并判断pre0及pre1
	{
		tmp.c=pre0 && pre1;
		tmp.sum=tmp.sqsum=0;
		return tmp;
	}
	if(!fg && dp[pos][pre0][pre1].c!=-1)   //注意边界
		return dp[pos][pre0][pre1];

	end=fg?bit[pos]:9;
	ans.c=ans.sum=ans.sqsum=0;
	for(i=0;i<=end;i++)
	{
		if(i==7) continue;   //跳过7，有7即不合法
		tmp=DFS(pos-1,(pre0+i)%7,(pre1*10+i)%7,fg&&i==end);
		ans.c+=tmp.c;
		ans.c%=mod;

		ans.sum+=(tmp.sum+((p[pos]*i)%mod)*tmp.c%mod)%mod;
		ans.sum%=mod;
		ans.sqsum+=(tmp.sqsum+((2*p[pos]*i)%mod)*tmp.sum)%mod;
		ans.sqsum%=mod;
		ans.sqsum+=((tmp.c*p[pos])%mod*p[pos]%mod*i*i%mod);
		ans.sqsum%=mod;
	}
	if(!fg) dp[pos][pre0][pre1]=ans;    //要判断边界
	return ans;
}

__int64 cal(__int64 n)
{
	int pos=0;

	while(n)
	{
		bit[pos++]=n%10;
		n/=10;
	}
	return DFS(pos-1,0,0,true).sqsum;
}

int main()
{
	int T;
	__int64 l,r,ans;

	scanf("%d",&T);
	init();
	while(T--)
	{
		scanf("%I64d%I64d",&l,&r);
		ans=cal(r);
		ans-=cal(l-1);
		ans=(ans%mod+mod)%mod;        //注意这里的写法，否则会出错，因为减法可能会出现负数
		printf("%I64d\n",ans);
	}
	return 0;
}