[HDU4507]吉哥系列故事——恨7不成妻

时间：2022-05-22 09:07:41

[HDU4507]吉哥系列故事——恨7不成妻

试题描述

单身!
依然单身！
吉哥依然单身！
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无关的数字的平方和。

输入

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

输出

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

输入示例





输出示例








数据规模及约定


见“输入”


题解


这题在状态设计上挺普通的，就是需要记好几个东西：设状态 (i, j, k, l) 表示 i 位数，最高位为 j，数字和对 7 取模等于 k，数对 7 取模等于 l。num(i, j, k, l) 记录个数，sum(i, j, k, l) 记录总和，f(i, j, k, l) 记录平方和，然后转移时推推式子就好了。




#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

#define LL long long

LL read() {

	LL x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 20

#define MOD 1000000007

LL f[maxn][10][7][7], sum[maxn][10][7][7], N[maxn][10][7][7], ten[maxn];

bool has[maxn][10][7][7];

int num[maxn];

LL cal(LL x) {

	if(!x) return 0;

	int cnt = 0; LL tx = x;

	while(x) num[++cnt] = x % 10, x /= 10;

	LL ans = 0, sm = 0, s = 0, Sum = 0; int sn = 0, aa = 0;

	for(int i = cnt - 1; i; i--)

		for(int j = 1; j <= 9; j++)

			for(int k1 = 1; k1 < 7; k1++)

				for(int k2 = 1; k2 < 7; k2++)

					(ans += f[i][j][k1][k2]) %= MOD,

					(aa += N[i][j][k1][k2]) %= MOD,

					(Sum += sum[i][j][k1][k2]) %= MOD;

	bool ok = 1;

	for(int i = cnt; i; i--) {

		for(int j = i < cnt ? 0 : 1; j < num[i]; j++)

			for(int k1 = 1; k1 < 7; k1++)

				for(int k2 = 1; k2 < 7; k2++) {

					int K1 = ((k1 - sn) % 7 + 7) % 7,

						K2 = (((LL)k2 - s) % 7 + 7) % 7;

					ans += f[i][j][K1][K2] + (sm * sum[i][j][K1][K2] << 1) + (sm * sm % MOD) * N[i][j][K1][K2];

					ans %= MOD;

					(Sum += sum[i][j][K1][K2] + sm * N[i][j][K1][K2]) %= MOD;

					(aa += N[i][j][K1][K2]) %= MOD;

				}

		(sm += ten[i-1] * num[i]) %= MOD; s += ten[i-1] * num[i]; sn += num[i];

		if(num[i] == 7){ ok = 0; break; }

	}

	LL ttx = tx % MOD;

	if(sn % 7 && s % 7 && ok) (ans += ttx * ttx) %= MOD, (Sum += ttx) %= MOD, aa++;

//	printf("%lld: %d %lld %lld\n", tx, aa, Sum, ans);

	return ans;

}

int main() {

	ten[0] = 1;

	for(int i = 1; i < maxn - 1; i++) ten[i] = ten[i-1] * 10;

	N[0][0][0][0] = 1; has[0][0][0][0] = 1;

	for(int i = 0; i < maxn - 1; i++)

		for(int j = 0; j <= 9; j++)

			for(int k = 0; k < 7; k++)

				for(int l = 0; l < 7; l++) if(has[i][j][k][l]) {

					for(int x = 0; x <= 9; x++) if(x != 7) {

						LL t = x * ten[i], tt = t % MOD;

						has[i+1][x][(k+x)%7][(t+l)%7] = 1;

						(N[i+1][x][(k+x)%7][(t+l)%7] += N[i][j][k][l]) %= MOD;

						(sum[i+1][x][(k+x)%7][(t+l)%7] += sum[i][j][k][l] + tt * N[i][j][k][l]) %= MOD;

						f[i+1][x][(k+x)%7][(t+l)%7] += f[i][j][k][l] + (tt * tt % MOD) * N[i][j][k][l] + (tt * sum[i][j][k][l] << 1);

						f[i+1][x][(k+x)%7][(t+l)%7] %= MOD;

					}

//					printf("%d %d %d %d: %lld\n", i, j, k, l, sum[i][j][k][l]);

				}

	int T = read();

	while(T--) {

		LL l = read(), r = read();

		printf("%lld\n", (cal(r) - cal(l - 1) + MOD) % MOD);

	}

	return 0;

}





相关文章