[CF1601F]Two Sorts
link:https://codeforces.com/problemset/problem/1601/F
Description
有一个数列 \(\{a_1, a_2, \ldots, a_n\}\) 是一个 \(1 \sim n\) 的排列，且所有的数都按照字典序排序，现在给出整数 \(n(1 \leq n \leq 10^{12})\) ，求 \(\left(\sum_{i=1}^n((i-a_i) \bmod 998244353)\right) \bmod 10^9+7\) ，注意这里 \(x \bmod y\) 的结果为正数。
Solution
好题！
我会暴力！爆搜合法字典序最小状态，复杂度 \(\mathcal O(n)\) 。
\(10^{12}\) 的范围，但看上去不像是能 \(\log\) 时间解决，于是考虑 meet in the middle。
不难发现字典序相近的数前缀相同，于是暴力预处理出后面 \(6\) 位的数，然后爆搜前面 \(6\) 位即可。
Code
点击查看代码
#include<bits/stdc++.h>
#define LL long long
#define vi vector<int>
#define eb emplace_back
using namespace std;
const int MOD1 = 998244353, MOD2 = 1e9+7, HAL = 1000000;
vi num[7];
LL cnt1, cnt2, sum[7], n, ans, po10[10] = {1, 10, 100, 1000, 10000, 100000, 1000000};
void dfs1(int len, int x) {
if (len == 7) return ;
num[len].eb((cnt1-x+MOD1)%MOD1);
sum[len] += (cnt1-x+MOD1)%MOD1;
++cnt1;
for (int i = 0; i <= 9; ++i)
dfs1(len+1, x*10+i);
}
bool check(int x) {
return 1ll*x*HAL+HAL-1 <= n && 1ll*x*HAL*10 > n;
}
void dfs2(int len, LL x) {
if (x > n) return ;
if (check(x)) {
for (int i = 0; i <= 6; ++i) {
LL del = ((cnt2+1-x*po10[i])%MOD1+MOD1)%MOD1;
LL pos = lower_bound(num[i].begin(), num[i].end(), MOD1-del)-num[i].begin();
(ans += (sum[i]+del*num[i].size()-MOD1*(num[i].size()-pos))) %= MOD2;
}
cnt2 += cnt1;
} else {
++cnt2;
(ans += ((cnt2-x)%MOD1+MOD1)%MOD1) %= MOD2;
for (int i = (!len); i <= 9; ++i)
dfs2(len+1, x*10+i);
}
}
int main() {
scanf("%lld", &n);
dfs1(0, 0);
for (int i = 0; i <= 6; ++i) sort(num[i].begin(), num[i].end());
cnt2 = -1;
dfs2(0, 0);
printf("%lld\n", ans);
return 0;
}
Summary
meet in the middle 真滴强！
标签：10,MOD1,int,sum,Two,len,cnt1,CF1601F,Sorts From： https://www.cnblogs.com/BlackCrow/p/17796653.html