吉哥系列故事——恨7不成妻 HDU - 4507 | 数位dp

dp数组存放结构体，看到平方要想到拆项
debug：p[]数组是mod 1e9 + 7， 不是mod7，在求preval的时候不能用这个数组。debug好久难受了。。。

题意：
如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
　　1、整数中某一位是7；
　　2、整数的每一位加起来的和是7的整数倍；
　　3、这个整数是7的整数倍；
要求一个区间中和7无关的数的平方和。
分析：
需要用数位DP维护3个值：
1.与7无关的数的个数
2.与7无关的数的和
3、与7无关的数的平方和。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e6;
const int inf = 0x3f3f3f3f;
struct node
{
	ll num, sum, sqsum;
	node(ll a = 0, ll b = 0, ll c = 0) : num(a), sum(b), sqsum(c){}
};
int v[30];
node dp[30][10][10];
ll p[30];

void init()
{
	for(int i = 0; i < 30; i++)	
		for(int j = 0; j < 10; j++)
			for(int k = 0; k < 10; k++)
				dp[i][j][k] = node(-1, 0, 0);
	p[0] = 1;
	for(int i = 1; i < 30; i++)
		p[i] = 10 * p[i - 1] % mod;
}

node dfs(int pos, int sum, ll preval, int limit)
{
	if(!pos) return sum && preval ? node(1, 0, 0) : node(0, 0, 0);
	if(!limit && ~dp[pos][sum][preval].num) return dp[pos][sum][preval];
	int up = limit ? v[pos] : 9;
	node res = node(0, 0, 0);
	for(int i = 0; i <= up; i++)
	{
		if(i == 7) continue;
		int nowsum = (sum + i) % 7;
		ll nowval = preval + i * (ll)pow(10, pos - 1); nowval %= 7;
		node tmp = dfs(pos - 1, nowsum, nowval, limit && i == up);
		res.num += tmp.num, res.num %= mod;
		res.sum += (tmp.num * (i * p[pos - 1] % mod) % mod + tmp.sum) % mod, res.sum %= mod;
		res.sqsum += (tmp.sqsum + 2 * i * p[pos - 1] % mod * tmp.sum % mod) % mod, res.sqsum %= mod;
		res.sqsum += tmp.num * (i * p[pos - 1] % mod) % mod * (i * p[pos - 1] % mod) % mod, res.sqsum %= mod;
	}
	if(!limit) dp[pos][sum][preval] = res;
	return res;
}

ll solve(ll x)
{
	int len = 0;
	while(x)
	{
		v[++len] = x % 10;
		x /= 10;
	}
	return dfs(len, 0, 0, 1).sqsum;
}

int main()
{
	int t; cin >> t;
	init();
	while(t--)
	{
		ll l, r;
		cin >> l >> r;
		cout << ((solve(r) - solve(l - 1)) + mod) % mod << endl;
	}
}