单身!
依然单身!
吉哥依然单身!
DS级码农吉哥依然单身!
所以,他生平最恨情人节,不管是214还是77,他都讨厌!
吉哥观察了214和77这两个数,发现:
2+1+4=7
7+7=7*2
77=7*11
最终,他发现原来这一切归根到底都是因为和7有关!所以,他现在甚至讨厌一切和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无关的数字的平方和。
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 思路:还是数位DP,套用模板,求的是平方和,记录其后数位满足条件的个数即可,比如233, 234, 235满足,则平方和为(200+33)^2+(200+34)^2+(200+35)^2 = 3*200^2 + 2*200*(33+34+35)+33^2+34^2+35^2,记录下每次的和与平方和维护即可
typedef long long LL;
typedef pair<LL, LL> PLL; const int MOD = 1e9+; struct Node {
LL num, sum, ssum;
} dp[][][]; LL a[], p[]; Node dfs(int pos, int pre, int presum, bool limit) {
if(pos == -) {
Node ret;
ret.num = (pre != && presum != );
ret.sum = ret.ssum = ;
return ret;
}
if(!limit && dp[pos][pre][presum].num != -) return dp[pos][pre][presum];
int up = limit?a[pos]:;
Node ans;
ans.num = ans.sum = ans.ssum = ;
for(int i = ; i <= up; ++i) {
if(i == ) continue;
Node nex = dfs(pos-, (pre+i)%, (presum*+i)%, limit&&i==a[pos]);
if(nex.num == ) continue;
ans.num = ((ans.num + nex.num) % MOD + MOD) % MOD;
ans.sum = ((ans.sum + nex.sum + (p[pos]*i)%MOD*nex.num) % MOD + MOD) % MOD;
ans.ssum = ((ans.ssum + nex.ssum + ((*p[pos]*i) % MOD)*nex.sum) % MOD + MOD) % MOD;
ans.ssum = ((ans.ssum + (p[pos]*nex.num)%MOD * p[pos] % MOD *i*i) % MOD + MOD) % MOD;
}
if(!limit) dp[pos][pre][presum] = ans;
return ans;
} LL solve(LL n, LL m) {
int pos = ;
while(n) {
a[pos++] = n % ;
n /= ;
}
LL t1 = dfs(pos-, , , true).ssum;
pos = ;
while(m) {
a[pos++] = m % ;
m /= ;
}
t1 = dfs(pos-, , , true).ssum - t1;
return (t1%MOD+MOD)%MOD;
} void run_case() { LL n, m;
cin >> n >> m;
cout << solve(n-, m) << "\n";
} int main() {
ios::sync_with_stdio(false), cin.tie();
int t;
cin >> t;
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
for(int k = ; k < ; ++k)
dp[i][j][k].num = -;
p[] = ;
for(int i = ; i < ; ++i)
p[i] = (p[i-]*)%MOD;
while(t--)
run_case();
return ;
}