meet in the middle 做法没看懂。
但我觉得 A_zjzj 老师的做法很牛！
题目链接。
题意
给定 ，令 表示 中所有数字里面，字典序第 小的数字。
求 。
。
题解
令 表示数字 是字典序第几大的（也就是说 是 的逆）。
令 。
那么要求的相当于 。
首先能看出来 。
那么也就是说只需要求出来
就好了。
同时也可以发现，。
考虑枚举 ，并计算这样的
的数量。可以发现不太好算。
然后能发现一个性质，假如 和
两个数字位数相同，那么应该有
。
这说明 。
也就是说，所有位数相同的数字里面，
这玩意是单调的，那么这就可以二分了。
那么就可以，不同位数的分开考虑。
对于同一位的所有数字，
是单调的，那么就可以用二分找出所有不同
的分界线。
这里还需要在
复杂度内求出
的值，但是这是容易的。
位数一个 ，二分一个 ，求 还需要一个 。
所以最后复杂度是 的。
代码
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
78
79
80
81
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int p=998244353;
const int mod=1000000007;
ll P[20];
ll n;
inline ll rk(ll m,int w)
{
ll ans=0,mem=m*10;
for(int i=1;i<=w;i++)
{
ans+=m-P[w-i]+1;
m/=10;
}
while(P[w]<=n)
{
ans+=min(mem,n+1)-P[w];
w++,mem*=10;
}
return ans;
}
inline ll floor(ll a,ll b)
{
if(a>=0) return a/b;
return -((-a+b-1)/b);
}
inline ll get(int w)
{
ll ans=0;
ll L=P[w-1],R=min(P[w]-1,n);
while(true)
{
ll val=floor(rk(L,w)-L,p),l=L,r=R;
while(l<r)
{
ll mid=(l+r+1)>>1;
if(floor(rk(mid,w)-mid,p)==val) l=mid;
else r=mid-1;
}
ans+=(l-L+1)%mod*val;
if(l==R) break;
L=l+1;
}
return ans%mod;
}
int main()
{
n=lread(),P[0]=1;
for(int i=1;i<=18;i++) P[i]=P[i-1]*10;
ll ans=0;
for(int i=1;n>=P[i-1];i++) ans+=get(i);
ans=-ans%mod*p%mod;
ans=(ans%mod+mod)%mod;
printf("%lld\n",ans);
return 0;
}
|