恼人的数学作业(数字 dp)
最编程
2024-04-20 20:41:58
...
题目链接:https://www.luogu.com.cn/problem/P4999
很明显,本题是数位dp
Solve
我们定义\(f[i][j](1<=i<=19,0<=j<=9)\)表示i位数字以j为最高位的数字的数字和
当j为0时表示\(\sum f[i-1][j](0<=j<=9)\)
我们需要预处理出f数组
很明显,初值可以是这样赋:f[1][x]=x;(0<=x<=9)
我们考虑f[i][j]其实是在f[i-1][j]后面加上0~9的数字
因此很容易想出转移方程: f[i][j]=(f[i][0]+j*power(i-1))%mod;
其中mod是模数,power(x)表示10的x次方
统计答案实际上就是求\(getans(r)-getans(l-1)\)
getans表示1~r所有数字的数字和
getans的求法
long long getans(long long x)
{
if(x==0)return 0;
long long xx=x,ans=0,len=getlen(x),ist=getist(x);
for(int j=ist-1;j>=0;j--)ans=(ans+f[len][j])%mod;
//统计整块
x-=ist*power(len-1);
return (ans+1LL*ist*(x+1)%mod+getans(x))%mod;
//统计零散小块
}
Code
#include<bits/stdc++.h>
using namespace std;
int t;
long long f[25][10],sqd[25],ll,rr;
long long mod=1000000007;
int getlen(long long x)//求位数
{
int n=0;
while(x)
{
n++;
x/=10;
}
return n;
}
long long getist(long long x)//求最高位
{
while(x>=10)x/=10;
return x;
}
long long power(int x)//求10的x次方
{
long long an=1;
for(int i=1;i<=x;i++)an*=10;
return an;
}
long long getans(long long x)//求1~x的数字和
{
if(x==0)return 0;
long long xx=x,ans=0,len=getlen(x),ist=getist(x);
for(int j=ist-1;j>=0;j--)ans=(ans+f[len][j])%mod;
x-=ist*power(len-1);
return (ans+1LL*ist*(x+1)%mod+getans(x))%mod;
}
int main()
{
for(int i=0;i<=9;i++)f[1][i]=i;
for(int i=2;i<=19;i++)
{
for(int j=0;j<=9;j++)
f[i][0]=(f[i][0]+f[i-1][j])%mod;
for(int j=1;j<=9;j++)
f[i][j]=(f[i][0]+j*power(i-1))%mod;
}
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&ll,&rr);
printf("%lld\n",(getans(rr)-getans(ll-1)+mod)%mod);
}
return 0;
}
下一篇: 纯数学作业 - 第 0 章
推荐阅读
-
小明非常喜欢数学,有一次做数学作业时,老师让他计算 9~16 的和,他马上写出了正确答案是 100,但他并不满足于此,他想知道有多少个连续的正数序列的和(至少包括两个数)是 100。-说明
-
恼人的数学作业(数字 dp)
-
小明非常喜欢数学,有一次做数学作业时,老师让他计算 9~16 的和,他马上写出了正确答案 100。但他并不满足于此,他想知道有多少个连续的正数序列的和(至少包括两个数)是 100。-源代码
-
简单的数学作业
-
MM的数学作业
-
第一天的数学作业
-
[BZOJ2326] [HNOI2011] 数学作业 [矩阵乘法] [DP]
-
Python | 10 年级侄子的数学作业
-
只有计算机才能完成的初等数学作业 - 情景 1:序列表
-
P4999 无聊的数学作业(计算 dp)