首页 > 代码库 > HDU - 4507 吉哥系列故事――恨7不成妻 （数位DP）

HDU - 4507 吉哥系列故事――恨7不成妻 （数位DP）

2024-07-14 02:21:56   218人阅读

Description

　　单身!
　　依然单身！
　　吉哥依然单身！
　　DS级码农吉哥依然单身！
　　所以，他生平最恨情人节，不管是214还是77，他都讨厌！
　　
　　吉哥观察了214和77这两个数，发现：
　　2+1+4=7
　　7+7=7*2
　　77=7*11
　　最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！

　　什么样的数和7有关呢？

　　如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关――
　　1、整数中某一位是7；
　　2、整数的每一位加起来的和是7的整数倍；
　　3、这个整数是7的整数倍；

　　现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
 

Input

输入数据的第一行是case数T(1 <= T <= 50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。
 

Output

请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。
 

Sample Input

3
1 9
10 11
17 17
 

Sample Output

236
221
0
 

Source

2013腾讯编程马拉松初赛第一场（3月21日）

思路：数位DP， 一个表示与7无关的个数，一个表示与7无关的数的和，7无关的数字的平方和。

           难处理的是平方和，要从前两个推出来，就是将平方和拆出来就行了，还有乱mod不会过啊，

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 20;
const ll mod = 1000000007ll;

struct node {
	long long cnt;
	long long sum;
	long long sqsum;
} dp[maxn][10][10];
ll p[maxn];
int num[maxn];

node dfs(int cur, int p1, int p2, int flag) {
	if (cur == -1) {
		node tmp;
		tmp.cnt = (p1 != 0 && p2 != 0);
		tmp.sum = tmp.sqsum = 0;
		return tmp;
	}
	if (!flag && dp[cur][p1][p2].cnt != -1)
		return dp[cur][p1][p2];
	int end = flag?num[cur]:9;
	node ans;
	node tmp;
	ans.cnt = ans.sqsum = ans.sum = 0;
	for (int i = 0; i <= end; i++) {
		if (i == 7)
			continue;
		tmp = dfs(cur-1, (p1+i)%7, (p2*10+i)%7, flag&&i==end);
		ans.cnt += tmp.cnt;
		ans.cnt %= mod;
		ans.sum += (tmp.sum+ ((p[cur]*i)%mod)*tmp.cnt%mod)%mod;
		ans.sum %= mod;
		ans.sqsum += (tmp.sqsum + ((2*p[cur]*i)%mod)*tmp.sum)%mod;
		ans.sqsum %= mod;
		ans.sqsum += (tmp.cnt*p[cur])%mod*p[cur]%mod*i*i%mod;
		ans.sqsum %= mod;
	}
	if (!flag)
		dp[cur][p1][p2] = ans;
	return ans;
}

long long cal(long long m) {
	int cnt = 0;
	while (m) {
		num[cnt++] = m%10;
		m /= 10;
	}
	return dfs(cnt-1, 0, 0, 1).sqsum;
}

int main() {
	int t;
	p[0] = 1;
	for (int i = 1; i < maxn; i++)
		p[i] = (p[i-1]*10) % mod;
	for (int i = 0; i < maxn; i++)
		for (int j = 0; j < 10; j++)
			for (int k = 0; k < 10; k++)
				dp[i][j][k].cnt = -1;
	cin >> t;
	while (t--) {
		ll l, r;
		cin >> l >> r;
		long long ans = cal(r);
		ans -= cal(l-1);
		ans = (ans%mod+mod)%mod;
		cout << ans << endl;
	}
	return 0;
}


联系
我们