一本通1590恨 7 不成妻

1590：恨 7 不成妻

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

单身！

依然单身！

吉哥依然单身！

DS 级码农吉哥依然单身！

所以，他平生最恨情人节，不管是 7，他都讨厌！

吉哥观察了 77 这两个数，发现：

最终，他发现原来这一切归根到底都是因为和 7 有关的数！

什么样的数和 7 有关：

整数中某一位是；

整数的每一位加起来的和是 7 的整数倍；

这个整数是 7 的整数倍。

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

【输入】

输入数据的第一行是测试数据组数 T 组测试数据。

每组数据在一行内包含两个正整数。

【输出】

对于每组数据，请计算 [ 取模后输出。

【输入样例】

【输出样例】

236
221
0

【提示】

数据范围与提示：

对于全部数据，1≤T≤50,1≤L≤R≤10^18 。

$1 \leq T \leq 50, 1 \leq L \leq R \leq 10^{18}$

下一个状态是tmp，这个状态的平方和+=（A+tmp[与7无关的数的和]）², 就是A²+2*A*tmp[与7无关的数的和]+{（tmp[与7无关的数的和]²）=（tmp[与7无关的数的平方和]）}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-');
        ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
inline void writeln(ll x)
{
    write(x);
    putchar('
');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) writeln(x)
const ll Mod=1000000007;
int T,Num[20];
ll Bin[20];
struct Record
{
    ll Ges,Shuz_he,Pingf_he;
    bool Vis;
}dp[20][10][10][2][2];
inline Record dfs(int Weiz,int Pre1,int Pre2,bool Shangj,bool Qiand0)
{
    if(dp[Weiz][Pre1][Pre2][Shangj][Qiand0].Vis) return dp[Weiz][Pre1][Pre2][Shangj][Qiand0];
    if(Weiz==0)
    {
        return dp[Weiz][Pre1][Pre2][Shangj][Qiand0]=(Record){(Pre1&&Pre2)?1:0,0,0,1};
    }
    Record ans=(Record){0,0,0,1};
    int i,Up=(Shangj)?(Num[Weiz]):(9);
    for(i=0;i<=Up;i++) if(i!=7)
    {
        bool Bo1=(Shangj&&i==Up),Bo2=(Qiand0&&i==0);
        Record tmp=dfs(Weiz-1,(Pre1+i)%7,(Pre2*10+i)%7,Bo1,Bo2);
        ll A=i*Bin[Weiz]%Mod;
        ans.Ges+=tmp.Ges;
        ans.Ges-=(ans.Ges>=Mod)?Mod:0;
        ans.Shuz_he+=(tmp.Shuz_he+A*tmp.Ges%Mod)%Mod;
        ans.Shuz_he-=(ans.Shuz_he>=Mod)?Mod:0;
        ans.Pingf_he+=(tmp.Pingf_he+2*A*tmp.Shuz_he%Mod+A*A%Mod*tmp.Ges%Mod)%Mod;
        ans.Pingf_he-=(ans.Pingf_he>=Mod)?Mod:0;
    }
    return (dp[Weiz][Pre1][Pre2][Shangj][Qiand0]=ans);
}
inline ll Solve(ll n)
{
    *Num=0;
    while(n)
    {
        Num[++*Num]=n%10;
        n/=10;
    }
    int i,j,k,ii,jj;
    for(i=0;i<20;i++) for(j=0;j<10;j++) for(k=0;k<10;k++)
    for(ii=0;ii<2;ii++) for(jj=0;jj<2;jj++) dp[i][j][k][ii][jj].Vis=0;
    return dfs(*Num,0,0,1,1).Pingf_he%Mod;
}
int main()
{
    int i;
    Bin[1]=1;
    for(i=2;i<=20;i++) Bin[i]=(Bin[i-1]*10)%Mod;
    ll l,r;
    R(T);
    while(T--)
    {
        R(l); R(r);
        Wl(((Solve(r)-Solve(l-1))%Mod+Mod)%Mod);
    }
    return 0;
}
/*
input
3
1 9
10 11
17 17
output
236
221
0
*/

View Code