首先来说,,这题我wrong了好几次,代码力太弱啊。。很多细节没考虑。。
题意:给定两个数 L R,1 <= L <= R <= 10^18 ;求L 到 R 间 与 7 无关的数的平方和
什么数与7 无关?
1 没有数字7
2 不是7的倍数
3 所有数字的和不是7的倍数
我们先来考虑一下 如果这题问的是: L 到 R 间 与7 无关的数有多少个?
这道题该怎么思考? 给一点提示 dp 方程可以写成三维的 num(i,j,k) 其中 i 代表数的位数 j 代表 这个数对7取模的余数 k 代表这个数所有数字和对7取模的值,至于num(i,j,k) 当让就是这种数的个数了, 方程的转化也很简单 从数末尾逐步填数字 l (0~9)的话 num(i+1,(j*10+l)%7,(k+l)%7)+=num(i,j,k);
接下来 我默认你知道 num[i][j][k] 该怎么求了 这个时候 再来考虑一下 L 到 R 间与7 无关的数的和 ? 这个时候不用考虑的太复杂,,因为首先,你在求num[i][j][k]的时候已经求出了所有的满足条件的数的所有可能,要求和,无非就是哪一位的那个数字有多少个。
如果我们的dp是逐步往数的末尾填数 ,这个时候可以这样写 sum(i,j,k)其中i,j,k和num的i,j,k一个意思,然后sum表示满足这种情况的数的和 方程的转换可以写为:同样从数末尾逐步填数字 l (0~9)-- num(i+1,(j*10+l)%7,(k+l)%7)+=sum(i,j,k)*10+num(i,j,k)*l;
再来考虑平方和就比较容易了,,我们知道如果前面的数是a 我们往后面塞一个数字l 那么我们要求的数的平方和是---(10*a+l)^2 也就是100*a*a+20*a*l+l*l
方程我就不写了,,然后接下来的思路都是和上面的类似
贴出渣渣的代码。。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<stdlib.h>
#include <vector>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define ll __int64
#define CL(a,b) memset(a,b,sizeof(a))
#define MAXNODE 100010
ll MOD=; ll s,e; ll dp[][][];
ll wsu[][][];
ll num[][][];
ll val[];
void initval()
{
int i=;
val[]=;
val[]=;
for(i=;i<=;i++)
{
val[i]=val[i-]*;
}
} void initdp()
{
int i,j,k,l;
CL(dp,);
CL(num,);
CL(wsu,);
for(i=;i<;i++)
{
if(i==)continue;
dp[][i%][i%]+=i*i;
wsu[][i%][i%]+=i;
num[][i%][i%]++;
}
num[][][]=;
for(i=;i<;i++)
{
for(j=;j<;j++)
{
for(k=;k<;k++)
{
for(l=;l<;l++)
{
if(l==)continue;
num[i+][(j+l)%][(k*+l)%]+=num[i][j][k]%MOD;
num[i+][(j+l)%][(k*+l)%]%=MOD;
wsu[i+][(j+l)%][(k*+l)%]+=(wsu[i][j][k]*(ll)+(ll)l*(num[i][j][k]))%MOD;
wsu[i+][(j+l)%][(k*+l)%]%=MOD;
dp[i+][(j+l)%][(k*+l)%]+=(((ll)l*(ll)l*num[i][j][k])+dp[i][j][k]*+(ll)*(ll)l*wsu[i][j][k]*(ll))%MOD;
dp[i+][(j+l)%][(k*+l)%]%=MOD;
}
// printf("%d %d %d %I64d\n",i,j,k,dp[i][j][k]);
}
}
}
} ll pro(ll n)
{
if(n==)return ;
ll rem=;
ll nu[];
int w,i,j,k;
nu[]=;
ll tem=n,va;w=,rem=;
while(tem!=)
{
nu[w]=tem%;
tem/=;
w++;
}
va=;
int su=;
ll v=;
while(--w)
{
if(nu[w]==)
{
for(i=;i<w;i++)nu[i]=;
nu[w]=;
}
for(i=nu[w]-;i>=;i--)
{
if(i==)continue;
for(j=;j<;j++)
{
for(k=;k<;k++)
{
if((su+i+j)%==)continue;
if(((ll)v+(ll)i*val[w]+(ll)k)%==)continue;
ll pre=(va+(ll)i*(val[w]%MOD))%MOD;
pre%=MOD;
rem+=(((pre*pre)%MOD)*(num[w-][j][k]%MOD))%MOD;
rem%=MOD;
rem+=dp[w-][j][k]%MOD;;
rem%=MOD;
rem+=((((ll)*pre)%MOD)*wsu[w-][j][k]%MOD)%MOD;
rem%=MOD;
}
}
}
rem%=MOD;
va+=(nu[w]*(val[w]%MOD))%MOD;
va%=MOD;
v+=nu[w]*(val[w]%);
v%=;
su+=nu[w];
su%=;
}
if(v!=&&su!=)rem+=(va*va)%MOD;
return rem%MOD;
} int main()
{
int tt;
initval();
initdp();
scanf("%d",&tt);
while(tt--)
{
scanf("%I64d %I64d",&s,&e);
ll rs=pro(s-1LL);
ll re=pro(e);
ll rem=re-rs;
rem=rem%MOD;
if(rem<)rem+=MOD;
// printf("%I64d %I64d ",rs,re);
printf("%I64d\n",rem);
}
return ;
}