#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<int mod>
class Modular {
public:
int val;
Modular() : val(0) {}
Modular(int new_val) : val(new_val) {
}
friend Modular operator+(const Modular& a, const Modular& b) {
if (a.val + b.val >= mod) return a.val + b.val - mod;
else return a.val + b.val;
}
friend Modular operator-(const Modular& a, const Modular& b) {
if (a.val - b.val < 0) return a.val - b.val + mod;
else return a.val - b.val;
}
friend Modular operator*(const Modular& a, const Modular& b) {
return 1ll * a.val * b.val % mod;
}
friend Modular binpow(Modular a, long long n) {
Modular res = 1;
for (; n; n >>= 1) {
if (n & 1) res *= a;
a *= a;
}
return res;
}
/* ALTERNATIVE INVERSE FUNCTION USING EXTENDED EUCLIDEAN ALGORITHM
friend void gcd(int a, int b, Modular& x, Modular& y) {
if (a == 0) {
x = Modular(0);
y = Modular(1);
return;
}
Modular x1, y1;
gcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
}
friend Modular inv(const Modular& a) {
Modular x, y;
gcd(a.val, mod, x, y);
return x;
}
*/
friend Modular inv(const Modular& a) {
return binpow(a, mod - 2);
}
Modular operator/(const Modular& ot) const {
return *this * inv(ot);
}
Modular& operator++() {
if (val + 1 == mod) val = 0;
else ++val;
return *this;
}
Modular operator++(int) {
Modular tmp = *this;
++(*this);
return tmp;
}
Modular operator+() const {
return *this;
}
Modular operator-() const {
return 0 - *this;
}
Modular& operator+=(const Modular& ot) {
return *this = *this + ot;
}
Modular& operator-=(const Modular& ot) {
return *this = *this - ot;
}
Modular& operator*=(const Modular& ot) {
return *this = *this * ot;
}
Modular& operator/=(const Modular& ot) {
return *this = *this / ot;
}
bool operator==(const Modular& ot) const {
return val == ot.val;
}
bool operator!=(const Modular& ot) const {
return val != ot.val;
}
bool operator<(const Modular& ot) const {
return val < ot.val;
}
bool operator>(const Modular& ot) const {
return val > ot.val;
}
explicit operator int() const {
return val;
}
};
template <int mod>
Modular<mod> any_to_mint(ll a) {
a %= mod;
return a < 0 ? a + mod : a;
}
template<int mod>
istream& operator>>(istream& istr, Modular<mod>& x) {
return istr >> x.val;
}
template<int mod>
ostream& operator<<(ostream& ostr, const Modular<mod>& x) {
return ostr << x.val;
}
template <int mod = 998244353, int root = 3>
class NTT {
using Mint = Modular<mod>;
public:
static vector<int> mult(const vector<int>& a, const vector<int>& b) {
vector<Mint> amod(a.size());
vector<Mint> bmod(b.size());
for (int i = 0; i < a.size(); i++) {
amod[i] = any_to_mint<mod>(a[i]);
}
for (int i = 0; i < b.size(); i++) {
bmod[i] = any_to_mint<mod>(b[i]);
}
vector<Mint> resmod = mult(amod, bmod);
vector<int> res(resmod.size());
for (int i = 0; i < res.size(); i++) {
res[i] = resmod[i].val;
}
return res;
}
static vector<Mint> mult(const vector<Mint>& a, const vector<Mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
int lg = 0;
while ((1 << lg) < n + m - 1) lg++;
int z = 1 << lg;
auto a2 = a, b2 = b;
a2.resize(z);
b2.resize(z);
nft(false, a2);
nft(false, b2);
for (int i = 0; i < z; i++) a2[i] *= b2[i];
nft(true, a2);
a2.resize(n + m - 1);
Mint iz = inv(Mint(z));
for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
return a2;
}
private:
static void nft(bool type, vector<Modular<mod>> &a) {
int n = int(a.size()), s = 0;
while ((1 << s) < n) s++;
assert(1 << s == n);
static vector<Mint> ep, iep;
while (int(ep.size()) <= s) {
ep.push_back(binpow(Mint(root), (mod - 1) / (1 << ep.size())));
iep.push_back(inv(ep.back()));
}
vector<Mint> b(n);
for (int i = 1; i <= s; i++) {
int w = 1 << (s - i);
Mint base = type ? iep[i] : ep[i], now = 1;
for (int y = 0; y < n / 2; y += w) {
for (int x = 0; x < w; x++) {
auto l = a[y << 1 | x];
auto r = now * a[y << 1 | x | w];
b[y | x] = l + r;
b[y | x | n >> 1] = l - r;
}
now *= base;
}
swap(a, b);
}
}
};
const ll inf = 1e18;
const int C = 10;
const int N = 2e5 + 10;
const int M = 1e6 + 1e5 + 10;
int cnt_suf[C][M];
int flag[N];
ll dp[(1 << C)][(1 << C)];
int rig_true[C][N];
int b[N];
int lef[C][N], rig[C][N];
int pref[C][N], suf[C][N];
bool getbit(int mask, int bit) {
return mask & (1 << bit);
}
ll mask_to_ll(int mask) {
ll res = 0;
for (int i = 1; i < C; i++) {
if (getbit(mask, i)) {
res = res * 10 + i;
mask ^= (1 << i);
break;
}
}
for (int i = 0; i < C; i++) {
if (getbit(mask, i)) {
res = res * 10 + i;
}
}
return res;
}
int vec_to_mask(const vector<int>& vec) {
int mask = 0;
for (int i : vec) {
mask |= (1 << i);
}
return mask;
}
void init() {
{
for (int x = M - 1; x >= 1; x /= 10) {
cnt_suf[x % 10][M - 1]++;
}
}
for (int i = M - 2; i >= 1; i--) {
int mask = 0;
for (int x = i; x >= 1; x /= 10) {
mask |= (1 << (x % 10));
}
for (int c = 0; c < C; c++) {
if (getbit(mask, c)) {
cnt_suf[c][i] = cnt_suf[c][i + 1] + 1;
} else {
cnt_suf[c][i] = 0;
}
}
}
flag[0] = (1 << 0);
for (int i = 1; i <= N - 1; i++) {
for (int j = i; j >= 1; j /= 10) {
flag[i] |= (1 << (j % 10));
}
}
for (int i = 0; i < (1 << C); i++) {
for (int j = 0; j < (1 << C); j++) {
dp[i][j] = inf;
}
}
for (int mask = 0; mask < (1 << C); mask++) {
for (int last = 0; last < C && last != 9; last++) {
int pref_mask = mask | (1 << last);
int suf_mask = mask | (1 << (last + 1));
if (mask_to_ll(mask) != 0 || last != 0) {
dp[pref_mask][suf_mask] = min(dp[pref_mask][suf_mask], mask_to_ll(mask == 1 ? 3 : mask) * 10 + last);
}
pref_mask = mask | (mask == 0 && last == 0 ? 0 : (1 << last)) | (1 << 9);
suf_mask = mask | (1 << (last + 1)) | (1 << 0);
dp[pref_mask][suf_mask] = min(dp[pref_mask][suf_mask], mask_to_ll(mask == 1 ? 3 : mask) * 100 + last * 10 + 9);
}
}
for (int i = (1 << C) - 1; i >= 0; i--) {
for (int j = (1 << C) - 1; j >= 0; j--) {
for (int c = 0; c < C; c++) {
dp[i][j] = min(dp[i][j], dp[i | (1 << c)][j]);
dp[i][j] = min(dp[i][j], dp[i][j | (1 << c)]);
}
}
}
}
void calc_lef_rig(int k) {
const int n = 200'000;
for (int c = 0; c < C; c++) {
vector<int> p(n, 0);
vector<int> q(k, 0);
for (int i = 0; i < n; i++) {
p[i] = getbit(flag[i], c);
}
for (int i = 1; i <= k; i++) {
q[k - i] = b[i] == c;
}
auto r = NTT<998244353, 3>::mult(p, q);
for (int i = 0; i < n; i++) {
lef[c][i] = r[i];
rig[c][i] = rig_true[c][i] = r[i + k - 1];
}
}
{
vector<int> p(n, 0);
vector<int> q(k, 0);
for (int i = 0; i < n; i++) {
int new_flag = flag[i];
if (i < 9'999) {
flag[i] |= (1 << 0);
}
p[i] = getbit(new_flag, 0);
}
for (int i = 1; i <= k; i++) {
q[k - i] = b[i] == 0;
}
auto r = NTT<998244353, 3>::mult(p, q);
for (int i = 0; i < n; i++) {
lef[0][i] = r[i];
rig[0][i] = r[i + k - 1];
}
}
}
void calc_pref_suf(int k) {
for (int c = 0; c < C; c++) {
pref[c][0] = 0;
suf[c][k + 1] = 0;
}
for (int i = 1; i <= k; i++) {
for (int c = 0; c < C; c++) {
pref[c][i] = pref[c][i - 1];
}
pref[b[i]][i]++;
}
for (int i = k; i >= 1; i--) {
for (int c = 0; c < C; c++) {
suf[c][i] = suf[c][i + 1];
}
suf[b[i]][i]++;
}
}
ll solve_small(int k) {
const int n = 100'000;
for (int i = 1; i < n; i++) {
bool ok = true;
for (int c = 0; c < C; c++) {
ok &= rig_true[c][i] == pref[c][k];
}
if (ok) {
return i;
}
}
return inf;
}
ll solve(int k) {
calc_lef_rig(k);
calc_pref_suf(k);
const int n = 100'000;
ll ans = inf;
ans = min(ans, solve_small(k));
for (int i = 0; i < n; i++) {
if (i + k - 1 < n) {
int need = 0;
for (int c = 0; c < C; c++) {
if (rig[c][i] != pref[c][k]) {
need |= (1 << c);
}
}
ans = min(ans, dp[need][0] * n + i);
} else {
int len_pref = n - i;
int len_suf = k - len_pref;
int need_pref = 0, need_suf = 0;
for (int c = 0; c < C; c++) {
if (rig[c][i] != pref[c][len_pref]) {
need_pref |= (1 << c);
}
if (lef[c][len_suf - 1] != suf[c][k - len_suf + 1]) {
need_suf |= (1 << c);
}
}
ans = min(ans, dp[need_pref][need_suf] * n + i);
}
}
return ans;
}
ll solve_same(int k) {
for (int i = 1; i <= k - 1; i++) {
if (b[i] != b[i + 1]) {
return inf;
}
}
for (int n = 1; n + k - 1 <= M - 1; n++) {
if (cnt_suf[b[1]][n] >= k) {
return n;
}
}
return -1;
}
ll slow(int k) {
for (int n = 1; n <= 1000; n++) {
bool ok = true;
for (int i = 1; i <= k; i++) {
ok &= getbit(flag[n + i - 1], b[i]);
}
if (ok) {
return n;
}
}
return -1;
}
void stress() {
mt19937 rnd;
while (true) {
int k = rnd() % 100 + 1;
for (int i = 1; i <= k; i++) {
b[i] = rnd() % C;
}
ll res = slow(k);
if (res == -1) {
continue;
}
ll ans = solve(k);
if (ans == res) {
cout << "OK" << endl;
} else {
cout << "WA\n";
cout << k << "\n";
for (int i = 1; i <= k; i++) {
cout << b[i] << " ";
}
cout << "\n\n";
cout << ans << " " << res << "\n";
break;
}
}
exit(0);
}
void gen_same(int& k, int trg_k, int trg_b) {
k = trg_k;
for (int i = 1; i <= k; i++) {
b[i] = trg_b;
}
}
void stress_same() {
mt19937 rnd;
while (true) {
int k = rnd() % 1000 + 99000;
b[1] = rnd() % C;
for (int i = 2; i <= k; i++) {
b[i] = b[i - 1];
}
ll ans = solve(k);
ll res = solve_same(k);
if (ans == res) {
cout << "OK" << endl;
} else {
cout << "WA\n";
cout << k << "\n";
cout << "b[i] = " << b[1] << "\n";
cout << "\n\n";
cout << ans << " " << res << "\n";
break;
}
}
exit(0);
}
ll dp_slow[(1 << C)][(1 << C)];
int ll_to_mask(ll x) {
int mask = 0;
while (x > 0) {
mask |= (1 << (x % 10));
x /= 10;
}
return mask;
}
void stress_dp() {
for (int i = 0; i < (1 << C); i++) {
for (int j = 0; j < (1 << C); j++) {
dp_slow[i][j] = inf;
}
}
for (int i = 1; i <= 1e7; i++) {
int x = ll_to_mask(i);
int y = ll_to_mask(i + 1);
dp_slow[x][y] = min(dp_slow[x][y], ll(i));
}
for (int i = 0; i < (1 << C); i++) {
for (int j = 0; j < (1 << C); j++) {
if (dp_slow[i][j] != inf && dp[i][j] != dp_slow[i][j]) {
cout << "WA\n";
cout << i << " " << j << "\n";
cout << dp[i][j] << " " << dp_slow[i][j] << "\n";
exit(0);
}
}
}
cout << "OK" << endl;
exit(0);
}
bool check(int k, ll ans) {
for (int i = 1; i <= k; i++) {
if (!getbit(ll_to_mask(ans + i - 1), b[i])) {
return false;
}
}
return true;
}
void stress_check_big() {
mt19937 rnd;
while (true) {
int k = rnd() % 1000 + 90000;
for (int i = 1; i <= k; i++) {
b[i] = rnd() % C;
}
ll ans = solve(k);
if (check(k, ans)) {
cout << "OK " << k << " " << ans << endl;
} else {
cout << "WA\n";
cout << k << "\n";
cout << "b ?\n\n";
cout << ans << "\n";
break;
}
}
exit(0);
}
void stress_big() {
mt19937 rnd;
while (true) {
int k = rnd() % 100 + 90000;
ll res = rnd() % 123123123 + 1;
for (int i = 1; i <= k; i++) {
int mask = ll_to_mask(res + i - 1);
vector<int> vec;
for (int c = 0; c < C; c++) {
if (getbit(mask, c)) {
vec.push_back(c);
}
}
b[i] = vec[rnd() % vec.size()];
}
ll ans = solve(k);
bool ok = check(k, ans);
if (ok && ans <= res) {
cout << "OK " << k << " " << ans << " " << res << endl;
} else {
cout << "WA\n";
cout << k << "\n";
cout << "b ?\n\n";
cout << ans << " " << res << "\n";
cout << (ok ? "good" : "bad") << "\n";
break;
}
}
exit(0);
}
void gen_big(int& k, int trg_k, ll trg_ans) {
k = trg_k;
mt19937 rnd;
for (int i = 1; i <= k; i++) {
int mask = ll_to_mask(trg_ans + i - 1);
vector<int> vec;
for (int c = 0; c < C; c++) {
if (getbit(mask, c)) {
vec.push_back(c);
}
}
b[i] = vec[rnd() % vec.size()];
bool ok = false;
for (char ch : to_string(trg_ans + i - 1)) {
if ((ch - '0') == b[i]) {
ok = true;
}
}
assert(ok);
}
assert(check(k, trg_ans));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
init();
// stress();
// stress_same();
// stress_dp();
// stress_check_big();
// stress_big();
int k;
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> b[i];
}
// gen_same(k, 90239, 0);
// int trg_k = 90012;
// ll trg_ans = 89376811;
// gen_big(k, trg_k, trg_ans);
cout << solve(k) << "\n";
// cout << solve_same(k) << "\n";
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Compilation message
sequence.cpp: In instantiation of 'static std::vector<int> NTT<mod, root>::mult(const std::vector<int>&, const std::vector<int>&) [with int mod = 998244353; int root = 3]':
sequence.cpp:296:46: required from here
sequence.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
sequence.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for (int i = 0; i < b.size(); i++) {
| ~~^~~~~~~~~~
sequence.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int i = 0; i < res.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
393 ms |
95096 KB |
Output is correct |
| 2 |
Correct |
390 ms |
96936 KB |
Output is correct |
| 3 |
Correct |
389 ms |
95144 KB |
Output is correct |
| 4 |
Correct |
395 ms |
95036 KB |
Output is correct |
| 5 |
Correct |
389 ms |
95012 KB |
Output is correct |
| 6 |
Correct |
398 ms |
95044 KB |
Output is correct |
| 7 |
Correct |
390 ms |
95028 KB |
Output is correct |
| 8 |
Correct |
390 ms |
96768 KB |
Output is correct |
| 9 |
Correct |
386 ms |
96940 KB |
Output is correct |
| 10 |
Correct |
394 ms |
96620 KB |
Output is correct |
| 11 |
Correct |
385 ms |
96744 KB |
Output is correct |
| 12 |
Correct |
393 ms |
95100 KB |
Output is correct |
| 13 |
Correct |
394 ms |
95012 KB |
Output is correct |
| 14 |
Correct |
390 ms |
96936 KB |
Output is correct |
| 15 |
Correct |
392 ms |
96692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
396 ms |
95200 KB |
Output is correct |
| 2 |
Correct |
388 ms |
96540 KB |
Output is correct |
| 3 |
Correct |
395 ms |
95164 KB |
Output is correct |
| 4 |
Correct |
395 ms |
95136 KB |
Output is correct |
| 5 |
Correct |
394 ms |
95008 KB |
Output is correct |
| 6 |
Correct |
390 ms |
95196 KB |
Output is correct |
| 7 |
Correct |
390 ms |
96848 KB |
Output is correct |
| 8 |
Correct |
389 ms |
95096 KB |
Output is correct |
| 9 |
Correct |
386 ms |
96656 KB |
Output is correct |
| 10 |
Correct |
388 ms |
96608 KB |
Output is correct |
| 11 |
Correct |
385 ms |
96600 KB |
Output is correct |
| 12 |
Correct |
385 ms |
96564 KB |
Output is correct |
| 13 |
Correct |
388 ms |
96592 KB |
Output is correct |
| 14 |
Correct |
387 ms |
95108 KB |
Output is correct |
| 15 |
Correct |
387 ms |
95092 KB |
Output is correct |
| 16 |
Correct |
403 ms |
96696 KB |
Output is correct |
| 17 |
Correct |
389 ms |
96688 KB |
Output is correct |
| 18 |
Correct |
396 ms |
95368 KB |
Output is correct |
| 19 |
Correct |
389 ms |
96656 KB |
Output is correct |
| 20 |
Correct |
390 ms |
96784 KB |
Output is correct |
| 21 |
Correct |
385 ms |
96624 KB |
Output is correct |
| 22 |
Correct |
389 ms |
96700 KB |
Output is correct |
| 23 |
Correct |
385 ms |
96656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
389 ms |
96624 KB |
Output is correct |
| 2 |
Correct |
387 ms |
96848 KB |
Output is correct |
| 3 |
Correct |
393 ms |
96820 KB |
Output is correct |
| 4 |
Incorrect |
391 ms |
96908 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
389 ms |
95180 KB |
Output is correct |
| 2 |
Correct |
386 ms |
96564 KB |
Output is correct |
| 3 |
Correct |
390 ms |
95008 KB |
Output is correct |
| 4 |
Correct |
388 ms |
95040 KB |
Output is correct |
| 5 |
Correct |
392 ms |
97380 KB |
Output is correct |
| 6 |
Correct |
387 ms |
95136 KB |
Output is correct |
| 7 |
Correct |
393 ms |
95016 KB |
Output is correct |
| 8 |
Correct |
388 ms |
96652 KB |
Output is correct |
| 9 |
Correct |
389 ms |
95136 KB |
Output is correct |
| 10 |
Correct |
388 ms |
96892 KB |
Output is correct |
| 11 |
Incorrect |
724 ms |
98144 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
