AcWing 1086. 恨7不成妻
单身!
依然单身!
吉哥依然单身!
DS 级码农吉哥依然单身!
所以,他平生最恨情人节,不管是 214还是 77,他都讨厌!
吉哥观察了 214和 77这两个数,发现:
2+1+4=7
7+7=7×2
77=7×11
最终,他发现原来这一切归根到底都是因为和 7有关!
所以,他现在甚至讨厌一切和 7有关的数!
什么样的数和 7有关呢?
如果一个整数符合下面三个条件之一,那么我们就说这个整数和 7有关:
1.整数中某一位是 7;
2.整数的每一位加起来的和是 7的整数倍;
3.这个整数是 7的整数倍。
现在问题来了:吉哥想知道在一定区间内和 7无关的整数的平方和。
输入格式
第一行包含整数 T,表示共有 T组测试数据。
每组数据占一行,包含两个整数 L和 R。
输出格式
对于每组数据,请计算 [L,R]中和7无关的数字的 平方和 ,并将结果对 10^9+7取模后输出。
数据范围
1≤T≤50,
1≤L≤R≤10^18
3
1 9
10 11
17 17
236
221
0
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const LL N = 20 , P = 1e9 + 7;
struct F{
LL s0 , s1 , s2;
}f[N][10][7][7];
LL power7[N] , power9[N];//10^i%7,10^i%P
LL mod(LL x , LL y)//避免得到负数
{
return (x % y + y) % y;
}
void init()
{
//初始化长度是1的情况
for(int i = 0 ; i < 10 ; i++)
if(i != 7)
{
auto &v = f[1][i][i % 7][i % 7];
v.s0++;
v.s1 += i;
v.s2 += i * i;
}
LL p = 10;//倍率
for(int i = 2 ; i < N ; i++ , p *= 10)//位数
for(int j = 0 ; j < 10 ; j++)//最高位
{
if(j == 7) continue;
for(int a = 0 ; a < 7 ; a++)//该数 % 7 余数
for(int b = 0 ; b < 7 ; b++)//各位之和 % 7 余数
for(int k = 0 ; k < 10 ; k++)//枚举0-9
{
if(k == 7) continue;
//v2是v1所依赖的状态
auto &v1 = f[i][j][a][b] , &v2 = f[i - 1][k][mod( a-j*mod(p , 7) , 7 )][mod(b - j , 7)];
//开启痛苦面具,对照上面的公式,时刻提醒记得及时取模!!!!!!
v1.s0 = mod(v1.s0 + v2.s0 , P);
v1.s1 = mod(v1.s1 + j * (p % P) % P * v2.s0 % P + v2.s1 , P);
v1.s2 = mod(v1.s2 +
v2.s0 * j % P * (p % P) % P * j % P * (p % P) % P +
2 * j % P * (p % P) % P * v2.s1 % P +
v2.s2 , P);
}
}
power7[0] = power9[0] = 1;
for(int i = 1 ; i < N ; i++)
{
power7[i] = power7[i - 1] * 10 % 7;
power9[i] = power9[i - 1] * 10 % P;
}
}
//求出i位,且最高位是j,且本身模7不等于a,且各位数之和模7不等b的集合
//因为预处理的f[i][j][a][b]是本身模7等于a,且各位数之和模7等于b的集合,因此需要两趟for循环来实现
F get(int i , int j , int a , int b)
{
LL s0 = 0 , s1 = 0 , s2 = 0;
for(int x = 0 ; x < 7 ; x++)
for(int y = 0 ; y < 7 ; y++)
{
if(x == a || y == b) continue;
auto v = f[i][j][x][y];
s0 = mod(s0 + v.s0 , P);
s1 = mod(s1 + v.s1 , P);
s2 = mod(s2 + v.s2 , P);
}
return {s0 , s1 , s2};
}
LL dp(LL n)
{
if(!n) return 0;
LL backup_n = n % P;//备份一个n
vector<int> nums;
while(n) nums.push_back(n % 10) , n /= 10;
LL res = 0;
LL last_a = 0 , last_b = 0;//last_a表示前缀本身的值,last_b表示前缀各位数之和
for(int i = nums.size() - 1 ; i >= 0 ; i--)
{
int x = nums[i];
for(int j = 0 ; j < x ; j++)
{
if(j == 7) continue;
int a = mod(-last_a * power7[i + 1] , 7) , b = mod(-last_b , 7);
auto v = get(i + 1 , j , a , b);//求得本身模7不等于a,并且各位数之和模7不等b的集合,此时就可以使用预处理出来的结构体
//根据公式求s2,时刻提醒记得及时取模!!!!!!
res = mod(res +
(last_a % P) * (last_a % P) % P * (power9[i + 1] % P) % P * (power9[i + 1] % P) % P * v.s0 % P +
2 * (last_a % P) * (power9[i + 1] % P) % P * v.s1 % P +
v.s2 ,
P);
}
if(x == 7) break;
last_a = last_a * 10 + x;
last_b += x;
//记得特判n本身
if(!i && last_a % 7 && last_b % 7) res = mod(res + backup_n * backup_n , P);
}
return res;
}
int main()
{
init();
int T;
cin >> T;
while(T--)
{
LL l , r;
cin >> l >> r;
cout << mod(dp(r) - dp(l - 1) , P) << endl;
}
}