HDU-4507


题目地址:点此传送
题目
Problem Description
单身!   
依然单身!   
吉哥依然单身!   
DS级码农吉哥依然单身!   
所以,他生平最恨情人节,不管是214还是77,他都讨厌!      
吉哥观察了214和77这两个数,发现:   
$2+1+4=7$   
$7+7=7\times 2 $ 
$77=7\times 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
HINT
2013腾讯编程马拉松初赛第一场(3月21日)
题意

看题(略)

思路

数位dp,以前只做过记录个数的没做过记录和,第一眼我把记录的个数改成平方和,一直t也不知道咋回事……后来搜的题解,还是利用求个数,就是多记录了两个数
$c^2=(a+b)^2=a^2+2\times b+b^2$
假设找到第i个位置时,搜索数的大小为 $i\times pow(i,pos)$,这个位置之后的数字为num1,num2,num3 …. numN,则 i位以后所有满足数的平方和为
$=((i\times pow(i,pos)+num1)^2+(i\times pow(i,pos)+num2)^2 +$
$(i\times pow(i,pos)+num3)^2+\dots +(i\times pow(i,pos)+numN)^2)$
$ =N\times (i\times pow(i,pos)^2)^2+2\times i\times pow(i,pos)\times (num1+num2+num3$
$+\dots+numN)+(num1^2+num2^2+num3^2+\dots +numN^2)$

所以我们只需维护满足的个数 n ,num的和,$num^2$就行
开个结构体dp[pos][num][sum].c 代表次数 dp[pos][num][sum].sum 代表num和 dp[pos][num][sum].sqsum 平方和 (其他 pos 第几位,num数字,sum每一位位和)
dp很巧妙,具体看代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
void read(ll &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
struct ss{

ll c;
ll sum;
ll sqsum;

}dp[20][10][10];
int d[20];
ss dfs(int pos,int num,int sum,int limit){

if(!limit&&dp[pos][num][sum].c!=-1) return dp[pos][num][sum];
int end=limit?d[pos]:9;
ll p=pow(10LL,pos);
ss ans;
ans.c=ans.sum=ans.sqsum=0;
for(int i=0;i<=end;i++){
if(i==7) continue;
if(pos==0) {if((sum+i)%7&&(i+num)%7) { ans.c++;ans.sum+=i;ans.sqsum+=i*i;}}
else
{
//p pow(10,pos) 变为该位置数的大小
ss k=dfs(pos-1,(num+i*p)%7,(sum+i)%7,limit&(i==end));
ans.c=(ans.c+k.c)%mod; //次数 等于他后面的所有次数和
ll q1=(i*p)%mod; //上面推导的 i*pow(10,pos)
ll q2=(q1*q1)%mod; // (i*pow(10,pos))^2
ans.sum=(ans.sum+k.sum+k.c*q1)%mod;
//每个数都有增加个 i*pow(10,pos)所以一共增加 k.c*q1 再加上原来的
ans.sqsum=(ans.sqsum+(k.c*q2%mod)+((k.sum*q1%mod)*2)%mod+k.sqsum)%mod;
//利用上面推导
}


}
if(!limit){
dp[pos][num][sum].c=ans.c;
dp[pos][num][sum].sum=ans.sum;
dp[pos][num][sum].sqsum=ans.sqsum;
}
return ans;

}

ll solve(ll x){
if(x==0) return x;
int cnt=0;
while(x){d[cnt++]=x%10;x/=10;}
return dfs(cnt-1,0,0,1).sqsum%mod;

}
int main()
{
for(int i=0;i<20;i++)
for(int j=0;j<10;j++)
for(int k=0;k<10;k++)
dp[i][j][k].c=dp[i][j][k].sum=dp[i][j][k].sqsum=-1;
ll a,b;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&a,&b);
printf("%lld\n",(solve(b)-solve(a-1)+mod)%mod);
}


return 0;
}
如果对您有帮助,请小小支持一下,您的支持将鼓励我继续创作!
0%