https://scg3.piaoztsdy.cn/p/273
进制数 实在是太大了，因此位数多了就一定不是最优的，考虑确定每个数的位数：
- 的位数不少于 。
- 若 且 ，则 的位数一定严格多于 。
由以上两条结论可以计算每个数的最少位数，并且可以证明最优解一定都取这样算出来的位数：假设 是第一个不取算出来的位数的数字，由于 的位数与 的位数的差值的最小值也是确定的（若排列 中 排在 前面则为 ，否则为 ），而原方案全部取到了最小差值，因此最后 的位数一定大于原方案的位数，因此不是最优的。
接下来为每个数的每一位填写数字：设当前正在填写字典序排序的序列中 位置内第 高位及以后的值，则其中的 位数至少依次填写为 （如果 不是 位数，起点要加上 ；如果 ，起点也要加上 ；如果都有，起点要加上 ），且 的这一位必须单调不降。填完之后，只需要对其中每个第 位相同的区间递归处理子区间即可。
在递归过程中对不存在 位数的 直接跳过，最终的时间复杂度为 ，空间复杂度为 （如果使用线段树实现 RMQ），瓶颈在跳过不合法 使用的 RMQ。
（实际上，我们也可以套用 RMQ 把时间复杂度降到 ，但是意义不大。）
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 12, M = 17, B = 10, P = 1e9 + 7;
int p[N], q[N], d[N], b[N], w[N];
long long s[N][M];
pair <int, int> dfs(int l, int r, int n, int c, int e)
{
if (l > r) return make_pair(0, 0);
if (l == r) return make_pair((int) (1ll * e * b[d[p[l]] - c] % P), b[d[p[l]] - c]);
long long u = 0, v = 0;
int z = w[r - l + 1], t = min(s[l][z], s[r - (1 << z) + 1][z]) / n;
if (d[p[l]] == t)
{
u = e;
v = b[t - c];
l++;
}
while (l <= r)
{
int z = w[r - l + 1];
long long y = min(s[l][z], s[r - (1 << z) + 1][z]);
if (y / n != t) break;
pair <int, int> x = dfs(l, y % n, n, t + 1, 0);
u = (u + x.first + 1ll * e * (1ll * B * x.second % P + 1) + 1) % P;
v = (v + 1ll * b[t - c] * (1ll * B * x.second % P + 1)) % P;
l = y % n + 2;
e++;
}
pair <int, int> x = dfs(l, r, n, t + 1, 0);
u = (u + x.first + 1ll * e * B % P * x.second % P) % P;
v = (v + 1ll * b[t - c] * B % P * x.second % P) % P;
return make_pair(u, v);
}
int main()
{
freopen("seminar.in", "r", stdin);
freopen("seminar.out", "w", stdout);
int n;
cin >> n;
for (int i = 0, j = 1; j <= n; i++, j <<= 1)
w[j] = i;
for (int i = 3; i <= n; i++)
if (!w[i]) w[i] = w[i - 1];
b[0] = 1;
for (int i = 1; i <= n; i++)
b[i] = 1ll * b[i - 1] * B % P;
for (int i = 1; i <= n; i++)
cin >> p[i];
for (int i = 1; i <= n; i++)
q[p[i]] = i;
d[1] = 1;
for (int i = 2; i <= n; i++)
{
d[i] = d[i - 1];
if (q[i] < q[i - 1]) d[i]++;
}
for (int i = 1; i <= n; i++)
s[i][0] = 1ll * d[p[i]] * n + i - 1;
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
s[i][j] = min(s[i][j - 1], s[i + (1 << (j - 1))][j - 1]);
cout << dfs(1, n, n, 1, 1).first << endl;
return 0;
}
暂无评论