hdu4507 吉哥系列故事——恨7不成妻

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

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1059 Accepted Submission(s): 328

Problem Description

　　单身!
　　依然单身！
　　吉哥依然单身！
　　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

Sample Output

236
221
0
这一题我们可以看出，要求是很多的，这里很容易从数据大小和时限可以看出是必须用dp做的，要求不和７相关的平方和，我们推得，如果，在当位是t,且下一位，可以用n个，那么我们可以得出，各数之后，sum[i]＝t*p[i]*i+s[i-1],各数平方各s[i]=n*t*t*p[i]*p[i]+2*t*p[i]+s1[i-1]+s2[i-1];得到这两个公式就容易了，可以马上，用个结构存起来，搜得结果！
#include <iostream>

#include <stdio.h>
#include <string.h>
using namespace std;
#define M  100
int pri[M];
#define MOD 1000000007
struct node {
    __int64 cnt,s1,s2;
    node(__int64 tcnt=0,__int64 ts1=0,__int64 ts2=0){
        cnt=tcnt,s1=ts1,s2=ts2;
    }
}dp[M][7][7][3];
bool flag[M][7][7][3];
__int64 ten[30];
node dfs(int pos,int t,int s,int mod,int f){
    if(pos==0){
        if(t||mod==0||s==0)
        return node(0,0,0);
        return node(1,0,0);
    }
    if(!f&&flag[pos][s][mod][t])return dp[pos][s][mod][t];
    int u=f?pri[pos]:9;
    node ans;
    for(int i=0;i<=u;i++){
        node temp=dfs(pos-1,t||i==7,(s+i)%7,(mod*10+i)%7,f&&i==u);
        ans.cnt=(ans.cnt+temp.cnt)%MOD;
        __int64 k=i*ten[pos-1]%MOD;
        ans.s1=(temp.cnt*k%MOD+temp.s1+ans.s1)%MOD;
        ans.s2=(k*k%MOD*temp.cnt%MOD+k*temp.s1%MOD*2+temp.s2+ans.s2)%MOD;
    }
    if(!f)flag[pos][s][mod][t]=true,dp[pos][s][mod][t]=ans;
    return ans;
}
__int64 solve(__int64 x){
    int cnt=0;
    while(x){
        pri[++cnt]=x%10;x/=10;
    }
    node temp=dfs(cnt,0,0,0,1);
    return temp.s2;
}
int main()
{
    int tcase;
    __int64 l,r;
    memset(flag,false,sizeof(flag));
    ten[0]=1;
    for(int i=1;i<30;i++)
    ten[i]=ten[i-1]*10%MOD;
    scanf("%d",&tcase);
    while(tcase--){
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",(solve(r)-solve(l-1)+MOD)%MOD);
    }
    return 0;
}

hdu4507 吉哥系列故事——恨七不成妻

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

相关推荐