@[Illusory_](/user/154101)
??什么意思?
by Chancylaser @ 2019-12-14 08:52:35
~~有一个数kkk~~
by 小鲍bob @ 2019-12-14 08:54:29
@[初音Yiku](/user/241817) 如果kk过大,会爆longlong。
by MatrixCascade @ 2019-12-14 08:56:08
@[初音Yiku](/user/241817) 对不起,我也搞错了,必须数位dp。
by MatrixCascade @ 2019-12-14 09:00:04
@[初音Yiku](/user/241817) P2602了解下
by yummy @ 2019-12-14 09:03:05
@[Illusory_](/user/154101)
```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long l,r;
int rt[21],se[21];
long long dp1[21],dp2[21];
ll pw(ll a,ll n)
{
ll ans=1;
while(n)
{
if(n&1) ans=(ans*a);
a=(a*a);
n>>=1;
}
return ans;
}
void pre(long long x,long long *dp)
{
long long cnt[20]={0};
int le=0;
while(x)
{
le++;
cnt[le]=x%10;
x/=10;
}
for(int i=le;i>=1;--i)
{
for(int j=0;j<=9;++j)
{
dp[j]+=se[i-1]*cnt[i];
}
for(int j=0;j<cnt[i];++j)
{
dp[j]+=rt[i-1];
}
long long ans=0;
for(int j=i-1;j>=1;--j)
{
ans=ans*10+cnt[j];
}
dp[cnt[i]]=dp[cnt[i]]+ans+1;
dp[0]-=rt[i-1];
}
}
signed main() {
int kk;
scanf("%lld",&kk);
rt[0]=1;
for(int i=1;i<=15;++i)
{
se[i]=se[i-1]*10+rt[i-1];
rt[i]=rt[i-1]*10;
}
int l,r;
l=pw(10,kk-1);
r=pw(10,kk)-1;
pre(l-1,dp1);
pre(r,dp2);
cout<<dp2[6]-dp1[6];
return 0;
}
```
by MatrixCascade @ 2019-12-14 09:08:05
@[初音Yiku](/user/241817)
by MatrixCascade @ 2019-12-14 09:08:13
@[Illusory_](/user/154101) 不需要数位DP吧
by jacky567 @ 2019-12-14 09:11:47
@[初音Yiku](/user/241817) $f[n]=8\times f[n-1]+9\times 10^{n-1}$
by jacky567 @ 2019-12-14 09:13:01
@[Jacky0705](/user/43373) 你这个明显错的。
by MatrixCascade @ 2019-12-14 09:13:04