Acwing 1086. 恨7不成妻
Intro
题目传送门
给定闭区间 [L,R],求这个区间内所有满足以下条件的数的平方和:
- 整数中每一位都不是 7。
- 整数中每一位加起来的和不是 7 的整数倍。
- 整数不是 7 的整数倍。
Solution
容易发现,我们为了快速处理长度为 i,开头为 j 的所有满足条件的数的平方和,需要将每一位的和与这个整数放进状态里。
所以我们定义状态为:fi,j,a,b 表示共有 i 位,开头为 j,这个数模 7 为 a,各位数字之和模 7 余数为 b。
这样的话我们可以从 fi−1,k,a−j×10i−1,b−j 转移上来。
但我们要求的是平方和,怎么办?
重要
对于一个形如 jAi(i∈[1,t]) 的 i 位数,我们可以将其转换一下,举个例子:
(jA1)2+(jA2)2+⋯+(jAt)2=(j×10i−1)2×t+2×j×10i−1×(A1+A2+⋯+At)+A12+A22+⋯+At2
所以我们只需要知道 t 和 ∑Ai 和 ∑Ai2 就能快速得到下一层的方案数,同理我们来看看怎么得到 jA1+jA2+⋯+jAt。
jA1+jA2+⋯+jAt=j×10i−1×t+(A1+A2+⋯+At)
Code
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 20;
const LL MOD = 1e9+7;
struct F {
LL s0 , s1 , s2;
} f[N][10][7][7];
LL power7[N] , power10[N];
int mod(LL x , int y) {
return (x % y + y) % y;
}
void init() {
for(int i = 0 ; i <= 9 ; i ++)
if(i != 7) {
auto& v = f[1][i][i%7][i%7];
v.s0 ++; v.s1 += i; v.s2 += i*i;
}
LL power = 10;
for(int i = 2 ; i < N ; i ++ , power *= 10)
for(int j = 0 ; j <= 9 ; j ++) {
if(j == 7) continue;
for(int a = 0 ; a < 7 ; a ++)
for(int b = 0 ; b < 7 ; b ++) {
auto& v1 = f[i][j][a][b];
for(int k = 0 ; k <= 9 ; k ++) {
auto& v2 = f[i-1][k][mod(-power*j+a,7)][mod(b-j,7)];
v1.s0 = mod(v1.s0 + v2.s0, MOD);
v1.s1 = mod(v1.s1 + v2.s1 + j * (power % MOD) % MOD * v2.s0, MOD);
v1.s2 = mod(v1.s2 +
j * j * (power % MOD) % MOD * (power % MOD) % MOD * v2.s0 +
v2.s2 +
2 * j * power % MOD * v2.s1
, MOD);
}
}
}
power7[0] = power10[0] = 1ll;
for(int i = 1 ; i < N ; i ++) {
power7[i] = power7[i-1]*10ll % 7;
power10[i] = mod(power10[i-1]*10ll , MOD);
}
}
F get(int i , int j , int a , int b) {
LL s0 = 0 , s1 = 0 , s2 = 0;
for(int x = 0 ; x < 7 ; x ++) {
if(x == a) continue;
for(int y = 0 ; y < 7 ; y ++) {
if(y == b) continue;
auto v = f[i][j][x][y];
s0 = mod(s0 + v.s0 , MOD);
s1 = mod(s1 + v.s1 , MOD);
s2 = mod(s2 + v.s2 , MOD);
}
}
return {s0 , s1 , s2};
}
LL calc(LL n) {
if(!n) return 0;
LL bkn = n%MOD;
vector<int> nums;
while(n) nums.push_back(n%10) , n/=10;
LL res = 0;
LL last1 = 0; // 数字 N
LL last2 = 0; // 各位数字之和
for(int i = nums.size()-1 ; i >= 0 ; i --) {
int x = nums[i];
for(int j = 0 ; j < x ; j ++) {
if(j == 7) continue;
// last1 A + ? != 0(mod 7) => ? != -last1 A
int a = mod(-last1*power7[i+1] , 7);
// last2 + ? != 0(mod 7) => ? != -last2(mod 7)
int b = mod(-last2 , 7);
// 此处 a , b 为不合法的 a 和 b
auto v = get(i+1 , j , a , b);
res = mod(res +
power10[i+1]*power10[i+1]%MOD*(last1%MOD)%MOD*(last1%MOD)%MOD*v.s0%MOD+
power10[i+1]*2ll%MOD*last1%MOD*v.s1%MOD+
v.s2
,MOD);
}
if(x == 7) break;
last1 = last1*10 + x;
last2 = last2+x;
if(!i && last1%7 != 0 && last2%7 != 0) res = mod(res + bkn*bkn , MOD);
}
return res;
}
void slove() {
LL L , R;
scanf("%lld%lld" , &L , &R);
printf("%d\n" , mod(calc(R) - calc(L-1) , MOD));
return;
}
int main() {
init();
int T; scanf("%d" , &T);
while(T --) slove();
return 0;
}