首先注意到一个数如果位数能更小，取更小总是更优的。
那么具体能多小呢？
首先，显然如果 的位数 的位数，则有 。设 为 的位数，则显然有 。
紧接着，考虑到如果位数是相同的，则 的大小关系和它们的字典序大小关系一致。于是如果有 ，则有 。
求出 后，直接按找字典序贪心地取最小字典序即可。正确性显然：
- 依据 的构造，可以保证 ；
- 由于单个数时 相同，故字典序最小时就是最小的。
那么如何取最小字典序？这一个数的 比前面的大，那么直接补 即可；否则，需要在最后一位上 。前面的位都不用变。
可以直接单调栈维护，时间复杂度 。
（代码来自 xhabc66）
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > li;
long long mi[114514],ni[114514];
const int MOD=1000000007;
int p[114514],q[114514],a[114514],b[114514];
int main(){freopen("seminar.in","r",stdin);freopen("seminar.out","w",stdout);
mi[0]=1;for(int i=1;i<114514;i++)mi[i]=mi[i-1]*10%MOD;
ni[0]=1;for(int i=1;i<114514;i++)ni[i]=ni[i-1]*700000005%MOD;
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>q[i],p[q[i]]=i;
a[1]=1;
for(int i=2;i<=n;i++)
if(p[i]<p[i-1])a[i]=a[i-1]+1;
else a[i]=a[i-1];
for(int i=1;i<=n;i++)b[p[i]]=a[i];
long long nowans=0,ans=0;int sz=-1;
for(int i=1;i<=n;i++){
while(sz>=0&&li[sz].first>b[i])nowans-=li[sz].second*mi[b[i-1]-li[sz].first],li.pop_back(),sz--;
if(b[i]>b[i-1])nowans*=mi[b[i]-b[i-1]];else nowans*=ni[b[i-1]-b[i]];
nowans%=MOD;
if(sz==-1)li.push_back(make_pair(1,1)),nowans+=mi[b[i]-1],sz++;
else if(b[i-1]<b[i]);
else if(li[sz].first==b[i]){
auto t=li[sz];li.pop_back();li.push_back(make_pair(t.first,t.second+1));
nowans+=mi[b[i]-t.first];
}else{
li.push_back(make_pair(b[i],1));sz++;nowans++;
}
nowans%=MOD;
ans+=nowans;
ans%=MOD;
}
cout<<(ans+MOD)%MOD<<endl;
}
暂无评论