A. [ARC210D] Jeu d'ensemble indépendant (5)
À chaque tour, un sommet u est supprimé, et A supprime également le voisinage de u. Si n est impair, A ne peut pas supprimer le voisinage, sinon l'ensemble de sommets devient vide. En explorant manuellement, on constate que dans ce cas, chaque composante connexe doit avoir ≤ 2 sommets. Si n est pair, A peut supprimer au plus un sommet supplémentaire. Les deux joueurs suppriment d'abord les sommets isolés. Si leur nombre est pair, A supprime ensuite un sommet de degré 1 et son voisin, laissant un graphe où A peut gagner, ce qui exige que chaque composante restante ait ≤ 2 sommets. Par analyse, le sommet supplémentaire supprimé par A au premier tour est celui avec le degré maximal. Si le nombre de sommets isolés est impair, B supprime d'abord un sommet pour empêcher A de gagner. On extrait les composantes de taille >2, et si A ne peut pas gagner dans le graphe original, une exploration manuelle montre qu'A ne peut pas gagner avec de telles composantes, qui peuvent être traitées par force brute. Complexité temporelle : O(n + m).
// Code C++ pour le jeu d'ensemble indépendant
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
basic_string <int> G[MAXN], Q, C;
bool vis[MAXN];
int d[MAXN];
void dfs(int u) {
vis[u] = 1;
Q += u;
for (int v : G[u]) if (!vis[v]) dfs(v);
}
bool chk(int b) {
int x = 0, o = 1;
for (int t : C) if (d[t] > d[x]) x = t;
for (int y : G[x]) if (y != b) --d[x], --d[y];
for (int t : C) o &= d[t] <= 1;
for (int y : G[x]) if (y != b) ++d[x], ++d[y];
return o;
}
void solve() {
int n, m, c1 = 0;
cin >> n >> m;
C.clear();
for (int i = 1; i <= n; ++i) d[i] = vis[i] = 0, G[i].clear();
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
G[u] += v; G[v] += u;
++d[u]; ++d[v];
}
for (int i = 1; i <= n; ++i) if (!vis[i]) {
Q.clear();
dfs(i);
if (Q.size() <= 2) c1 += Q.size() == 1;
else C += Q;
}
if (n & 1) {
cout << (C.empty() ? "Alice\n" : "Bob\n");
return;
}
if (chk(0)) { cout << "Alice\n"; return; }
if (c1 % 2 == 0 || C.size() > 10) { cout << "Bob\n"; return; }
for (int x : C) {
for (int y : G[x]) --d[x], --d[y];
if (!chk(x)) { cout << "Bob\n"; return; }
for (int y : G[x]) ++d[x], ++d[y];
}
cout << "Alice\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
B. [ARC203E] Grille de carreaux avec un trou (4)
Considérons le nombre de points par ligne a_i. Les opérations consistent à soustraire 1 d'un intervalle de longueur L ou à soustraire L d'un point unique. Considérons la différence d_i = a_i - a_{i-1}. Aucune opération ne change la somme des d_i pour les indices congrus modulo L. Par discussion, les cas légitimes sont : h, w, r, c ≡ 1 (mod L) ou h, w ≡ -1 (mod L) et r, c ≡ 0 (mod L). Pour le premier cas, on remplit la ligne r horizontalement et la colonne c verticalement, le reste étant des rectangles L×L remplis uniformément. Pour le second cas, on remplit des bandes horizontalement et verticalement, avec des rectangles L×L restants. Complexité temporelle : O(n + m).
// Code C++ pour la grille avec un trou
#include <bits/stdc++.h>
using namespace std;
void solve() {
int h, w, d, n, m, r, c;
cin >> h >> w >> d >> n >> m >> r >> c;
auto e = [&](int x, int y) { return x >= y && x % d == y % d; };
auto O = [&](int i, int j) {
if (n >= d) {
n -= d;
for (int x = 0; x < d; ++x) cout << i + x << " " << j << "\n";
} else {
for (int x = 0; x < d; ++x) cout << i << " " << j + x << "\n";
}
};
if (e(h, 1) && e(w, 1) && e(r, 1) && e(c, 1) && e(n, w / d) && e(m, h / d)) {
cout << "Yes\n"; n -= w / d;
vector<int> X, Y;
for (int k = 0; k < h / d; ++k) X.push_back(k * d + 1 + (k >= r / d));
for (int k = 0; k < w / d; ++k) Y.push_back(k * d + 1 + (k >= c / d));
for (int j : Y) cout << r << " " << j << "\n";
for (int i : X) for (int j : Y) O(i, j);
for (int i : X) cout << i << " " << c << "\n";
} else if (e(h, d - 1) && e(w, d - 1) && e(r, 0) && e(c, 0) && e(n, (w + 1) / d * (d - 1)) && e(m, (h + 1) / d * (d - 1))) {
cout << "Yes\n"; n -= (w + 1) / d * (d - 1);
vector <int> LX, RX, LY, RY;
for (int i = 1; i < r; i += d) LX.push_back(i);
for (int i = r; i < h; i += d) RX.push_back(i);
for (int i = 1; i < c; i += d) LY.push_back(i);
for (int i = c; i < w; i += d) RY.push_back(i);
for (int j : LY) for (int i = 1; i < d; ++i) cout << r + i << " " << j << "\n";
for (int j : RY) for (int i = 1; i < d; ++i) cout << r - i << " " << j << "\n";
for (int i : LX) for (int j : LY) if (j != LY.back()) O(i, j);
for (int i : LX) for (int j : RY) if (i != LX.back()) O(i, j);
for (int i : RX) for (int j : LY) if (i != RX[0]) O(i, j);
for (int i : RX) for (int j : RY) if (j != RY[0]) O(i, j);
for (int i : LX) for (int j = 1; j < d; ++j) cout << i << " " << c - j << "\n";
for (int i : RX) for (int j = 1; j < d; ++j) cout << i << " " << c + j << "\n";
} else cout << "No\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
C. [CF17Final-G] Mancala (2)
On prend les éléments depuis la fin. Pour la position actuelle, si on a déjà pris k éléments à droite, on peut effectuer l'opération pendant k+1 moments. Si a_i ≤ i, on peut en prendre ⌊(a_i + k)/i⌋. On enregistre k, qui est de complexité O(n). Complexité temporelle : O(n^3).
// Code C++ pour Mancala
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
int n, m, k, f[100005];
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k; f[0] = 1;
for (int i = n; i >= 1; --i) {
for (int d = m; ~d; --d) if (f[d]) {
int z = f[d]; f[d] = 0;
if (i < k) f[d] = (f[d] + 1ll * z * (k - i)) % MOD;
for (int v = 0; v <= min(i, k); ++v) {
int t = d + (d + v) / i; m = max(m, t);
if ((f[t] += z) >= MOD) f[t] -= MOD;
}
}
}
int z = 1ll * k * (k + 1) / 2 * n;
for (int i = 1; i < n; ++i) z = 1ll * z * (k + 1) % MOD;
for (int i = 0; i <= m; ++i) z = (z + 1ll * (MOD - f[i]) * i) % MOD;
cout << z << "\n";
}
D. [AGC046E] Couverture par permutations (5)
Pour caractériser une séquence légitime, on détermine d'abord les k premiers éléments, puis dans l'intervalle [2, k+1] on trouve le dernier intervalle légitime, et ainsi de suite. On obtient une suite d'intervalles qui ne se chevauchent pas. On peut les décrire par des intersections adjacentes S_i. Si t est connu, on calcule le nombre d'occurrences de chaque élément dans S, qui doit être entre ⌊t/2⌋ et t. On énumère t. Pour trouver S_i, on utilise un algorithme glouton. Complexité temporelle : O(n^2 A).
// Code C++ pour la couverture par permutations
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m, a[MAXN], b[MAXN], f[MAXN];
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], m = max(m, a[i] - 1);
basic_string<int> z{n + 1}, s;
for (;; z = min(z, s), ++m, s.clear()) {
for (int i = 1; i <= n; ++i) b[i] = m + 1 - a[i], f[i] = 0;
if (*max_element(b + 1, b + n + 1) > (m + 1) / 2) break;
for (int t = m; t; --t) {
int mx = 0;
for (int i = 1; i <= n; ++i) if (!b[i] && !f[i]) f[i] = 2, mx = i;
for (int i = 1; i <= mx; ++i) if (!f[i] && t / 2 >= b[i]) f[i] = 2;
if (!mx) for (int i = 1; i <= n; ++i) {
if (!f[i] && t / 2 >= b[i]) {
f[i] = 2;
if (t > 2 * b[i] + 1) break;
} else break;
}
if (!mx && !f[1] && t / 2 >= b[1]) f[1] = 2;
for (int i = 1; i <= n; ++i) if (f[i] == 2) s += i;
for (int i = 1; i <= n; ++i) if (f[i] == 0) s += i, --b[i];
for (int i = 1; i <= n; ++i) f[i] = !f[i];
}
for (int i = 1; i <= n; ++i) if (!f[i]) s += i;
}
if (z[0] > n) z = {-1};
for (int i : z) cout << i << " ";
cout << "\n";
return 0;
}
*E. [AGC074D] Sortie valide pour les problèmes DSU (7)
Soit m = C(n,2). Supposons que les paires de sommets connectés après chaque arête valide soient t_1 à t_{n-1}. Pour un préfixe a[1,i] avec x uns et t_{i-1} < x ≤ t_i, on requiert que les zéros dans a[i+1,m] ne dépassent pas m - t_i. On observe que si la somme des a_i ∈ (t_{k-1}, t_k], alors les préfixes avec x < k sont légitimes. Pour chaque t, on ne s'intéresse qu'à t_{k-1} et t_k, en calculant le coût via le (t_{k-1}+1)-ième 1 et en déplaçant des zéros. On énumère les paires (t_{k-1}, t_k) légitimes en considérant la taille des blocs connectés L, R et le nombre de paires connectées restantes c. La deuxième partie peut être prétraitée avec bitset, et la première partie peut être déterminée par rceherche binaire. Complexité temporelle : O(n^3 log n + n^4 / ω).
// Code C++ pour les problèmes DSU
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 125005;
const ll inf = 1e18;
int S(int x) { return x * (x - 1) / 2; }
bitset <MAXN> f[505], o;
int n, m, s = 0, t = 0, b[MAXN], d[505][505];
ll c[MAXN], z;
ll qry(int x, int y) {
if (x >= s) return inf;
int p = b[x + 1], q = max(0, t - p - (m - y));
return c[p + q] - c[p] - 1ll * q * x;
}
void solve() {
cin >> n; m = S(n); s = t = 0; z = inf;
for (int i = 1, q; i <= m; ++i) cin >> q, (q ? b[++s] = t : c[++t] = s);
if (!s || !t) { cout << "0\n"; return; }
for (int i = 1; i <= t; ++i) c[i] += c[i - 1];
for (int v = 2; v <= n; ++v) for (int i = max(0, s - S(v)); i < s - d[v][1]; ++i) if (f[n - v][i]) {
z = min(z, qry(i + d[v][lower_bound(d[v] + 1, d[v] + v, s - i) - d[v] - 1], i + S(v)));
}
cout << (z == inf ? -1 : z) << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _; f[0] = 1;
for (int i = 1; i <= 500; ++i) {
for (int j = 1; j <= i; ++j) o = f[i - j], o <<= S(j), f[i] |= o, d[i][j] = S(j) + S(i - j);
sort(d[i] + 1, d[i] + i);
}
while (_--) solve();
return 0;
}
*F. [ARC214F] Mouvements imprévisibles (7)
On transforme le problème en un modèle de flot. Les chemins sont transformés en absence de coupe. Un ensemble de points est une coupe s'ils sont 8-connexes, et deux points sur la même ligne avec un point entre eux ne peuvent pas être traversés deux fois vers le bas consécutivement. Ainsi, les points avec distance de Manhattan ≤ 2 sont connectés, et si du coin inférieur gauche au coin supérieur droit ils sont connectés, cela correspond à une coupe. On prouve la nécessité et la suffisance, puis on construit le graphe et on calcule la coupe minimale. Complexité temporelle : O((hw)^{1.5}).
// Code C++ pour les mouvements imprévisibles
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 20005, MAXE = 1e6 + 5, inf = 1e9;
namespace F {
struct Edge {
int v, f, lst;
} G[MAXE];
int S = 1, T = 2, tot = 1, hd[MAXV], cur[MAXV], dep[MAXV];
void init() { tot = 1; memset(hd, 0, sizeof(hd)); }
void adde(int u, int v, int w) { G[++tot] = {v, w, hd[u]}; hd[u] = tot; }
void link(int u, int v, int w) { adde(u, v, w); adde(v, u, 0); }
bool BFS() {
memcpy(cur, hd, sizeof(cur)); memset(dep, -1, sizeof(dep));
queue <int> Q; Q.push(S); dep[S] = 0;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int i = hd[u]; i; i = G[i].lst) if (G[i].f && dep[G[i].v] == -1) {
dep[G[i].v] = dep[u] + 1; Q.push(G[i].v);
}
}
return ~dep[T];
}
int dfs(int u, int f) {
if (u == T) return f;
int r = f;
for (int i = cur[u]; i; i = G[i].lst) {
int v = G[cur[u] = i].v;
if (G[i].f && dep[v] == dep[u] + 1) {
int g = dfs(v, min(r, G[i].f));
if (!g) dep[v] = -1;
G[i].f -= g; G[i ^ 1].f += g; r -= g;
}
if (!r) return f;
}
return f - r;
}
int Dinic() {
int f = 0;
while (BFS()) f += dfs(S, inf);
return f;
}
}
char a[105][105];
int b[105][105][2], n, m, o;
void solve() {
F::init(); cin >> n >> m; o = 2;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
if (a[i][j] == '#') b[i][j][0] = ++o, b[i][j][1] = ++o;
}
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (a[i][j] == '#') {
F::link(b[i][j][0], b[i][j][1], 1);
if (j == 1 || i == n || (j == 2 && i > 1) || (i == n - 1 && j < m)) F::link(1, b[i][j][0], inf);
if (j == m || i == 1 || (i == 2 && j > 1) || (j == m - 1 && i < n)) F::link(b[i][j][1], 2, inf);
for (int x = max(1, i - 2); x <= min(n, i + 2); ++x) for (int y = max(1, j - 2); y <= min(m, j + 2); ++y) {
if (abs(x - i) + abs(y - j) <= 2 && a[x][y] == '#' && (i != x || j != y)) F::link(b[i][j][1], b[x][y][0], inf);
}
}
cout << F::Dinic() << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
G. [ARC211E] Takahashi avide 2 (3)
La permutation obtenue est un ordre DFS, trié en choisissant gloutonnement le point avec le degré minimum, en cas d'égalité on compare les séquences DFS des sous-arbres par ordre lexicographique. On construit l'arbre de manière similaire à DFS, puis on vérifie si les fils de chaque point sont ordonnés de manière croissante. La vérification se fait en O(min(siz_u, siz_v)) par DFS. Complexité temporelle : O(n log n).
// Code C++ pour Takahashi avide
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
vector <int> G[MAXN];
int n, k, v, a[MAXN], fa[MAXN], f[MAXN], d[MAXN];
bool dfs(int u) {
if (a[k] != u) return 0;
if (k == n || a[k + 1] > u) return 1;
for (int r = v, i = v = a[k + 1]; i < r; ++i) {
++k; G[u].push_back(i); fa[i] = u; ++d[u];
if (!dfs(i)) return 0;
}
return 1;
}
int cmp(int x, int y) {
if (G[x].size() != G[y].size()) return G[x].size() < G[y].size() ? -1 : 1;
for (int i = 0; i < (int)G[x].size(); ++i) {
int o = cmp(G[x][i], G[y][i]);
if (o) return o;
}
return 0;
}
void solve() {
cin >> n; k = 1; v = n;
for (int i = 1; i <= n; ++i) cin >> a[i], f[i] = d[i] = 0, G[i].clear();
if (!dfs(n)) { cout << "No\n"; return; }
for (int u = 1; u <= n; ++u) {
for (int i = 1; i < (int)G[u].size(); ++i) if (cmp(G[u][i - 1], G[u][i]) > 0) { cout << "No\n"; return; }
}
cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
H. [ARC213D] Minimiser l'inversion (4.5)
La valeur de a_i = n dépend seulement de la relation entre i-1 et n-i. En fait, a_i dépend du rang de i parmi les éléments inférieurs à a_i. On énumère la contribution de chaque a_i = x, qui dépend de sgn(x - v). On peut transformer algébriquement, et on doit calculer f_t = Σ min(i, t-i) * C(k-1, i) * C(n-k, t-i). C'est une forme de convolution, et on peut utiliser la division pour traiter les cas où min(i, t-i) ≤ mid < max(i, t-i). Complexité temporelle : O(n log^2 n).
// Code C++ pour minimiser l'inversion
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353, N = 1 << 19, G = 3;
int inv[N], fac[N], ifac[N];
namespace P {
int rev[N], w[N << 1];
int ksm(int a, int b = MOD - 2) { int s = 1; for (; b; a = 1ll * a * a % MOD, b >>= 1) if (b & 1) s = 1ll * s * a % MOD; return s; }
void poly_init() {
inv[1] = 1;
for (int i = 2; i < N; ++i) inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
fac[0] = ifac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD, ifac[i] = 1ll * ifac[i - 1] * inv[i] % MOD;
for (int k = 1; k <= N; k <<= 1) {
int x = ksm(G, (MOD - 1) / k); w[k] = 1;
for (int i = 1; i < k; ++i) w[i + k] = 1ll * x * w[i + k - 1] % MOD;
}
}
int plen(int x) { int y = 1; for (; y < x; y <<= 1); return y; }
void ntt(int *f, bool idft, int n) {
for (int i = 0; i < n; ++i) {
rev[i] = (rev[i >> 1] >> 1);
if (i & 1) rev[i] |= n >> 1;
}
for (int i = 0; i < n; ++i) if (rev[i] < i) swap(f[i], f[rev[i]]);
for (int k = 2, x, y; k <= n; k <<= 1) {
for (int i = 0; i < n; i += k) {
for (int j = i; j < i + k / 2; ++j) {
x = f[j]; y = 1ll * f[j + k / 2] * w[k + j - i] % MOD;
f[j] = (x + y >= MOD) ? x + y - MOD : x + y; f[j + k / 2] = (x >= y) ? x - y : x + MOD - y;
}
}
}
if (idft) {
reverse(f + 1, f + n);
for (int i = 0, x = ksm(n); i < n; ++i) f[i] = 1ll * f[i] * x % MOD;
}
}
void poly_mul(const int *f, const int *g, int *h, int n, int m) {
static int a[N], b[N];
for (int i = 0; i < n; ++i) a[i] = f[i];
for (int i = 0; i < m; ++i) b[i] = g[i];
int len = plen(n + m - 1);
ntt(a, 0, len); ntt(b, 0, len);
for (int i = 0; i < len; ++i) h[i] = 1ll * a[i] * b[i] % MOD;
ntt(h, 1, len);
memset(a, 0, sizeof(int) * len);
memset(b, 0, sizeof(int) * len);
}
void poly_inv(const int *f, int *g, int n) {
static int a[N];
g[0] = ksm(f[0]);
int k = 2;
for (; k < (n << 1); k <<= 1) {
for (int i = 0; i < k; ++i) a[i] = f[i];
ntt(g, 0, k << 1); ntt(a, 0, k << 1);
for (int i = 0; i < (k << 1); ++i) {
g[i] = (2 - 1ll * a[i] * g[i] % MOD) * g[i] % MOD;
if (g[i] < 0) g[i] += MOD;
}
ntt(g, 1, k << 1);
memset(g + k, 0, sizeof(int) * k);
}
memset(g + n, 0, sizeof(int) * (k - n));
memset(a, 0, sizeof(int) * k);
}
}
int n, k, z[N], w[N], a1[N], b1[N], a2[N], b2[N];
int C(int x, int y) { return y < 0 || y > x ? 0 : 1ll * fac[x] * ifac[y] % MOD * ifac[x - y] % MOD; }
int Q(int x) { return x & 1 ? 1ll * (x / 2) * (x / 2) % MOD : 1ll * (x / 2) * (x / 2 - 1) % MOD; }
void cdq(int l, int r) {
if (2 * l >= n) return;
if (l == r) { w[2 * l] = (w[2 * l] + 1ll * C(k - 1, l) * C(n - k, l) % MOD * l) % MOD; return; }
int p = (l + r) / 2 + 1;
for (int i = l; i < p; ++i) a1[i - l] = 1ll * C(k - 1, i) * i % MOD, a2[i - l] = 1ll * C(n - k, i) * i % MOD;
for (int i = p; i <= r; ++i) b1[i - p] = C(n - k, i), b2[i - p] = C(k - 1, i);
P::poly_mul(a1, b1, a1, p - l, r - p + 1);
P::poly_mul(a2, b2, a2, p - l, r - p + 1);
for (int i = l + p; i < r + p && i < n; ++i) w[i] = (1ll * w[i] + a1[i - l - p] + a2[i - l - p]) % MOD;
cdq(l, p - 1); cdq(p, r);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
P::poly_init(); cin >> n >> k; inv[1] = 1;
for (int i = 2; i <= n; ++i) inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
for (int i = fac[0] = ifac[0] = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD, ifac[i] = 1ll * ifac[i - 1] * inv[i] % MOD;
for (int x = 1, s = 0; x < n; ++x) s = (s + 1ll * fac[n - 1] * inv[x] % MOD * Q(x)) % MOD, z[x + 1] = (z[x + 1] + s) % MOD;
cdq(0, n - 1);
for (int x = 1; x <= n; ++x) z[x] = (z[x] + 1ll * w[x - 1] * fac[x - 1] % MOD * fac[n - x]) % MOD;
for (int x = n, s = 0; x > 1; --x) {
s = (s + (1ll * Q(x) * C(n - 1, x - 1) + MOD - w[x - 1]) % MOD * fac[x - 2] % MOD * fac[n - x] % MOD) % MOD;
z[x - 1] = (z[x - 1] + s) % MOD;
}
for (int i = 1; i <= n; ++i) cout << z[i] << "\n";
return 0;
}
I. [ARC209D] A_A_i
Pour chaque point où a_{a_i} = -1, on le fait pointer vers 1. Si a_i = -1, il doit pointer vers un point x où a_x = 1. Le choix de x affecte la valeur de a_{a_p} pour a_p = i, donc on choisit le plus petit x possible. On scanne séquentiellement, on essaie de connecter le premier point avec a_i = -1 à 1, et si un seul point reste, on le traite. Enfin, on remplit x dans ces a_i. Complexité temporelle : O(n).
// Code C++ pour A_A_i
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
int n, a[MAXN];
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], a[i] = max(a[i], 0);
if (!a[1]) a[1] = 1;
else if (!a[a[1]]) a[a[1]] = 1;
int x = find(a + 1, a + n + 1, 1) - a, c0 = count(a + 1, a + n + 1, 0);
if (c0 == 1) {
int h = find(a + 1, a + n + 1, 0) - a, t = find(a + 1, a + n + 1, h) - a;
if (t < h) a[h] = 1;
else a[h] = h, a[h] = min_element(a + 1, a + n + 1) - a;
}
for (int i = 2, o = 1; i <= n; ++i) {
if (!a[i]) {
a[i] = -1;
if (!--c0 && x > n) a[i] = 1, x = i;
} else if (!a[a[i]]) a[a[i]] = 1, x = min(x, a[i]), --c0;
else if (a[a[i]] < 0) {
if (o) {
int y = find(a + 1, a + n + 1, 0) - a; o = 0;
if (y < x) x = y, a[x] = 1;
}
}
}
for (int i = 1; i <= n; ++i) if (a[i] < 0) a[i] = x;
for (int i = 1; i <= n; ++i) cout << a[a[i]] << " \n"[i == n];
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
J. [Keyence2019F] Découpe de papier (2)
On énumère un préfixe et le nombre de coupes horizontales dans celui-ci. On peut calculer la réponse en O(1) avec des transformations combinatoires. Complexité temporelle : O(n + m).
// Code C++ pour la découpe de papier
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e7 + 5, MOD = 1e9 + 7, i3 = (MOD + 1) / 3;
int n, m, K, fc[MAXN], ic[MAXN];
int C(int x, int y) { return y < 0 || y > x ? 0 : 1ll * fc[x] * ic[y] % MOD * ic[x - y] % MOD; }
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> K; ic[1] = 1;
for (int i = 2; i < MAXN; ++i) ic[i] = 1ll * ic[MOD % i] * (MOD - MOD / i) % MOD;
for (int i = fc[0] = ic[0] = 1; i < MAXN; ++i) fc[i] = 1ll * fc[i - 1] * i % MOD, ic[i] = 1ll * ic[i - 1] * ic[i] % MOD;
cout << (1ll * K * fc[n + m] + 1ll * K * (K + 1) / 2 % MOD * fc[n + m] + 1ll * i3 * K % MOD * (K - 1) % MOD * (K + 1) % MOD * n % MOD * m % MOD * fc[n + m - 2]) % MOD * ic[n + m - K] % MOD << "\n";
return 0;
}
K. [Diverta2019-2F] Diverta City (4)
En incrémentant, lors de l'ajout d'un point, on s'assure que les chemins différents obtenus par insertion en différents endroits sont distincts, c'est-à-dire que toutes les sommes a_{n,x} + a_{n,y} sont distinctes. De plus, on s'assure que les séquences différentes sont distinctes, en multipliant les poids des arêtes par la longueur du plus long chemin d. On peut contrôler les poids des arêtes en dessous de 9×10^{10}. Complexité temporelle : O(2^n n^3).
// Code C++ pour Diverta City
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[10][10], b[10], f[1 << 10][10];
bool chk(int n) {
unordered_map<ll, int> S;
for (int i = 0; i <= n; ++i) for (int j = i + 1; j <= n; ++j) if (S[b[i] + b[j]]++) return 0;
return 1;
}
ll dis(int n) {
memset(f, 0, sizeof(f));
for (int s = 0; s < (1 << n); ++s) for (int i = 0; i < n; ++i) if (s >> i & 1) {
for (int j = 0; j < n; ++j) if (!(s >> j & 1)) f[s | 1 << j][j] = max(f[s | 1 << j][j], f[s][i] + a[i][j]);
}
return *max_element(f[(1 << n) - 1], f[(1 << n) - 1] + n);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n; b[0] = 0; b[1] = 1;
for (int i = 2; i < n; ++i) while (!chk(i)) ++b[i];
for (int i = 1; i < n; ++i) {
ll d = i > 2 ? dis(i) : i;
for (int j = 0; j < i; ++j) a[i][j] = a[j][i] = d * b[j + 1];
}
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cout << a[i][j] << " \n"[j == n - 1];
return 0;
}
L. [ARC203D] Insertion XOR (2)
Par discussoin, on conserve tous les segments de 0 de longueur ≥ 2 en les transformant en 00, avec un 1 entre eux. On compte le nombre de sous-chaînes "100", en discutant le début et la fin. Complexité temporelle : O(n + q).
// Code C++ pour l'insertion XOR
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int n, q, s, c, a[MAXN];
int w(int x) { return 1 <= x && x <= n - 2 && a[x] && !a[x + 1] && !a[x + 2]; }
int Q() {
if (c == n) return n;
if (c == 0 || c == n - 1) return 2;
if (!s) return (!a[1] && !a[n] ? 3 : 2) + (!a[1] && !a[2]);
int z = 3 * s;
if (!a[1]) z += 1 + !a[2];
if (a[n]) ++z;
else if (a[n - 1]) z += 2;
return z;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], c += a[i];
for (int i = 1; i <= n - 2; ++i) s += w(i);
cin >> q;
for (int x; q--;) {
cin >> x; s -= w(x) + w(x - 1) + w(x - 2); c += 1 - 2 * a[x];
a[x] ^= 1; s += w(x) + w(x - 1) + w(x - 2);
cout << Q() << "\n";
}
return 0;
}
*M. [AGC074E] Supprimer AB (8.5)
On représente AB comme des parenthèses, et on trace la courbe des sommes préfixes ±1. Une chaîne palindromique légitime correspond à une courbe symétrique centrale. On définit S = a_0 + a_n. On conserve seulement les valeurs minimales strictes en préfixe et suffixe. On considère le minimum a_x et son symétrique a_y = S - a_x, puis on récursivement applique l'opération. On utilise un tableau ST pour les minimums intervalles et les premières/dernières occurrences, et on maintient les occurrences avec la technique Mo. La simulation du processus récursif prend O(√n) étapes. Complexité temporelle : O(n√q + q√n).
// Code C++ pour supprimer AB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 5;
int n, m, a[MAXN], b[MAXN], pr[MAXN], sf[MAXN], hd[MAXN], tl[MAXN], Z[MAXN];
struct info { int x, l, r; } mn[19][MAXN], c[MAXN];
info operator+(const info& u, const info& v) {
if (u.x != v.x) return u.x < v.x ? u : v;
return {u.x, min(u.l, v.l), max(u.r, v.r)};
}
info F(int l, int r) {
int k = __lg(r - l + 1);
return mn[k][l] + mn[k][r - (1 << k) + 1];
}
int ql(int x) { return 0 <= x && x <= n ? hd[x] : n + 1; }
int qr(int x) { return 0 <= x && x <= n ? tl[x] : 0; }
int qry(int L, int R) {
int z = -1, S = a[L] + a[R];
for (int o : {0, 1}) {
int x, y;
if (!o) {
x = F(L, R).l; y = qr(S - a[x]);
if (y <= x) continue;
} else {
x = F(L, R).r; y = ql(S - a[x]);
if (y >= x) continue;
}
int w = a[y] - a[x];
for (int p, q; (L < x && x < R) || (L < y && y < R); w += a[y] + a[q] - a[p] - a[x], x = p, y = q) {
if (x < y) {
if ((p = F(y, R).r) == y) break;
if ((q = ql(S - a[p])) > x) break;
} else {
if ((p = F(L, y).l) == y) break;
if ((q = qr(S - a[p])) < x) break;
}
}
if (min(x, y) == L && max(x, y) == R) z = z < 0 ? w : min(z, w);
}
return z;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
string S; cin >> S >> m; n = a[0] = S.size();
for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + (S[i - 1] == 'A' ? 1 : -1);
fill(b, b + n + 1, -1); fill(hd + 1, hd + n + 1, n + 1);
for (int i = 0, x = *min_element(a, a + n + 1); i <= n; ++i) a[i] -= x, swap(b[a[i]], pr[i] = i);
fill(b, b + n + 1, n + 1); fill(tl + 1, tl + n + 1, -1);
for (int i = n; ~i; --i) swap(b[a[i]], sf[i] = i);
for (int i = 0; i <= n; ++i) mn[0][i] = {a[i], i, i};
for (int k = 0; k < 18; ++k) for (int i = 0; i + (2 << k) - 1 <= n; ++i) {
mn[k + 1][i] = mn[k][i] + mn[k][i + (1 << k)];
}
for (int i = 1; i <= m; ++i) cin >> c[i].l >> c[i].r, c[i].x = i, --c[i].l;
int B = n / sqrt(m) + 1, L = 1, R = 0;
sort(c + 1, c + m + 1, [&](auto x, auto y) {
if (x.l / B != y.l / B) return x.l < y.l;
return x.l / B & 1 ? x.r > y.r : x.r < y.r;
});
for (int i = 1; i <= m; ++i) {
while (R < c[i].r) ++R, tl[a[R]] = R, hd[a[R]] = min(hd[a[R]], R);
while (L > c[i].l) --L, hd[a[L]] = L, tl[a[L]] = max(tl[a[L]], L);
for (; L < c[i].l; ++L) {
if (sf[L] > R) hd[a[L]] = n + 1, tl[a[L]] = 0;
else hd[a[L]] = sf[L];
}
for (; R > c[i].r; --R) {
if (pr[R] < L) hd[a[R]] = n + 1, tl[a[R]] = 0;
else tl[a[R]] = pr[R];
}
Z[c[i].x] = qry(c[i].l, c[i].r);
}
for (int i = 1; i <= m; ++i) cout << Z[i] << "\n";
return 0;
}
N. [ARC212F] Ajouter un entier (2)
En générant à l'envers, connaissant a_{i+1} et a_{i+2}, on a a_i = |a_{i+1} - a_{i+2}|. On énumère a_{n-1}, et à partir de (a_{n-1}, x) on applique (x, y) ← (|x-y|, x) n-2 fois. Cela ressemble à l'algorithme d'Euclide, et quand x est beaucoup plus grand que y, on accélère pour obtenir x ≤ y en O(1) opérations, donc seulement O(log m) itérations. Complexité temporelle : O(m log m).
// Code C++ pour ajouter un entier
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int sol(int n, int x, int y) {
if (!y) return n % 3 == 1 ? 1ll * x * x % MOD : 0;
int k = x / y, t = min(k / 2, n / 3);
n -= 3 * t; x -= 2 * t * y;
if (!n) return 1ll * x * y % MOD;
return sol(n - 1, abs(x - y), x);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m, x, z = 0;
cin >> n >> m >> x;
for (int i = 0; i <= m; ++i) z = (z + sol(n - 2, i, x)) % MOD;
cout << z << "\n";
return 0;
}
O. [CodeFes2017-F] Le plus grand décalage cyclique le plus petit (2)
Pour un alphabet de taillle 2, on met uniformément des b après chaque a, obtenant des ab^k et ab^{k+1}. En réordonnant ces chaînes comme a' et b', on obtient un sous-problème (x, y) plus petit. Pour l'alphabet de taille 3, on met uniformément des c après a, et les positions restantes sont remplies de b, se récursivant en (ac^k b, ac^{k+1}, b) ou (ac^k, ac^k b, ac^{k+1}). On prouve qu'en O(1) récursions, Z diminue au moins de moitié. Complexité temporelle : O((X+Y+Z) log Z).
// Code C++ pour le décalage cyclique
#include <bits/stdc++.h>
using namespace std;
string rep(int c, string s) {
string t; while (c--) t += s;
return t;
}
string Q2(int a, int b, string A, string B) {
if (!a || !b) return rep(a, A) + rep(b, B);
A += rep(b / a, B); b %= a;
return Q2(a - b, b, A, A + B);
}
string Q3(int a, int b, int c, string A, string B, string C) {
if (!a) return Q2(b, c, B, C);
if (!b) return Q2(a, c, A, C);
if (!c) return Q2(a, b, A, B);
A += rep(c / a, C); c %= a;
if (b + c >= a) return Q3(a - c, c, b - a + c, A + B, A + C, B);
return Q3(a - b - c, b, c, A, A + B, A + C);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int a, b, c;
cin >> a >> b >> c;
cout << Q3(a, b, c, "a", "b", "c") << "\n";
return 0;
}
P. [AGC029E] TKHS errant (3)
Pour déterminer si u→v a une contribution, soit p = LCA(u, v), alors le minimum sur le chemin u→p doit être inférieur au minimum sur p→1 (sans inclure p). Pour chaque u, si la profondeur maximale < dep_p, c'est légitime; si > dep_p, c'est illégitime. On vérifie si p est le maximum en maintenant la seconde valeur maximale sur le chemin. Complexité temporelle : O(n).
// Code C++ pour TKHS errant
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
vector <int> G[MAXN];
int n, a[MAXN], f[MAXN], mx[MAXN], sc[MAXN], fa[MAXN];
void dfs1(int u, int fz) {
fa[u] = fz; mx[u] = mx[fz]; sc[u] = sc[fz];
if (fa[mx[u]] < fz) sc[u] = mx[u], mx[u] = u;
else if (fa[sc[u]] < fz) sc[u] = u;
for (int v : G[u]) if (v != fz) dfs1(v, u);
}
void dfs2(int u, int w) {
a[u] += w += f[u];
for (int v : G[u]) if (v != fa[u]) dfs2(v, w + 1);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
G[u].push_back(v); G[v].push_back(u);
}
dfs1(1, 0);
for (int u = 2; u <= n; ++u) if (fa[mx[u]] > u) {
++f[sc[u] == mx[fa[mx[u]]] && u < fa[sc[u]] ? fa[mx[u]] : mx[u]];
--f[u];
}
dfs2(1, 0);
for (int i = 2; i <= n; ++i) cout << a[i] << " \n"[i == n];
return 0;
}
Q. [ARC213C] Double X
Sur deux arbres, les sous-arbres de k sont des nœuds gauches et droites, et on doit choisir un appariement de taille 4 de poids minimal. On ne conserve que les 4 arêtes sortantes les plus petites pour chaque nœud gauche, car au moins l'une d'elles est légitime. On utilise une file de priorité pour maintenir les intervalles optimaux, avec fusion de segments d'arbre par sous-arbre et arbres persistants pour les parties extérieures. Complexité temporelle : O(n log n).
// Code C++ pour Double X
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
namespace F {
struct Edge { int v, e, f, w; } G[MAXN * 6];
int S, T, ec, hd[MAXN * 2], pre[MAXN * 2];
bool inq[MAXN * 2];
ll dis[MAXN * 2];
void init() { memset(hd, 0, (T + 1) * 4); ec = 1; }
void adde(int u, int v, int f, int w) { G[++ec] = {v, hd[u], f, w}; hd[u] = ec; }
void link(int u, int v, int f, int w) { adde(u, v, f, w); adde(v, u, 0, -w); }
bool SPFA() {
memset(dis, 0x3f, (T + 1) * 8); memset(pre, 0, (T + 1) * 4); memset(inq, 0, T + 1);
queue <int> Q; Q.push(S); inq[S] = 1; dis[S] = 0;
while (Q.size()) {
int u = Q.front(); Q.pop(); inq[u] = 0;
for (int i = hd[u], v; i; i = G[i].e) if (G[i].f && dis[v = G[i].v] > dis[u] + G[i].w) {
dis[v] = dis[u] + G[i].w; pre[v] = i;
if (!inq[v]) Q.push(v), inq[v] = 1;
}
}
return pre[T];
}
ll ssp() {
int f = 4; ll z = 0;
for (; f && SPFA(); z += dis[T], --f) {
for (int u = T; u != S; u = G[pre[u] ^ 1].v) --G[pre[u]].f, ++G[pre[u] ^ 1].f;
}
return f ? -1 : z;
}
}
int n, a[MAXN];
int cmp(int x, int y) { return a[x] < a[y] ? x : y; }
int ls[MAXN * 72], rs[MAXN * 72], mi[MAXN * 72], tot;
void init() {
for (int i = 1; i <= tot; ++i) ls[i] = rs[i] = mi[i] = 0;
tot = 0;
}
void ins(int x, int y, int l, int r, int q, int &p) {
mi[p = ++tot] = cmp(mi[q], y);
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) ins(x, y, l, mid, ls[q], ls[p]), rs[p] = rs[q];
else ins(x, y, mid + 1, r, rs[q], rs[p]), ls[p] = ls[q];
}
int merge(int l, int r, int q, int p) {
if (!p || !q) return p | q;
int mid = (l + r) >> 1, u = ++tot;
mi[u] = cmp(mi[p], mi[q]);
if (l == r) return u;
ls[u] = merge(l, mid, ls[q], ls[p]); rs[u] = merge(mid + 1, r, rs[q], rs[p]);
return u;
}
int qmn(int ul, int ur, int l, int r, int p) {
if (ul > ur) return 0;
if (ul <= l && r <= ur) return mi[p];
int mid = (l + r) >> 1, s = 0;
if (ul <= mid) s = cmp(s, qmn(ul, ur, l, mid, ls[p]));
if (mid < ur) s = cmp(s, qmn(ul, ur, mid + 1, r, rs[p]));
return s;
}
vector <int> Ga[MAXN], Gb[MAXN];
int dca, dfa[MAXN], efa[MAXN], rk[MAXN], dcb, dfb[MAXN], efb[MAXN];
int rt[MAXN], lrt[MAXN], rrt[MAXN];
void dfs1(int u, int fz) {
dfb[u] = ++dcb;
if (fz) Gb[u].erase(find(Gb[u].begin(), Gb[u].end(), fz));
for (int v : Gb[u]) dfs1(v, u);
efb[u] = dcb;
}
void dfs2(int u, int fz) {
dfa[u] = ++dca; rk[dca] = u; ins(dfb[u], u, 1, n, 0, rt[u]);
if (fz) Ga[u].erase(find(Ga[u].begin(), Ga[u].end(), fz));
for (int v : Ga[u]) dfs2(v, u), rt[u] = merge(1, n, rt[u], rt[v]);
efa[u] = dca;
}
int ha[MAXN], hb[MAXN];
void solve() {
cin >> n; init(); dca = dcb = rrt[n + 1] = 0;
for (int i = 1; i <= n; ++i) cin >> a[i], Ga[i].clear(), Gb[i].clear();
for (int i = 1, u, v; i < n; ++i) cin >> u >> v, Ga[u].push_back(v), Ga[v].push_back(u);
for (int i = 1, u, v; i < n; ++i) cin >> u >> v, Gb[u].push_back(v), Gb[v].push_back(u);
dfs1(1, 0); dfs2(1, 0);
for (int i = 1; i <= n; ++i) ins(dfb[rk[i]], rk[i], 1, n, lrt[i - 1], lrt[i]);
for (int i = n; i >= 1; --i) ins(dfb[rk[i]], rk[i], 1, n, rrt[i + 1], rrt[i]);
for (int u = 1; u <= n; ++u) {
if (Ga[u].size() < 3 || Gb[u].size() < 3) { cout << "-1 \n"[u == n]; continue; }
int qa = 1, qb = 1;
ha[1] = dfa[u] - 1; hb[1] = dfb[u] - 1;
for (int v : Ga[u]) ha[++qa] = efa[v];
for (int v : Gb[u]) hb[++qb] = efb[v];
ha[++qa] = hb[++qb] = n;
F::S = qa; F::T = qa + qb; F::init();
for (int i = 1; i < qa; ++i) F::link(qa, i, 1, 0);
for (int i = 1; i < qb; ++i) F::link(qa + i, qb + qa, 1, 0);
auto link = [&](int x) {
int l = dfa[x] > efa[u] ? 1 : lower_bound(ha + 1, ha + qa, dfa[x]) - ha;
int r = dfb[x] > efb[u] ? 1 : lower_bound(hb + 1, hb + qb, dfb[x]) - hb;
F::link(l, r + qa, 1, a[x]);
};
auto find = [&](auto&& f) {
priority_queue <array<int, 4>> Q;
auto push = [&](int l, int r) {
int o = f(l, r);
if (o) Q.push({-a[o], o, l, r});
};
push(1, n);
for (int c = 4, o = 0; Q.size();) {
int x = Q.top()[1], l = Q.top()[2], r = Q.top()[3]; Q.pop();
if ((dfb[x] < dfb[u] || efb[u] < dfb[x]) && o++);
else --c, link(x);
int i = lower_bound(hb + 1, hb + qb + 1, dfb[x]) - hb;
push(l, hb[i - 1]); push(hb[i] + 1, r);
}
};
find([&](int l, int r){ return cmp(qmn(l, r, 1, n, lrt[dfa[u] - 1]), qmn(l, r, 1, n, rrt[efa[u] + 1])); });
for (int v : Ga[u]) find([&](int l, int r){ return qmn(l, r, 1, n, rt[v]); });
cout << F::ssp() << " \n"[u == n];
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _; a[0] = 1e9 + 1;
while (_--) solve();
return 0;
}
R. [AGC053E] Plus de pics, plus de fun (4.5)
Soit a_i < b_i. On trouve x tel que b_x n'est pas un pic, alors [1, x) satisfait b_{i-1} > a_i et (x, n] satisfait b_{i+1} > a_i. Pour compter les séquences sans x, c'est-à-dire tous les b_{i-1} > a_i, on insère par ordre décroissant de b_i, et chaque x interdit l'insertion de i dans son prédécesseur. Pour le problème général, on énumère les étiquettes i, j des intervalles [x, x+1] qui ne se chevauchent pas. Complexité temporelle : O(n).
// Code C++ pour plus de pics
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 5, MOD = 1e9 + 7;
int n, l[MAXN], r[MAXN], c[MAXN * 2];
ll iv[MAXN], f[MAXN], g[MAXN], vl[MAXN], vr[MAXN], h[MAXN * 2];
array<int, 2> e[MAXN];
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n; iv[1] = 1;
for (int i = 2; i <= n; ++i) iv[i] = iv[MOD % i] * (MOD - MOD / i) % MOD;
for (int i = 1; i <= n; ++i) {
cin >> e[i][0] >> e[i][1];
if (e[i][0] < e[i][1]) swap(e[i][0], e[i][1]);
}
sort(e + 1, e + n + 1, greater<>());
for (int i = 1; i <= n; ++i) l[i] = e[i][1], r[i] = e[i][0], ++c[l[i]];
for (int i = 2 * n; i >= 1; --i) c[i] += c[i + 1];
f[0] = g[0] = vl[0] = vr[n + 1] = 1;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1] * (i - c[r[i] + 1]) % MOD;
g[i] = g[i - 1] * iv[i - c[r[i] + 1]] % MOD;
vl[i] = vl[i - 1] * (i + 1 - c[r[i] + 1]) % MOD;
}
for (int i = n; i >= 1; --i) vr[i] = vr[i + 1] * (i - 1 - c[r[i] + 1]) % MOD;
ll z = f[n];
for (int y = 1; y <= n; ++y) h[r[y]] = f[y - 1] * vr[y + 1] % MOD;
for (int i = 1; i <= 2 * n; ++i) h[i] = (h[i - 1] + h[i]) % MOD;
for (int x = 1; x <= n; ++x) z = (z + vl[x - 1] * g[x] % MOD * h[l[x] - 1]) % MOD;
cout << z << "\n";
return 0;
}
S. [APC001F] Arbre XOR (3)
Le chemin XOR équivaut à appliquer XOR sur deux chemins jusqu'à la racine. On note b_x le XOR de chaque chemin depuis la racine. À chaque opération, on applique XOR à au plus deux b avec la même valeur, et on connecte les b qui sont XORés ensemble, formant une forêt où chaque composante a un XOR global de 0. Les valeurs apparaissent en paires, et après réduction modulo 2, on peut utiliser la programmation dynamique avec compression de bits pour compter le nombre d'opérations. Complexité temporelle : O(n + 3^a).
// Code C++ pour l'arbre XOR
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, a[MAXN], c[16], f[1 << 16], z, o;
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1, u, v, w; i < n; ++i) cin >> u >> v >> w, a[u] ^= w, a[v] ^= w;
for (int i = 1; i < n; ++i) ++c[a[i]];
for (int i = 1; i < 16; ++i) z += (c[i] + 1) / 2, c[i] &= 1, o |= c[i] << i;
for (int s = 1; s < (1 << 16); ++s) if ((s | o) == o) {
int w = 0;
for (int i = 1; i < 16; ++i) if (s >> i & 1) w ^= i;
if (w) continue;
for (int b = o ^ s, x = b; ; x = (x - 1) & b) {
f[x | s] = max(f[x | s], f[x] + 1);
if (!x) break;
}
}
cout << z - f[o] << "\n";
return 0;
}
T. [Tenka2019F] X interdit (3)
On supprime d'abord les 0. Pour une séquence de 1 et 2, on énumère la somme v. On observe le nombre de préfixes dans [0, v]. Si v ≥ X, on doit supprimer X, donc X±1 ne peuvent pas être supprimés, et ainsi de suite. Les restrictions deviennent qu'il faut remplir environ (v - X)/2 des 2 au début et à la fin, et le reste est arbitraire. On énumère v et le nombre de 1 au milieu pour calculer le nombre de séquences. Complexité temporelle : O(n^2).
// Code C++ pour X interdit
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005, MOD = 998244353;
int n, X, C[MAXN][MAXN], f[MAXN], z;
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> X;
for (int i = 0; i <= n; ++i) for (int j = C[i][0] = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
for (int x = 0; x <= n; ++x) for (int y = 0; x + y <= n; ++y) if (x + 2 * y < X) z = (z + 1ll * C[n][x + y] * C[x + y][x] % MOD) % MOD;
for (int v = X; v <= 2 * n; ++v) if ((v - X) & 1) {
int c = v - X + 1;
if (c <= v - c) {
for (int i = 0; 2 * i <= v - 2 * c; ++i) {
int x = v - 2 * c - 2 * i, y = i + c;
if (x + y <= n) z = (z + 1ll * C[n][x + y] * C[x + i][x]) % MOD;
}
} else if (X & 1) z = (z + C[n][v / 2]) % MOD;
}
cout << z << "\n";
return 0;
}
*U. [AGC048F] Enregistrement 01 (8.5)
On inverse la séquence. La séquence originale est une fusion de plusieurs chaînes 10101..., notées S_x. On extrait la plus longue sous-séquence Q à chaque fois. On prouve que R = T - Q ∈ S. Si |R| + 2 ≤ |Q|, on peut faire |R| ← |R| + 2, |Q| ← |Q| - 2. Cela se généralise à T = S_x + S_y devenant S_{x'} + S_{y'} avec x ≤ x' ≤ y' ≤ y et même parité. On prouve qu'un ensemble x_1 à x_m est légitime si et seulement si pour la solution gloutonne b_1 à b_q, dans chaque préfixe, le nombre de 0 et 1 de x ne dépasse pas celui de b. On utilise la programmation dynamique de l'ordre inverse pour calculer x. Complexité temporelle : O(n^3 log n).
// Code C++ pour l'enregistrement 01
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
void add(int &x, const int &y) { x = x + y >= MOD ? x + y - MOD : x + y; }
char s[305];
int n, v0[305], v1[305], f[305][305][305], z;
int qry() {
int c = 0;
for (int i = n - 1; ~i; --i) if (s[i] == '1' - c % 2) s[i] = 0, ++c;
return c;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> s; n = strlen(s);
for (int i = 1, x; i <= n; ++i) x = qry(), v0[i] = v0[i - 1] + x / 2, v1[i] = v1[i - 1] + (x + 1) / 2;
if (v0[n] + v1[n] < n) { cout << "0\n"; return 0; }
f[0][0][0] = 1;
for (int w = n; w; --w) {
int c0 = w / 2, c1 = (w + 1) / 2;
for (int i = 1; i <= n / w; ++i) for (int x = i * c0; x <= v0[i]; ++x) for (int y = i * c1; y <= v1[i]; ++y) {
add(f[i][x][y], f[i - 1][x - c0][y - c1]);
}
}
for (int i = 1; i <= n; ++i) add(z, f[i][v0[n]][v1[n]]);
cout << z << "\n";
return 0;
}
*V. [WTF22-1E] Trier A[i] - i (9)
On établit une bijection entre a et une séquence de ±1 avec m +1 et n -1, où la hauteur après chaque -1 correspond à a_i - i. Pour chaque y = v, on doit compter combien de -1 sont au-dessus. Pour n = m, v = 0, le nombre de -1 au-dessus de 0 à n est uniformément Catalan_n. On utilise la réflexion par inclusion-exclusion. On peut écrire la solution en termes de combinaisons. Complexité temporelle : O(n).
// Code C++ pour trier A[i] - i
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 5, MOD = 998244353;
ll fc[MAXN], ic[MAXN], iv[MAXN], f[MAXN], df[MAXN];
ll C(int x, int y) { return y < 0 || y > x ? 0 : fc[x] * ic[y] % MOD * ic[x - y] % MOD; }
ll cat(int x) { return C(2 * x, x) * iv[x + 1] % MOD; }
ll P(int x, int y) { return (C(x + y - 1, y) + MOD - C(x + y - 1, x)) % MOD; }
struct ds {
int a, m, n, r; ll z;
ds(int M = 0, int N = 0) : a(0), m(M), n(N), r(-1), z(0) {}
ll q(int A, int R) {
if (R < 0) return 0;
while (r < R) ++r, z = (z + C(r, a) * C(n - r, m - a)) % MOD;
while (a < A) ++a, z = (z + (MOD - C(r + 1, a)) * C(n - r, m + 1 - a)) % MOD;
return z;
}
} g[3][2];
int n, m;
ll Q(int a, int b, int l, int r) {
if (a < 0 || b < 0 || l > r) return 0;
int c = n - a - b;
return (g[c][0].q(a, r) + MOD - g[c][1].q(a, l - 1)) % MOD;
}
signed main() {
iv[1] = fc[0] = ic[0] = 1;
for (int i = 2; i < MAXN; ++i) iv[i] = (MOD - MOD / i) * iv[MOD % i] % MOD;
for (int i = 1; i < MAXN; ++i) fc[i] = fc[i - 1] * i % MOD, ic[i] = ic[i - 1] * iv[i] % MOD;
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) f[i + 1] = (f[i + 1] + P(i + m - n, i)) % MOD;
for (int k = 1; k < n; ++k) f[k + 1] = (f[k + 1] + C(2 * k + m - n - 1, k - 1)) % MOD;
for (int i = 0; i <= n; ++i) f[i] = f[i] * cat(n - i + 1) % MOD;
for (int x : {0, 1, 2}) g[x][0] = g[x][1] = ds(n - x, m + n - 1);
for (int i = 0; i <= n; ++i) {
int l = 2 * i, r = 2 * i + m - n - 2;
ll z = (Q(i, n - i, l, r) + Q(i - 1, n - i - 1, l, r) + 2 * MOD - Q(i - 1, n - i, l, r) - Q(i, n - i - 1, l, r)) % MOD;
if (i < n) f[i + 1] = (f[i + 1] + z) % MOD;
if (i > 1) f[n - i + 2] = (f[n - i + 2] + MOD - z) % MOD;
}
for (int j = 0; j < n; ++j) df[j + 1] = (df[j + 1] + P(j + m - n, j)) % MOD;
for (int k = 1; k < n; ++k) df[k + 1] = (df[k + 1] + C(2 * k + m - n - 1, k - 1)) % MOD;
for (int i = 0; i <= n; ++i) df[i] = df[i] * cat(n - i + 1) % MOD;
for (int i = 1; i <= n; ++i) f[i] = (f[i - 1] + f[i]) % MOD, df[i] = (df[i - 1] + df[i]) % MOD;
for (int i = 1; i <= n; ++i) f[i] = (f[i - 1] + f[i]) % MOD, df[i] = (df[i - 1] + df[i]) % MOD;
for (int i = 1; i <= n; ++i) cout << (f[i] + MOD - df[n - i + 1]) % MOD << "\n";
return 0;
}
W. [AGC074C] PORALIS (3.5)
On construit récursivement deux solutions de taille n/2, puis on remplit le bit de poids fort des éléments de la seconde moitié avec 1, obtenant des séquences de longueur paire. Pour ajouter optionnellement +1 à la longueur, on crée un nouveau bit de poids fort et on ne l'applique qu'au dernier élément, en indiquant si l'OR de ce bit correspond à une longueur +1. Si n est pair, on construit une solution de taille n/2 - 1, puis on crée deux nouveaux bits de poids fort pour +1/+2, avec une plage de valeurs en O(n^3), mais réellement ≤ 2^26. Complexité temporelle : O(n).
// Code C++ pour PORALIS
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1035;
int a[2][MAXN], b[2][MAXN];
int dp(int o, int n) {
if (n == 1) {
a[o][1] = 1; b[o][1] = 0;
return 1;
}
if (n == 2) {
a[o][1] = 1; a[o][2] = 2;
b[o][1] = 3; b[o][2] = 0;
return 2;
}
if (n & 1) {
int m = n / 2, k = dp(o ^ 1, m), x = 1 << k, y = 2 << k;
for (int i = 1; i <= m; ++i) a[o][i] = a[o ^ 1][i], a[o][i + m] = a[o ^ 1][i] | x;
for (int i = 2; i <= n; ++i) {
if (i & 1) b[o][i] = b[o ^ 1][i / 2];
else b[o][i] = b[o ^ 1][i / 2] | y;
}
a[o][n] = y; b[o][1] = 2 * y - 1;
return k + 2;
} else {
int m = n / 2 - 1, k = dp(o ^ 1, m), x = 1 << k, y = 2 << k, z = 4 << k;
for (int i = 1; i <= m; ++i) a[o][i] = a[o ^ 1][i], a[o][i + m] = a[o ^ 1][i] | x;
for (int i = 2; i <= n - 1; ++i) {
if (i & 1) b[o][i] = b[o ^ 1][i / 2] | z;
else b[o][i] = b[o ^ 1][i / 2] | y | z;
}
a[o][n - 1] = y; a[o][n] = z; b[o][1] = 2 * z - 1; b[o][n] = 0;
return k + 3;
}
}
void solve() {
int n; cin >> n; dp(0, n);
for (int i = 1; i <= n; ++i) cout << a[0][i] << " \n"[i == n];
for (int i = 1; i <= n; ++i) cout << b[0][i] << " \n"[i == n];
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
X. [Dwacon6E] Couverture par intervalles (2)
On applique l'inclusion-exclusion pour chaque segment de longueur 1 pour savoir s'il est couvert. On s'intéresse seulement à la collection de longueurs des segments restants S. Pour un intervalle de longueur k, le nombre de séquences est Σ_{x ∈ S} max(0, S - k + 1). On ajoute les éléments dans S en ordre inverse, en enregistrant |S| et ΣS. Complexité temporelle : O(X^3).
// Code C++ pour la couverture par intervalles
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int ksm(int a, int b = MOD - 2) { int s = 1; for (; b; a = 1ll * a * a % MOD, b >>= 1) if (b & 1) s = 1ll * s * a % MOD; return s; }
int n, m, a[505], f[505][505], fc[505], ic[505], z;
int C(int x, int y) { return y < 0 || y > x ? 0 : 1ll * fc[x] * ic[y] % MOD * ic[x - y] % MOD; }
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = fc[0] = ic[0] = 1; i <= m; ++i) ic[i] = ksm(fc[i] = 1ll * i * fc[i - 1] % MOD);
for (int i = 1, x; i <= n; ++i) cin >> x, ++a[x];
f[0][0] = 1;
for (int i = m; i >= 1; --i) {
for (int c = m / (i + 1); ~c; --c) for (int s = c * (i + 1); s <= m; ++s) if (f[c][s]) {
for (int t = 1; s + t * i <= m; ++t) {
f[c + t][s + t * i] = (f[c + t][s + t * i] + 1ll * f[c][s] * ic[t]) % MOD;
}
}
if (a[i]) for (int c = 0; c <= m / i; ++c) for (int s = c * i; s <= m; ++s) f[c][s] = 1ll * f[c][s] * ksm(s - (i - 1) * c, a[i]) % MOD;
}
for (int c = 0; c <= m; ++c) for (int s = c; s <= m - c + 1; ++s) if (f[c][s]) {
z = (z + 1ll * ((m - s) & 1 ? MOD - f[c][s] : f[c][s]) * fc[c] % MOD * C(m - s + 1, c)) % MOD;
}
cout << z << "\n";
return 0;
}
Y. [AGC045D] Lampes et boutons (5)
On suppose que les opérations x = 1 à A sont effectuées en ordre croissant. Si p_x ≠ x, alors le cycle entier est allumé; si p_x = x, c'est un échec. On trouve le premier x tel que p_x = x, et on exige que tous les éléments > A aient un cycle passant par [1, x). On utilise une approche similaire aux nombres de Stirling du premier type. Complexité temporelle : O(n^2).
// Code C++ pour lampes et boutons
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e7 + 5, MOD = 1e9 + 7;
int n, m;
ll fc[MAXN], ic[MAXN], iv[MAXN];
ll C(int x, int y) { return y < 0 || y > x ? 0 : fc[x] * ic[y] % MOD * ic[x - y] % MOD; }
ll sol(int X, int Y, int Z) { return fc[X + Y + Z] * X % MOD * iv[X + Y] % MOD; }
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m; iv[1] = 1;
for (int i = 2; i <= n; ++i) iv[i] = iv[MOD % i] * (MOD - MOD / i) % MOD;
for (int i = fc[0] = ic[0] = 1; i <= n; ++i) fc[i] = fc[i - 1] * i % MOD, ic[i] = ic[i - 1] * iv[i] % MOD;
ll z = 0;
for (int i = 0; i < m; ++i) {
z = (z + (i & 1 ? MOD - C(m, i) : C(m, i)) * sol(m - i, n - m, 0)) % MOD;
}
for (int k = 2; k <= m; ++k) for (int i = 0; i < k - 1; ++i) {
z = (z + (i & 1 ? MOD - C(k - 1, i) : C(k - 1, i)) * sol(k - 1 - i, n - m, m - k)) % MOD;
}
cout << z << "\n";
return 0;
}
Z. [Tenka2018F] Circulaire (3)
Chaque valeur forme un intervalle, et la longueur de l'intervalle contenant 1 est le nombre d'opérations d. On détermine l'intervalle d'insertion pour chaque valeur v : les éléments > v dans les premiers d ne peuvent pas être insérés, et si v apparaît, l'intervalle est restreint. On insère par ordre croissant, en utilisant un arbre de segments pour maintenir les positions. Complexité temporelle : O(n log n).
// Code C++ pour circulaire
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5, MOD = 998244353;
int n, a[MAXN], ct[MAXN * 4];
vector <int> b[MAXN];
bool tg[MAXN * 4];
void psu(int p) { ct[p] = ct[p << 1] + ct[p << 1 | 1]; }
void adt(int p) { tg[p] = 1; ct[p] = 0; }
void psd(int p) { if (tg[p]) adt(p << 1), adt(p << 1 | 1), tg[p] = 0; }
void init(int l = 1, int r = n, int p = 1) {
ct[p] = r - l + 1;
if (l == r) return;
int mid = (l + r) >> 1;
init(l, mid, p << 1); init(mid + 1, r, p << 1 | 1);
}
void upd(int ul, int ur, int l = 1, int r = n, int p = 1) {
if (ul <= l && r <= ur) return adt(p);
int mid = (l + r) >> 1; psd(p);
if (ul <= mid) upd(ul, ur, l, mid, p << 1);
if (mid < ur) upd(ul, ur, mid + 1, r, p << 1 | 1);
psu(p);
}
int qry(int ul, int ur, int l = 1, int r = n, int p = 1) {
if (ul <= l && r <= ur) return ct[p];
int mid = (l + r) >> 1, s = 0; psd(p);
if (ul <= mid) s += qry(ul, ur, l, mid, p << 1);
if (mid < ur) s += qry(ul, ur, mid + 1, r, p << 1 | 1);
return s;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n; init();
for (int i = 1; i <= n; ++i) cin >> a[i];
int x = find(a + 1, a + n + 1, 1) - a;
if (x > n) { cout << "0\n"; return 0; }
if (x > 1) rotate(a + 1, a + x, a + n + 1);
else for (int i = n; i >= 1; --i) if (a[i] > 1) { rotate(a + 1, a + i + 1, a + n + 1); break; }
for (int i = 1; i <= n; ++i) b[a[i]].push_back(i);
for (int i = 1; i <= n; ++i) if (b[i].size()) {
if (b[i].back() - b[i][0] + 1 > (int)b[i].size()) { cout << "0\n"; return 0; }
}
int d = b[1].size() - 1, z = 1;
if (d == n - 1) {
for (int i = 1; i <= n; ++i) z = 1ll * i * z % MOD;
cout << z << "\n"; return 0;
}
for (int i = n; i >= 1; --i) {
if (b[i].empty()) z = 1ll * z * max(0, ct[1] - i + 1) % MOD;
else {
int l = b[i][0], r = b[i].back();
if (r - l > d) { cout << "0\n"; return 0; }
z = 1ll * z * qry(r - d, l) % MOD;
if (i > 1) upd(l - d, r);
}
}
cout << z << "\n";
return 0;
}
AA. [ARC214E] Échanger K fois (2)
Si a est une permutation, on calcule inv(a) / K. Sinon, on apparie gloutonnement dans l'ordre optimal, et si la parité de la permutation doit être ajustée, on échange deux positions adjacentes avec la même valeur a, et le changement d'inversions est une somme de points en 2D. Complexité temporelle : O(n log n).
// Code C++ pour échanger K fois
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 5;
int n, K, a[MAXN], b[MAXN], p[MAXN], l[MAXN], r[MAXN], f[MAXN], tr[MAXN];
vector <int> va[MAXN], vb[MAXN];
ll z, iv;
void chk(ll x) {
if (K % 2 == 0 && x % 2) return;
ll t = (x + K - 1) / K;
if (K * t % 2 != x % 2) ++t;
z = z < 0 ? t : min(z, t);
}
int qry(int x) { int s = 0; for (; x; x &= x - 1) s += tr[x]; return s; }
void solve() {
cin >> n >> K; z = -1; iv = 0;
for (int i = 1; i <= n; ++i) l[i] = r[i] = f[i] = 0, va[i].clear(), vb[i].clear(), tr[i] = 0;
for (int i = 1; i <= n; ++i) cin >> a[i], va[a[i]].push_back(i);
for (int i = 1; i <= n; ++i) cin >> b[i], vb[b[i]].push_back(i);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < (int)va[i].size(); ++j) p[va[i][j]] = vb[i][j];
for (int j = 1; j < (int)va[i].size(); ++j) l[va[i][j]] = va[i][j - 1], r[va[i][j - 1]] = va[i][j];
}
for (int i = n; i >= 1; --i) {
iv += qry(p[i]);
if (l[i]) f[l[i]] -= qry(p[i]) - qry(p[l[i]]);
if (r[i]) f[i] += qry(p[r[i]] - 1) - qry(p[i]);
for (int x = p[i]; x <= n; x += x & -x) ++tr[x];
}
chk(iv);
for (int i = 1; i <= n; ++i) if (r[i]) chk(iv + 2 * f[i] + 1);
cout << z << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
AB. [APC001I] Problème APSP simple (3.5)
On divise les lignes et colonnes contenant des obstacles, et on contracte le reste. On ne s'intéresse qu'à la distance entre les quatre coins de chaque zone. On calcule directement les contributions des lignes et colonnes sans obstacles, et on fait un BFS sur le graphe de grille réduit pour les obstacles. Complexité temporelle : O(n^4).
// Code C++ pour le problème APSP
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 5, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, MOD = 1e9 + 7;
int n, mx, my, qx, qy, a[35], b[35], lx[65], ly[65], rx[65], ry[65], sz[65][65];
int bx[MAXN], by[MAXN], cx[MAXN], cy[MAXN], d[65][65];
bool is[65][65];
void bfs(int sx, int sy) {
queue <array<int, 2>> Q;
memset(d, 0x3f, sizeof(d)); d[sx][sy] = 0; Q.push({sx, sy});
while (Q.size()) {
int x = Q.front()[0], y = Q.front()[1]; Q.pop();
for (int o : {0, 1, 2, 3}) {
int i = x + dx[o], j = y + dy[o];
if (1 <= i && i <= qx && 1 <= j && j <= qy && !is[i][j] && d[i][j] > d[x][y] + 1) Q.push({i, j}), d[i][j] = d[x][y] + 1;
}
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> mx >> my >> n; bx[1] = by[1] = 1;
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i]; ++cx[++a[i]]; ++cy[++b[i]];
bx[a[i]] = by[b[i]] = bx[a[i] + 1] = by[b[i] + 1] = 1;
}
ll S = (1ll * mx * my - n) % MOD, Sx = 0, Sy = 0, z = 0;
for (int i = 1; i <= mx; Sx = (Sx + my - cx[i]) % MOD, ++i) {
if (bx[i]) bx[i] = ++qx, lx[qx] = rx[qx] = i;
else bx[i] = qx, rx[qx] = i, z = (z + Sx * (S + MOD - Sx)) % MOD;
}
for (int i = 1; i <= my; Sy = (Sy + mx - cy[i]) % MOD, ++i) {
if (by[i]) by[i] = ++qy, ly[qy] = ry[qy] = i;
else by[i] = qy, ry[qy] = i, z = (z + Sy * (S + MOD - Sy)) % MOD;
}
for (int i = 1; i <= n; ++i) is[bx[a[i]]][by[b[i]]] = 1;
for (int i = 1; i <= qx; ++i) for (int j = 1; j <= qy; ++j) if (!is[i][j]) sz[i][j] = 1ll * (rx[i] - lx[i] + 1) * (ry[j] - ly[j] + 1) % MOD;
for (int i = 1; i <= qx; ++i) for (int j = 1; j <= qy; ++j) if (!is[i][j]) {
bfs(i, j);
for (int x = i; x <= qx; ++x) for (int y = x > i ? 1 : j + 1; y <= qy; ++y) if (!is[x][y]) {
z = (z + 1ll * sz[i][j] * sz[x][y] % MOD * d[x][y]) % MOD;
}
}
cout << z << "\n";
return 0;
}
*AC. [AGC053D] Tout le monde est un gagnant (8)
Soit a_{i,j} la note du i-ème participant au j-ème problème, et s_{i,j} la somme préfixe correspondante. On peut montrer par adjustment que s_i[1, a_i] et s_i(a_i, n] sont décroissants. On trie les a_i en ordre décroissant, et de i = n à 1, on échange un 3 à gauche et un 2 à droite, ou un 2 à gauche et un 1 à droite, en donnant priorité aux échanges (2,1). Complexité temporelle : O(n).
// Code C++ pour tout le monde est un gagnant
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, inf = 1e9;
int n, a[MAXN], b[MAXN], c[MAXN];
void solve() {
cin >> n;
int x = inf, y = inf;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i] >> c[i], x = min(x, c[i]), y = min(y, 2 * c[i] + b[i]);
for (int i = n; i >= 1; --i) {
int u = min(c[i], i), v = min(b[i], i - u), w = min(a[i], i - u - v), h = 3 * u + 2 * v + w - min({3 * i, x + 2 * i, y + i}), k;
k = min({h, v, a[i] - w}), h -= k, v -= k, w += k; //2->1
k = min({h / 2, u, a[i] - w}), h -= 2 * k, u -= k, w += k; //3->2->1
k = min({h, u, b[i] - v}), h -= k, u -= k, v += k; //3->2
k = min({(h + 1) / 2, u, a[i] - w}), h -= 2 * k, u -= k, w += k; //3->1
if (h > 0) { cout << "No\n"; return; }
x = min(x, u); y = min(y, 2 * u + v);
}
cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_--) solve();
return 0;
}
AD. [ARC130F] Remplacer par la moyenne (3.5)
On transforme a en enveloppe convexe inférieure, en traitant le problème d'arrondi. On découvre qu'une droite de pente k arrondie devient un segment de pente ⌊k⌋ et un segment de pente ⌈k⌉, ce qui peut être maintenu avec une pile monotone. Complexité temporelle : O(n).
// Code C++ pour remplacer par la moyenne
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 5;
int n, b[MAXN], h;
ll a[MAXN];
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
b[h = 1] = 1;
for (int i = 2; i <= n; ++i) {
for (; h > 1 && (a[b[h]] - a[b[h - 1]]) / (b[h] - b[h - 1]) >= (a[i] - a[b[h]]) / (i - b[h]); --h);
ll x = a[i] - a[b[h]], y = i - b[h], r = (x % y + y) % y, k = (x - r) / y;
b[++h] = i - r; a[b[h]] = a[b[h - 1]] + k * (b[h] - b[h - 1]);
if (r) b[++h] = i;
}
ll z = a[b[h]];
for (int i = 1; i < h; ++i) {
for (int j = b[i]; j < b[i + 1]; ++j) z += a[b[i]] + (a[b[i + 1]] - a[b[i]]) / (b[i + 1] - b[i]) * (j - b[i]);
}
cout << z << "\n";
return 0;
}
*AE. [AGC048E] Relation étrange (8)
Les préfixes sont légitimes quel que soit leur remplissage, car la pente y - x ∈ [-1, +∞) passera par 0. On ordonne les éléments par a_i + (i - 1)T, le premier maximum x doit avoir a_x = x_1, et on supprime x en faisant avancer les éléments suivants. Pour calculer a_i, on compare quand chaque a_j est supprimé par rapport à a_i. On peut maintenir le nombre d'éléments non supprimés avec une programmation dynamique en ordre inverse. Complexité temporelle : O(n^3 k^2).
// Code C++ pour relation étrange
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, m, t, a[55][55], f[55][55], z[55];
void add(int &x, const int &y) { x = x + y >= MOD ? x + y - MOD : x + y; }
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> t;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j];
for (int h = n, w = 1; h >= 1; w = 1ll * w * m % MOD, --h) for (int v : a[h]) if (v) {
memset(f, 0, sizeof(f)); f[h][0] = w;
for (int i = h - 1; i; --i) for (int j = 0; j < h; ++j) for (int x : a[i]) if (x) {
if (x >= v + (j + 1) * t) add(f[i][j], f[i + 1][j]);
else add(f[i][j + 1], f[i + 1][j]);
}
for (int i = 0; i < h; ++i) z[h] = (z[h] + 1ll * i * f[1][i]) % MOD;
}
for (int i = 1; i <= n; ++i) cout << z[i] << "\n";
return 0;
}
*AF. [AGC046F] Tournoi interdit (8.5)
On réduit le graphe de tournoi en une chaîne de composantes fortement connexes. Les composantes non terminales ne contiennent pas de triangles, donc elles sont des points isolés. On énumère la longueur de la chaîne et on compte les graphes de tournoi fortement connexes. On partitionne les nœuds en prédécesseurs L et successeurs R d'un nœud rt. L est une chaîne, et R se réduit à une chaîne. On caractérise les bords entre L et R. Complexité temporelle : O(n^4).
// Code C++ pour le tournoi interdit
#include <bits/stdc++.h>
using namespace std;
int MOD, f[205][205];
void add(int &x, const int &y) { x = x + y >= MOD ? x + y - MOD : x + y; }
int solve(int n, int k) {
if (!k) return n == 1;
int w = 0;
for (int L = 1; L < n - 1; ++L) {
int R = n - 1 - L;
if (max(L, R) > k) continue;
memset(f, 0, sizeof(f));
for (int i = 0; i < R; ++i) f[0][i] = R - i <= k && i + L <= k;
for (int i = 1; i < L; ++i) {
for (int j = 0, s = 0; j <= R; ++j) {
add(s, f[i - 1][j]);
if (R - j + i <= k && L - i + j <= k) f[i][j] = s;
}
}
for (int j = 0; j <= R; ++j) add(w, f[L - 1][j]);
}
return w;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, k, z = 0; cin >> n >> k >> MOD;
for (int p = 0; p <= k; ++p) {
int w = solve(n - p, k - p);
for (int i = 1; i <= n; ++i) if (i != n - p) w = 1ll * w * i % MOD;
add(z, w);
}
cout << z << "\n";
return 0;
}