吉哥系列故事——恨7不成妻(数位DP)

时间：2021-11-23 00:26:35

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

http://acm.hdu.edu.cn/showproblem.php?pid=4507

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

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
3
1 9
10 11
17 17
 
Sample Output
236
221
 
 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 struct DP{

     ll cnt,sum,sqsum;

     DP(ll a=,ll b=,ll c=):cnt(a),sum(b),sqsum(c){}

 }dp[][][];

 int a[];

 ll fac[];

 DP dfs(int pos,int aa,int bb,bool limit){

     if(pos==-) return DP(aa!=&&bb!=,,);

     if(!limit&&dp[pos][aa][bb].cnt!=-) return dp[pos][aa][bb];

     int up=limit?a[pos]:;

     DP ans;

     for(int i=;i<=up;i++){

         if(i!=){

             DP tmp=dfs(pos-,(aa+i)%,(bb*+i)%,limit&&i==up);

             ans.cnt=(ans.cnt+tmp.cnt)%MOD;

             ans.sum=(ans.sum+(((fac[pos]*i)%MOD*tmp.cnt)%MOD)+tmp.sum)%MOD;

             ans.sqsum=((ans.sqsum+tmp.sqsum+(*fac[pos]*i)%MOD*tmp.sum)%MOD)%MOD;

             ans.sqsum=(ans.sqsum+((i*fac[pos]*i%MOD)*fac[pos]%MOD*tmp.cnt)%MOD)%MOD;

         }

     }

     if(!limit) dp[pos][aa][bb]=ans;

     return ans;

 }

 ll solve(ll x){

     int pos=;

     while(x){

         a[pos++]=x%;

         x/=;

     }

     DP ans=dfs(pos-,,,);

     return ans.sqsum;

 }

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     fac[]=;

     for(int i=;i<;i++) fac[i]=(fac[i-]*)%MOD;

     for(int i=;i<;i++){

         for(int j=;j<;j++){

             for(int k=;k<;k++){

                 dp[i][j][k].cnt=-;

             }

         }

     }

     int t;

     cin>>t;

     ll n,m;

     while(t--){

         cin>>n>>m;

         ll ans=(solve(m)-solve(n-)+MOD)%MOD;

         cout<<ans<<endl;

     }

 }

相关文章