#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 L = 18;
const int C = 10;
const int N = 2e5 + 10;
const int M = 1e6 + 1e5 + 10;
int cnt_suf[C][M];
ll pw10[L];
int flag[N];
ll dp[(1 << C)][(1 << C)];
int flag_true[N];
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;
}
}
}
pw10[0] = 1;
for (int i = 1; i < L; i++) {
pw10[i] = pw10[i - 1] * 10;
}
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));
}
flag_true[i] = flag[i];
if (i <= 99'999) {
flag[i] |= (1 << 0); ///////////////////////////////////////////////////////////////////////////////////////
}
}
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++) {
if (mask == 0 && last == 0) {
continue;
}
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 | (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 = 100'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] = 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]++;
}
}
void calc_rig_true(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_true[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++) {
rig_true[c][i] = r[i + k - 1];
}
}
}
ll solve_small(int k) {
calc_rig_true(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);
}
}
if (dp[need][0] != inf) {
ans = min(ans, dp[need][0] * n + i);
}
// if (need == 0) {
// if (i == 0) {
// ans = min(ans, pw10[to_string(i + k - 1).size()]);
// } else {
// ans = min(ans, ll(i));
// }
// } else {
// if (need == 1) {
// need = 3;
// }
// ll x = mask_to_ll(need);
// ans = min(ans, x * pw10[to_string(i + k - 1).size()] + 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][len_suf]) {
need_suf |= (1 << c);
}
}
if (dp[need_pref][need_suf] != inf) {
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() % 10 + 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 + 10000;
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);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
init();
// stress();
// stress_same();
// cout << dp[vec_to_mask({1, 2, 3})][vec_to_mask({9, 0, 1, 4})] << "\n";
int k;
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> b[i];
}
// gen_same(k, 10009, 9);
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:311: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 |
497 ms |
98404 KB |
Output is correct |
| 2 |
Correct |
488 ms |
98456 KB |
Output is correct |
| 3 |
Correct |
500 ms |
98420 KB |
Output is correct |
| 4 |
Correct |
495 ms |
98416 KB |
Output is correct |
| 5 |
Correct |
493 ms |
98400 KB |
Output is correct |
| 6 |
Correct |
515 ms |
98420 KB |
Output is correct |
| 7 |
Correct |
495 ms |
98396 KB |
Output is correct |
| 8 |
Correct |
493 ms |
98424 KB |
Output is correct |
| 9 |
Correct |
497 ms |
98448 KB |
Output is correct |
| 10 |
Correct |
490 ms |
98416 KB |
Output is correct |
| 11 |
Correct |
495 ms |
98944 KB |
Output is correct |
| 12 |
Correct |
494 ms |
98404 KB |
Output is correct |
| 13 |
Correct |
502 ms |
98440 KB |
Output is correct |
| 14 |
Correct |
500 ms |
98368 KB |
Output is correct |
| 15 |
Correct |
487 ms |
98452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
492 ms |
98440 KB |
Output is correct |
| 2 |
Correct |
493 ms |
98652 KB |
Output is correct |
| 3 |
Correct |
495 ms |
98404 KB |
Output is correct |
| 4 |
Correct |
498 ms |
98432 KB |
Output is correct |
| 5 |
Correct |
496 ms |
98448 KB |
Output is correct |
| 6 |
Correct |
494 ms |
98452 KB |
Output is correct |
| 7 |
Correct |
492 ms |
98752 KB |
Output is correct |
| 8 |
Correct |
490 ms |
98416 KB |
Output is correct |
| 9 |
Correct |
489 ms |
98424 KB |
Output is correct |
| 10 |
Correct |
498 ms |
98492 KB |
Output is correct |
| 11 |
Incorrect |
487 ms |
98468 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
491 ms |
98388 KB |
Output is correct |
| 2 |
Correct |
497 ms |
98656 KB |
Output is correct |
| 3 |
Correct |
492 ms |
98648 KB |
Output is correct |
| 4 |
Correct |
498 ms |
98544 KB |
Output is correct |
| 5 |
Incorrect |
489 ms |
98628 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
499 ms |
98440 KB |
Output is correct |
| 2 |
Correct |
495 ms |
98712 KB |
Output is correct |
| 3 |
Correct |
493 ms |
98384 KB |
Output is correct |
| 4 |
Correct |
497 ms |
98496 KB |
Output is correct |
| 5 |
Incorrect |
644 ms |
99140 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
