#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) {
new_flag |= (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;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
init();
int k;
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> b[i];
}
cout << solve(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 |
394 ms |
93052 KB |
Output is correct |
| 2 |
Correct |
383 ms |
94688 KB |
Output is correct |
| 3 |
Correct |
390 ms |
93084 KB |
Output is correct |
| 4 |
Correct |
385 ms |
93020 KB |
Output is correct |
| 5 |
Correct |
385 ms |
92980 KB |
Output is correct |
| 6 |
Correct |
387 ms |
92968 KB |
Output is correct |
| 7 |
Correct |
386 ms |
93036 KB |
Output is correct |
| 8 |
Correct |
388 ms |
94616 KB |
Output is correct |
| 9 |
Correct |
382 ms |
94512 KB |
Output is correct |
| 10 |
Correct |
384 ms |
94640 KB |
Output is correct |
| 11 |
Correct |
383 ms |
94604 KB |
Output is correct |
| 12 |
Correct |
393 ms |
93132 KB |
Output is correct |
| 13 |
Correct |
387 ms |
92976 KB |
Output is correct |
| 14 |
Correct |
389 ms |
94868 KB |
Output is correct |
| 15 |
Correct |
386 ms |
94608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
395 ms |
93260 KB |
Output is correct |
| 2 |
Correct |
386 ms |
94648 KB |
Output is correct |
| 3 |
Correct |
393 ms |
93256 KB |
Output is correct |
| 4 |
Correct |
388 ms |
93068 KB |
Output is correct |
| 5 |
Correct |
391 ms |
92948 KB |
Output is correct |
| 6 |
Correct |
389 ms |
93092 KB |
Output is correct |
| 7 |
Correct |
389 ms |
94700 KB |
Output is correct |
| 8 |
Correct |
394 ms |
93124 KB |
Output is correct |
| 9 |
Correct |
391 ms |
94592 KB |
Output is correct |
| 10 |
Correct |
383 ms |
94604 KB |
Output is correct |
| 11 |
Correct |
390 ms |
94732 KB |
Output is correct |
| 12 |
Correct |
382 ms |
94664 KB |
Output is correct |
| 13 |
Correct |
392 ms |
94496 KB |
Output is correct |
| 14 |
Correct |
391 ms |
93084 KB |
Output is correct |
| 15 |
Correct |
387 ms |
93012 KB |
Output is correct |
| 16 |
Correct |
391 ms |
94532 KB |
Output is correct |
| 17 |
Correct |
392 ms |
94616 KB |
Output is correct |
| 18 |
Correct |
390 ms |
93280 KB |
Output is correct |
| 19 |
Correct |
384 ms |
94608 KB |
Output is correct |
| 20 |
Correct |
384 ms |
94532 KB |
Output is correct |
| 21 |
Correct |
384 ms |
94544 KB |
Output is correct |
| 22 |
Correct |
388 ms |
94612 KB |
Output is correct |
| 23 |
Correct |
384 ms |
94640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
390 ms |
94800 KB |
Output is correct |
| 2 |
Correct |
385 ms |
94820 KB |
Output is correct |
| 3 |
Correct |
392 ms |
94848 KB |
Output is correct |
| 4 |
Incorrect |
385 ms |
94844 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
392 ms |
93220 KB |
Output is correct |
| 2 |
Correct |
385 ms |
94608 KB |
Output is correct |
| 3 |
Correct |
393 ms |
93084 KB |
Output is correct |
| 4 |
Correct |
387 ms |
93088 KB |
Output is correct |
| 5 |
Correct |
395 ms |
95372 KB |
Output is correct |
| 6 |
Correct |
388 ms |
93084 KB |
Output is correct |
| 7 |
Correct |
395 ms |
93124 KB |
Output is correct |
| 8 |
Correct |
384 ms |
94652 KB |
Output is correct |
| 9 |
Correct |
388 ms |
93124 KB |
Output is correct |
| 10 |
Correct |
386 ms |
94608 KB |
Output is correct |
| 11 |
Incorrect |
727 ms |
96104 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
