标签：HDU int cnt pos 4507 ans dp 数位

HDU 4507 （数位dp）

题意

一个数满足以下三个条件之一，则被认为与7有关。

1、整数中某一位是7；

2、整数的每一位加起来的和是7的整数倍；

3、这个整数是7的整数倍；

求区间[L,R] 内与7无关的数的平方和。

思路

以往的数位dp都是求个数，这次是求平方和。
怎么想到当前位与下一位的关联？？？
一点头绪都没有，跑去看题解，发现了新大陆。
假设当前位pos填了数字i，之后pos+1到末尾可以满足题意的数共有cnt个，分别为num1,num2,num3....，则它们的贡献为

\(\sum_{j=1}^{cnt}(i*p[pos]+num[j])^2\)，

p[pos]表示10的pos次方，然后去掉括号就变成

\[cnt*(i*p[pos])^2+\sum_{j=1}^{cnt}num[j]^2+2*(i*p[pos])*\sum_{j=1}^{cnt}num[j] \]

所以转移时维护三个变量，满足题意的个数cnt、这些数的和以及平方和。

代码

node dfs(int pos,int val,int dval,int limit)//位置，数本身余7，数位和余7
{
	if(!pos) 
	{
		node ans={0,0,0};
		if((val%7)&&(dval%7)) ans.cnt++;
		return ans;
	}
	if(!limit&&f[pos][val][dval].cnt!=-1) return f[pos][val][dval];
	node ans={0,0,0};
	int up=limit?a[pos]:9;
	for(int i=0;i<=up;i++)
	{	
		if(i==7) continue;
		node ne=dfs(pos-1,(val*10+i)%7,(dval+i)%7,limit&&(i==up));
		int s1=i*p[pos-1]%mod,s2=s1*s1%mod;
		ans.cnt = (ans.cnt+ne.cnt)%mod;
		ans.sum = (ans.sum+ne.cnt*s1)%mod;
		ans.sum = (ans.sum+ ne.sum) %mod;
		ans.sqsum = (ans.sqsum + ne.cnt*s2%mod)%mod;
		ans.sqsum = (ans.sqsum + (2*s1%mod)*ne.sum%mod)%mod;
		ans.sqsum = (ans.sqsum + ne.sqsum)%mod;
	}
	if(!limit) f[pos][val][dval]=ans;
	return ans;

}

需要取模的题不要嫌烦，少一个mod可能都会wa

标签：HDU,int,cnt,pos,4507,ans,dp,数位
From： https://www.cnblogs.com/LIang2003/p/17116813.html