コンテンツにスキップ

数え上げ

タグ「数え上げ」の記事 13 件

ABC482 E - Diameter Endpoint Colors

NN 頂点の木 TT があり、頂点 vv は色 CvC_v で塗られています。同じ色で、間の距離(パスの辺の本数)が木の直径と等しい頂点の組 (u,v)(u, v)(u<vu < v)の個数を求める問題です(N≤2×105N \le 2 \times 10^5)。

直径の長さを DD とします。木の直径の中点を中心と呼ぶと、距離がちょうど DD になる組は中心を使って次のように分けられます。

  • D=2rD = 2r が偶数のとき、中心は頂点 cc です。どの頂点も cc からの距離が rr 以下なので、距離が DD になる組は、cc からの距離がどちらも rr で、パスが cc を通るもの、つまり cc の異なる隣接頂点の側(部分木)にあるものです。
  • D=2r+1D = 2r + 1 が奇数のとき、中心は辺 (c1,c2)(c_1, c_2) です。この辺を除いて c1c_1 側と c2c_2 側に分けると、距離が DD になる組は、c1c_1 側で c1c_1 からの距離が rr の頂点と、c2c_2 側で c2c_2 からの距離が rr の頂点の組です。

どちらの場合も、直径の端点になる頂点をいくつかのグループに分けると、「距離が DD になる」ことと「異なるグループに属する」ことが同値になります。偶数のときは cc の隣接頂点ごと、奇数のときは c1c_1 側と c2c_2 側の 22 つがグループです。

あとは、異なるグループにある同じ色の頂点の組を数えればよいです。グループを順に見ていき、色ごとに「それまでのグループに含まれる頂点の個数」を持っておきます。各頂点について、その色の個数を答えに足してから、グループ内の頂点をまとめて個数に加えます。

直径と中心は BFS を 22 回するなどして求められるので、全体の計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/graph/tree_util.hpp"
#include "shogo-library/utility/vector_func.hpp"
void solve() {
LL(N);
Tree<ll> tree(N);
tree.read();
VL(C, N);
C--;
vl cnt(N);
ll ans = 0;
for (auto g : tree_diameter_endpoint_groups(tree)) {
for (ll u : g)
ans += cnt[C[u]];
for (ll u : g)
cnt[C[u]]++;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tree_diameter_endpoint_groups は、上の解法のとおり直径の端点をグループに分けて返す関数です。C-- で色を 0 始まりにし、cnt に色ごとの個数を持っています。

使用ライブラリ:cpp_include@cb82602

SamCoding Round 9 (Div. 4) G - No Cheating

nn 個の椅子に kk 人の生徒を、どの 2 人も隣り合わないように座らせる方法の数を 109+710^9 + 7 で割った余りで求める問題です。どの椅子に人が座るかだけを区別します。クエリが qq 個あり、それぞれで次の 2 種類のどちらかが与えられます(1≤q≤1051 \le q \le 10^5、3≤n≤1063 \le n \le 10^6、0≤k≤n0 \le k \le n)。

  • t=1t = 1:椅子が 11 列に並んでいる。椅子 ii と隣り合うのは椅子 i−1,i+1i - 1, i + 1 だけ。
  • t=2t = 2:椅子が円形に並んでいる。上に加えて、椅子 11 と椅子 nn も隣り合う。

k=0k = 0 のときは 11 通り、k=1k = 1 のときはどちらの場合も nn 通りなので、以下では k≥2k \ge 2 とします。

空いている椅子 n−kn - k 個を先に並べると、その間と両端に n−k+1n - k + 1 個の隙間ができます。生徒が隣り合わないのは、生徒を異なる隙間に 1 人ずつ入れるときなので、答えは隙間から kk 個を選ぶ方法の数

(n−k+1k)\binom{n - k + 1}{k}

です。n−k+1<kn - k + 1 < k、つまり 2k−1>n2k - 1 > n のときは 00 です。

1 列の場合の数え方では、椅子 11 と椅子 nn の両方に座る並べ方も数えてしまっているので、それを引きます。

椅子 11 と椅子 nn の両方に座るとき、椅子 22 と椅子 n−1n - 1 は空いていなければなりません。残りの k−2k - 2 人は、椅子 33 から n−2n - 2 までの n−4n - 4 個の椅子に 1 列の場合と同じ条件で座るので、((n−4)−(k−2)+1k−2)=(n−k−1k−2)\binom{(n - 4) - (k - 2) + 1}{k - 2} = \binom{n - k - 1}{k - 2} 通りです。よって答えは

(n−k+1k)−(n−k−1k−2)\binom{n - k + 1}{k} - \binom{n - k - 1}{k - 2}

です。円形では kk 人の間に空いた椅子が kk 個以上必要なので、2k>n2k > n のときは 00 です。

二項係数は、10610^6 程度までの階乗とその逆元を前計算しておけば O(1)O(1) で求まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/combinatorics.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint1000000007;
using C = Combination<mint>;
void solve() {
LL(t, n, k);
if (k <= 1) {
if (k == 0)
print(1);
else
print(n);
return;
}
if (t == 1) {
if (k + k - 1 <= n) {
print(C::C(n - k + 1, k));
} else {
print(0);
}
} else {
if (2 * k <= n) {
print(C::C(n - k + 1, k) - C::C(n - k - 1, k - 2));
} else {
print(0);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(q);
rep(q)
solve();
}

Combination<mint> は階乗とその逆元の表を使って二項係数を求めるクラスで、C::C(n, r) が (nr)\binom{n}{r} です。

使用ライブラリ:cpp_include@4b58304

競プロキャンプ2026関西 F - Keep Far

NN 個の座席が一列に並んでいて、KK 人が順に 1 人ずつ座ります。各人は、左右の両隣に誰も座っていない空席があればその中から 1 つを選び、なければ空席から好きに 1 つを選んで座ります。最終的に座っている席が文字列 SS の # の位置と一致するような座り方の個数を、998244353998244353 で割った余りで求める問題です(1≤K≤N≤30001 \le K \le N \le 3000、# はちょうど KK 個)。

両隣に誰も座っていない空席を「よい席」と呼びます。座り方は 2 つの段階に分かれます。

  • 前半:よい席がある間は、よい席に座ります。前半に座る席の集合を II とすると、II のどの 2 席も隣り合いません。
  • 後半:よい席がなくなったら、残りの人は好きな空席に座ります。人が増えるとよい席は減る一方なので、後半によい席が復活することはありません。

前半が終わるのは、II に入っていないどの席にも、隣に II の席があるときです。

KK 人とも、座る時点で両隣が空いています。よって、どの順に座ってもルールに従っていて、答えは K!K! です。

隣り合う 2 席のうち後に座る人は、よい席でない席に座るので、後半に座っています。よって、前半は最後まで終わっていなければなりません。つまり II は次の条件を満たします。

  • II は # の席だけからなり、どの 2 席も隣り合わない。
  • II に入っていない席(. の席も含む)はすべて、隣に II の席がある。

特に、どの # とも隣り合わない . があれば、この条件を満たす II はないので答えは 00 です。

逆に、条件を満たす II を 1 つ決めて ∣I∣=i|I| = i とすると、前半の ii 人は II の席に好きな順で座れて i!i! 通り、後半の K−iK - i 人は残りの # の席に好きな順で座れて (K−i)!(K - i)! 通りです。したがって、条件を満たす II のうち ∣I∣=i|I| = i のものの個数を cic_i として、答えは

∑ii! (K−i)! ci\sum_{i} i! \, (K - i)! \, c_i

です。

II の席を左から p1<p2<⋯<pip_1 < p_2 < \dots < p_i とすると、条件は次のように言い換えられます。

  • どの pjp_j も # の席である。
  • pj+1−pjp_{j+1} - p_j は 22 か 33 である(隣り合わず、間の席はどれも II の席と隣り合う)。
  • p1p_1 は 11 か 22、pip_i は N−1N - 1 か NN である(両端の席も II の席と隣り合う)。

そこで、席を左から見ていき、「直前に選んだ席が何個前か」と「これまでに選んだ個数」を状態にして DP をします。計算量は O(N2)O(N^2) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/combinatorics.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/utility/container_func.hpp"
using mint = modint998244353;
using C = Combination<mint>;
void solve() {
LL(N, K);
STR(S);
ll full = true;
rep(i, N) {
if (S[i] == '#')
continue;
if (i > 0 && S[i - 1] == '#')
continue;
if (i < N - 1 && S[i + 1] == '#')
continue;
full = false;
}
rep(i, 1, N) {
if (S[i - 1] == '#' && S[i] == '#' && !full) {
print(0);
return;
}
}
if (not full) {
print(C::factorial(K));
return;
}
ary<vec<mint>, 3> dp = {vec<mint>(N + 1), vec<mint>(N + 1), vec<mint>(N + 1)};
dp[1][0] = 1;
for (char c : S) {
vec<mint> ndp(N + 1);
if (c == '#') {
rep(i, 1, N + 1) {
ndp[i] += dp[0][i - 1];
ndp[i] += dp[1][i - 1];
}
}
std::swap(dp[0], dp[1]);
std::swap(dp[1], dp[2]);
std::swap(dp[2], ndp);
}
mint ans = 0;
rep(i, K + 1) {
ans += C::factorial(K - i) * C::factorial(i) * (dp[1][i] + dp[2][i]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

full は「どの . の席も # の席と隣り合う」かどうかです。full でないときは、隣り合う # があれば 00、なければ K!K! を出力します。full のときは、隣り合う # がなくても DP に進みますが、そのときは II がすべての # の席になるしかないので、DP でも K!K! が求まります。

DP では、今の席を見る直前の時点で、dp[2][i] が「直前の席を選んだ」、dp[1][i] が「2 つ前の席を選んだ」、dp[0][i] が「3 つ前の席を選んだ」状態で、ii 個選んだときの場合の数です。今の席が # なら、dp[0] と dp[1] から今の席を選べます。そのあと 3 つの配列をずらして、次の席から見た状態にしています。はじめに dp[1][0] = 1 としているのは、席 11 の 2 つ左に仮の席が選ばれているとみなすためで、こうすると最初に選ぶ席は 11 か 22 になります。最後は、最後に選んだ席が NN か N−1N - 1 である dp[2] と dp[1] を使います。

modint998244353 は 998244353998244353 で割った余りで計算する整数型で、C::factorial(n) は n!n! を返します。場合の数は非常に大きくなるので、DP の配列も mint にしておく必要があります。

使用ライブラリ:cpp_include@9c33ee7

ABC480 E - Product-Bounded Arithmetic Sequences

長さが 33 以上で、公差が正の、正整数からなる等差数列を良い数列と呼びます。良い数列のうち、要素の総積が NN 以下であるものの個数を求める問題です(1≤N≤10181 \le N \le 10^{18})。

良い数列は、長さ ll、初項 aa、公差 dd で決まります(l≥3l \ge 3、a≥1a \ge 1、d≥1d \ge 1)。総積は

a(a+d)(a+2d)⋯(a+(l−1)d)a (a + d) (a + 2d) \cdots (a + (l - 1)d)

です。答えは 101210^{12} 程度になる(入力例 2)ので 1 つずつ数えることはできませんが、ll と aa を全探索して、dd の個数をまとめて数えれば間に合います。

  • ll の範囲:総積が最小になるのは a=d=1a = d = 1 のときで、その値は l!l! です。20!≈2.4×1018>101820! \approx 2.4 \times 10^{18} > 10^{18} なので、l≤19l \le 19 です。
  • aa の範囲:総積は a3a^3 より大きいので、a<106a < 10^6 です。
  • dd の個数:ll と aa を決めると、総積は dd について単調増加です。よって総積が NN 以下になる dd は 11 以上のある値 DD 以下のすべての整数で、その個数 DD は二分探索で求められます。総積は 2d22d^2 より大きいので、D<109D < 10^9 です。

aa を大きくしても総積は増えるので、ある aa で D=0D = 0 になったら、それより大きい aa も調べる必要はありません。計算量は、l=3l = 3 のときの 10610^6 個の aa のそれぞれで二分探索をするのがいちばん重く、全体で 10810^8 回程度の計算です。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/saturating.hpp"
#include "shogo-library/utility/binary-search.hpp"
void solve() {
LL(N);
ll ans = 0;
rep(l, 3, 20) {
rep(a, 1, 1e6) {
ll ng = 1e9;
ll ok = binary_search(0, ng, [=](ll x) {
ll p = a, t = a;
rep(l - 1) {
t += x;
p = saturating_mul(p, t);
if (p > N)
break;
}
return p <= N;
});
if (ok == 0)
break;
ans += ok;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ここでは f(x) が「公差 x のときの総積が NN 以下か」なので、返り値がそのまま DD になります。f(0) が偽(つまり al>Na^l > N)のときも、すべての x で偽なので 00 が返り、D=0D = 0 として扱えます。

総積の計算では、saturating_mul で掛け算がオーバーフローしたときに long long の最大値に丸めています。

使用ライブラリ:cpp_include@9c33ee7

ShareOJ Programming Contest vol.1 E - Solicitation of Murder

NN 頂点 MM 辺の有向グラフが与えられます。辺 a→ba \to b は「囚人 aa は囚人 bb に殺意を持っている」ことを表します。「生存している a,ba, b で辺 a→ba \to b があるものを選び、bb を殺す」という操作を好きな回数行ったあと、生存している囚人の集合としてありうるものの個数を 998244353998244353 で割った余りを求める問題です。

テストケースは TT 個あり、NN の総和と MM の総和はそれぞれ 2×1052 \times 10^5 以下です。

グラフを強連結成分分解します。外から入ってくる辺がない強連結成分(入次数 00 の成分)を、ここでは始点成分と呼びます。

生存者の集合 SS がありうるのは、すべての始点成分に SS の頂点が 1 つ以上あるときで、そのときに限ります。

必要性. 始点成分 CC の頂点を殺せるのは、CC の頂点だけです。CC の頂点が全員殺されたとすると、CC の中で最後に殺された頂点を殺した頂点は CC の中にいて、そのあとに殺されています。これは最後であることに反します。よって、CC には生存者が残ります。

十分性. どの頂点も、どこかの始点成分から到達できます。強連結成分の中では互いに到達できるので、すべての始点成分に SS の頂点があれば、すべての頂点が SS のどれかの頂点から到達できます。そこで、SS からの距離 d(v)d(v) を考え、SS にない頂点を d(v)d(v) が大きい順に殺します。d(v)=t≥1d(v) = t \ge 1 の頂点 vv には、d(u)=t−1d(u) = t - 1 で辺 u→vu \to v がある頂点 uu があります。uu は SS の頂点か、vv よりあとに殺す頂点なので、vv を殺すときにはまだ生きています。したがって、vv を殺せます。

条件は成分ごとに独立です。

  • 始点成分 CC では、空でない部分集合ならどれでもよいので 2∣C∣−12^{|C|} - 1 通りです。
  • それ以外の成分 CC では、制限がないので 2∣C∣2^{|C|} 通りです。

これらの積が答えです。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/graph.hpp"
#include "shogo-library/graph/graph_util.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
rep(M) {
LL(a, b);
a--, b--;
g.add_directed_edge(a, b);
}
vl dp(N);
auto tmp = strongly_connected_components(g);
mint ans = 1;
for (const auto &f : tmp) {
ll x = 0;
for (ll u : f) {
x |= dp[u];
}
ans *= mint(2).pow(f.size()) - !x;
for (ll u : f) {
for (ll v : g[u])
dp[v] = 1;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

strongly_connected_components は強連結成分をトポロジカル順に返します。dp[v] は「すでに処理した成分から vv に入る辺がある」ことを表すフラグです。成分 f を見る時点で、f に外から入る辺はすべて前の成分から来ているので、x が 00 なら f は始点成分です。成分の中の辺で立つフラグは、x を求めたあとに立てています。

使用ライブラリ:cpp_include@397a51d

AALC001 E - RGB

長さ NN の非負整数列 AA と、R, G, B からなる長さ NN の文字列 SS が与えられます。次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:l≤i<j<k≤rl \le i < j < k \le r かつ Si,Sj,SkS_i, S_j, S_k がこの順に R, G, B である組 (i,j,k)(i, j, k) すべてについての AiAjAkA_i A_j A_k の総和を、998244353998244353 で割った余りを出力する。

セグメント木の各ノードに、担当区間について次の 6 つの値を持たせます。

  • R\mathrm{R}:SiS_i が R である ii についての AiA_i の総和(G, B についても同様に G\mathrm{G}, B\mathrm{B})
  • RG\mathrm{RG}:i<ji < j かつ Si,SjS_i, S_j がこの順に R, G である組についての AiAjA_i A_j の総和(GB\mathrm{GB} も同様)
  • RGB\mathrm{RGB}:求めたい値

隣り合う区間 XX(左)と YY(右)をつなげるとき、たとえば RG\mathrm{RG} になる組は「両方 XX の中」「両方 YY の中」「R が XX、G が YY」のどれかです。最後の場合の総和は RXGY\mathrm{R}^X \mathrm{G}^Y なので、次のように合成できます。

RGXY=RGX+RGY+RXGYGBXY=GBX+GBY+GXBYRGBXY=RGBX+RGBY+RGXBY+RXGBY\begin{aligned} \mathrm{RG}^{XY} &= \mathrm{RG}^X + \mathrm{RG}^Y + \mathrm{R}^X \mathrm{G}^Y \\ \mathrm{GB}^{XY} &= \mathrm{GB}^X + \mathrm{GB}^Y + \mathrm{G}^X \mathrm{B}^Y \\ \mathrm{RGB}^{XY} &= \mathrm{RGB}^X + \mathrm{RGB}^Y + \mathrm{RG}^X \mathrm{B}^Y + \mathrm{R}^X \mathrm{GB}^Y \end{aligned}

R\mathrm{R}, G\mathrm{G}, B\mathrm{B} はそれぞれの和です。これをセグメント木に載せれば、全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
enum E {
R,
G,
B,
RG,
GB,
RGB,
};
void solve() {
LL(N, Q);
VL(A, N);
STR(S);
struct AALC0001E {
struct S {
ary<mint, 6> cnt;
S() : cnt{} {}
S(char x, mint a) : cnt{} {
if (x == 'R') {
cnt[E::R] += a;
} else if (x == 'G') {
cnt[E::G] += a;
} else if (x == 'B') {
cnt[E::B] += a;
} else {
assert(false);
}
}
};
static S op(const S &a, const S &b) {
S res = S();
res.cnt[E::R] = a.cnt[E::R] + b.cnt[E::R];
res.cnt[E::G] = a.cnt[E::G] + b.cnt[E::G];
res.cnt[E::B] = a.cnt[E::B] + b.cnt[E::B];
res.cnt[E::RG] = a.cnt[E::RG] + b.cnt[E::RG] + a.cnt[E::R] * b.cnt[E::G];
res.cnt[E::GB] = a.cnt[E::GB] + b.cnt[E::GB] + a.cnt[E::G] * b.cnt[E::B];
res.cnt[E::RGB] = a.cnt[E::RGB] + b.cnt[E::RGB] + a.cnt[E::RG] * b.cnt[E::B] + a.cnt[E::R] * b.cnt[E::GB];
return res;
}
static S e() { return S(); }
};
vec<AALC0001E::S> init;
init.reserve(N);
rep(i, N)
init.emplace_back(S[i], A[i]);
SegTree<AALC0001E> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, {S[i - 1], x});
} else if (q == 2) {
LL(l, r);
print(seg.prod(l - 1, r).cnt[E::RGB]);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。6 つの値は enum E の名前で配列 cnt に入れています。

使用ライブラリ:cpp_include@402f0cf

DOJ Beginner Contest 11 G - Déjà vu

正の整数列 a=(a1,a2,…,aN)a = (a_1, a_2, \dots, a_N) が与えられます。空でない部分列 bb に対して、次の操作を何回でも行えます。

  • 素数 pp を 1 つ選び、bb の要素のうち pp で割り切れるものをすべて同時に pp で割る。

bb の要素をすべて同じ値にするとき、その値の最大値を f(b)f(b) とします。すべての空でない部分列 bb についての f(b)f(b) の和を 998244353998244353 で割った余りを求める問題です。

ai≤2×105a_i \le 2 \times 10^5 で、NN の総和は 5×1055 \times 10^5 以下、max⁡a\max a の総和は 2×1052 \times 10^5 以下です。

素数 pp ごとに考えます。bb の各要素を素因数分解したときの pp の指数を見ると、pp を選ぶ操作は、正の指数をすべて 11 ずつ減らし、00 の指数はそのままにします。

最後にすべての指数を e>0e > 0 でそろえるには、正の指数どうしの差は変わらず、00 の指数は増えないので、はじめからすべての指数が ee でなければなりません。そうでなければ、すべて 00 にそろえるしかありません。

よって、f(b)f(b) は「bb のすべての要素で指数が等しい素数」について pep^e を掛けたものです。ここから次のことがいえます。

  • bb のすべての要素が c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形で書ける   ⟺  \iff cc を割り切るどの素数についても、bb のすべての要素の指数が cc の指数と等しい   ⟺  \iff f(b)=c⋅df(b) = c \cdot d(gcd⁡(c,d)=1\gcd(c, d) = 1)と書ける

f(b)=cf(b) = c となる部分列の個数

Section titled “f(b)=cf(b) = cf(b)=c となる部分列の個数”

aa の要素のうち、c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形のものの個数を tct_c とします。これらだけからなる空でない部分列は 2tc−12^{t_c} - 1 個あり、上の性質から、これはちょうど f(b)=c⋅jf(b) = c \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)となる部分列全体です。f(b)=cf(b) = c となる部分列の個数を gcg_c とすると、

gc=2tc−1−∑j≥2, gcd⁡(c,j)=1gcjg_c = 2^{t_c} - 1 - \sum_{j \ge 2,\ \gcd(c, j) = 1} g_{cj}

です。cc の大きい順に計算すれば、右辺の gcjg_{cj} はすでに求まっています。答えは ∑cc⋅gc\sum_c c \cdot g_c です。

M=max⁡aM = \max a とすると、cc ごとに M/cM / c 個の倍数を見るので、全体で O(Mlog⁡M)O(M \log M) 回の gcd⁡\gcd 計算です。

Python
from math import gcd
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = max(A)
tmp0 = [0] * (M + 1)
tmp1 = [0] * (M + 1)
for a in A:
tmp0[a] += 1
ans = 0
for i in reversed(range(1, M + 1)):
t = tmp0[i]
u = 0
for j in range(2, M // i + 1):
if gcd(i, j) != 1:
continue
t += tmp0[i * j]
u += tmp1[i * j]
v = (pow(2, t, MOD) - u - 1) % MOD
tmp1[i] = v
ans += i * v
ans %= MOD
print(ans)

tmp0[x] は値 xx の要素の個数、tmp1[c] は gcg_c です。t が tct_c、u が ∑gcj\sum g_{cj} にあたります。

DOJ Beginner Contest 11 D - Cipher Guess

英大文字だけからなる NN 個の暗号文の単語 C1,C2,…,CNC_1, C_2, \dots, C_N と、平文の単語 SS が与えられます。

単一換字式暗号(同じ文字は同じ文字に、異なる文字は異なる文字に置き換える)で SS を変換した結果になりうる単語を、候補とよびます。候補のうち暗号文に最も多く現れる単語を求める問題です。同数なら辞書順で最小のものを答え、候補がなければ -1 を出力します。

∣Ci∣,∣S∣≤20|C_i|, |S| \le 20 で、NN の総和は 10510^5 以下です。

単語 CC が候補であるための条件は、「SS で同じ文字が現れる位置の組」と「CC で同じ文字が現れる位置の組」が一致することです。

たとえば ABBA なら、A の位置が {0,3}\{0, 3\}、B の位置が {1,2}\{1, 2\} です。XYYX も {0,3},{1,2}\{0, 3\}, \{1, 2\} に分かれるので候補です。XYYY は {0},{1,2,3}\{0\}, \{1, 2, 3\} になるので候補ではありません。

そこで、各単語について文字ごとの出現位置のリストを作り、それをソートしたものを比べます。長さが違う単語は、位置の範囲が違うので自然に一致しません。

候補を Counter で数えます。あらかじめ CC を辞書順にソートしておくと、Counter には辞書順に単語が入ります。most_common は同数の要素を入れた順に返すので、most_common(1) で「最多で、同数なら辞書順最小」の単語が得られます。

単語の長さを LL とすると、全体で O(NL+Nlog⁡N)O(NL + N \log N) です。

Python
from collections import defaultdict, Counter
for _ in range(int(input())):
N = int(input())
C = input().split()
C.sort()
S = input()
d = defaultdict(list)
for i, a in enumerate(S):
d[a].append(i)
ans = Counter()
X = sorted(d.values())
for f in C:
d = defaultdict(list)
for i, a in enumerate(f):
d[a].append(i)
Y = sorted(d.values())
if X == Y:
ans[f] += 1
if ans:
print(ans.most_common(1)[0][0])
else:
print(-1)

Codeforces Round 1125 (Div. 3) C - Unrequited Love

長さ nn の整数列 a1,…,ana_1, \dots, a_n があります(6≤n≤2⋅1056 \le n \le 2 \cdot 10^5、∣ai∣≤104|a_i| \le 10^4)。1≤x≤n−41 \le x \le n - 4 に対して、鍵 x,x+2,x+4x, x + 2, x + 4 の組を「トライアド xx」と呼び、その値を ax+ax+2−ax+4a_x + a_{x+2} - a_{x+4} とします。

鍵を共有せず、値が等しい 2 つのトライアドの組(順序は区別しない)の個数を求めてください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

vx=ax+ax+2−ax+4v_x = a_x + a_{x+2} - a_{x+4} とおきます。

鍵を共有するのはどんなときか

Section titled “鍵を共有するのはどんなときか”

トライアド x<yx < y の鍵は {x,x+2,x+4}\{x, x+2, x+4\} と {y,y+2,y+4}\{y, y+2, y+4\} です。y−xy - x が奇数なら偶奇が違うので共有しません。y−x≥6y - x \ge 6 なら離れすぎていて共有しません。したがって、鍵を共有するのは y−x=2y - x = 2 または y−x=4y - x = 4 のときだけです。

鍵の共有を気にせずに、値が等しいペアをすべて数えてから、鍵を共有するペアを引きます。

  • 値が等しいペアの総数:vv をソートすると、同じ値が連続して並びます。同じ値が kk 個あれば、そこから (k2)=k(k−1)2\binom{k}{2} = \frac{k(k-1)}{2} 個のペアが作れます。
  • 鍵を共有するペア:vx=vx+2v_x = v_{x+2} となる xx の個数と、vx=vx+4v_x = v_{x+4} となる xx の個数を足したものです。

答えは前者から後者を引いたものです。計算量はソートがあるので O(nlog⁡n)O(n \log n) です。

補足:辞書で数えるとハックされる

Section titled “補足:辞書で数えるとハックされる”

vyv_y と等しい vxv_x(x<yx < y)の個数を、Counter などの辞書で数えながら左から見ていく方法も考えられます。ただ、Python でこの方法を提出したところ、PyPy でも TLE になりました(テスト 7)。

テスト 7 は、奇数番目の要素がすべて 00 の入力です。そのため奇数位置の vxv_x はすべて 00 になり、辞書のキー 00 が約 10510^5 回検索されます。一方、偶数位置の vxv_x は、キー 00 を検索するときにたどる位置をほかのキーで埋め尽くすように作られていると考えられます。Python の整数のハッシュ値は値そのものなので、キーが予測できればこのような入力を作れてしまいます。その結果、検索のたびに長い列をたどることになって TLE します。

対策としては、次のどちらかがあります。

  • 起動時に決めた乱数とキーの XOR をとってから辞書に入れる(ハックする側が衝突を狙えなくなる)
  • 上の解法のように、ハッシュを使わずにソートで数える

ここでは後者を採用しています。C++ の std::map は平衡二分木でハッシュを使わないので、辞書で数える方法でも問題ありません。

Python
from itertools import groupby
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = N - 4
v = [A[i] + A[i + 2] - A[i + 4] for i in range(M)]
ans = 0
for _, g in groupby(sorted(v)):
k = len(list(g))
ans += k * (k - 1) // 2
for i in range(M):
if i + 2 < M and v[i] == v[i + 2]:
ans -= 1
if i + 4 < M and v[i] == v[i + 4]:
ans -= 1
print(ans)

groupby(sorted(v)) で同じ値の並びごとに個数 k を数え、(k2)\binom{k}{2} を足しています。そのあと、位置の差が 22 と 44 で値が等しいものを引いています。

C++(std::map で数える)
#include "sh-library/base/all"
void solve() {
LL(N);
VL(A, N);
mll c;
ll ans = 0;
deque<ll> d;
rep(i, N - 4) {
ll t = A[i] + A[i + 2] - A[i + 4];
ans += c[t];
if (d.size() >= 1 && d[d.size() - 1] == t) {
ans++;
}
if (d.size() >= 3 && d[d.size() - 3] == t) {
ans++;
}
while (d.size() >= 4) {
c[d.front()]++;
d.pop_front();
}
d.push_back(t);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

左から順に見て、トライアド yy と組になる x<yx < y を数えています。

  • y−x≥5y - x \ge 5 の分は、c(値ごとの個数を持つ std::map)で数えます。
  • y−xy - x が 11 と 33 の分は、直近 4 個の値を持つ d で個別に確かめます。

y−xy - x が 22 と 44 のペアは鍵を共有するので数えません。

使用ライブラリ:cpp_include@6e9980e

SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain

正の整数の列 b1,…,bnb_1, \dots, b_n に対して、g(b)ig(b)_i を「ii より左にあって bj<bib_j < b_i を満たす jj のうち最大のもの(なければ 00)」と定めます。ある bb によって y=g(b)y = g(b) と書ける列 yy を「復元可能」と呼びます。

長さ nn の列 xx が与えられます。xx のいくつかの要素は −1-1 です。−1-1 をそれぞれ 00 以上 nn 以下の整数に置き換えて xx を復元可能にする方法の数を、109+710^9 + 7 で割った余りで求めてください(nn の総和 ≤5000\le 5000)。

bb の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 1,…,n1, \dots, n で並べます。値が等しい要素は、後ろにあるほうを小さいとみなします。gg の定義が真の不等号 bj<bib_j < b_i なので、こうすると「bj<bib_j < b_i」と「jj のほうが小さい(j<ij < i のとき)」が一致します。

このとき、ii の左部分木はちょうど区間 [gi+1,i−1][g_i + 1, i - 1] になります。ii の左部分木は「ii から左へ、ii より大きい要素が続く範囲」で、その左端の外側が ii より左で最も近い小さい要素、つまり gig_i だからです。

gg とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。

  • 根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
  • ii を追加するときは、bib_i より大きい要素をスタックから pop する。pop した部分が ii の左部分木になり、ii は残ったスタックの一番上の右の子になる。最後に ii を push する

pop し終わったときのスタックの一番上が、ちょうど gig_i です(空なら 00)。そのため、各ステップで何個 pop するかは gg から決まり、ツリーの形も gg から決まります。逆に、どんな形のツリーにも、それを作る bb が存在します(例えば、根からの深さをそのまま bb にすればよいです)。

まとめると、復元可能な yy と、nn 頂点の二分木の形は一対一に対応します。全部が −1-1 のときの答えは Catalan 数 CnC_n で、サンプル 3 の 132=C6132 = C_6 と一致します。

例えば g=[0,1,2,1,0,0,6]g = [0, 1, 2, 1, 0, 0, 6] に対応するツリーの親は、[5,4,2,1,6,−,6][5, 4, 2, 1, 6, -, 6] です(6 が根)。4 の左部分木が [g4+1,3]=[2,3][g_4 + 1, 3] = [2, 3] になっていることなどが確かめられます。

この対応を使うと、問題は次のように言い換えられます。

頂点 1,…,n1, \dots, n を中間順に並べた二分木のうち、xi≠−1x_i \ne -1 であるすべての ii について「ii の左部分木がちょうど [xi+1,i−1][x_i + 1, i - 1] である」ものを数える

xi≥ix_i \ge i のときは、そのような左部分木はありえないので答えは 00 です。

固定された左部分木は独立に数えられる

Section titled “固定された左部分木は独立に数えられる”

xi≠−1x_i \ne -1 のとき、ii の左部分木 [xi+1,i−1][x_i + 1, i - 1] は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと ii に潰してしまえば、ii は「左の子を持たない頂点」 として扱えます。

そこで、左から順に頂点を見ながら、次のように列を潰していきます。

  • xi=−1x_i = -1 のとき:ii を「自由な頂点」として列の末尾に加える
  • xi≠−1x_i \ne -1 のとき:列の中から xi+1x_i + 1 以降に始まる要素をすべて取り出す。それらが ii の左部分木になるので、その形の数を答えに掛ける。そのあと、xi+1x_i + 1 から ii までをまとめて「左の子を持たない頂点」1 個として末尾に加える

列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が xi+1x_i + 1 から始まる要素になっていないとき、つまり xi+1x_i + 1 がすでに潰された要素の内側にあるときは、答えは 00 です。ii の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。

最後に残った列全体の形の数も掛ければ、答えになります。

左の子を持たない頂点を含む二分木の数え上げ

Section titled “左の子を持たない頂点を含む二分木の数え上げ”

あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。

Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが hh のとき、次の頂点を追加する方法は次のとおりです。

  • 自由な頂点:00 個以上 hh 個以下を pop してから push するので、新しい高さは 11 以上 h+1h + 1 以下
  • 左の子を持たない頂点:pop しないで push するので、新しい高さは h+1h + 1

pop の仕方とツリーの形は一対一に対応するので、dp[h]\mathrm{dp}[h] を「スタックの高さが hh になる方法の数」とする DP で数えられます。自由な頂点の遷移は

dp′[h′]=∑h≥h′−1dp[h]\mathrm{dp}'[h'] = \sum_{h \ge h' - 1} \mathrm{dp}[h]

なので、後ろからの累積和で O(長さ)O(\text{長さ}) で計算できます。答えは最後の dp\mathrm{dp} の総和です。

各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ mm の列の DP は O(m2)O(m^2) なので、全体で O(n2)O(n^2) です。

Python
from bisect import bisect_left
from itertools import accumulate
MOD = 10**9 + 7
def count(flags):
dp = [1]
for f in flags:
if f:
dp = [0] + dp
else:
s = list(accumulate(reversed(dp)))
s.reverse()
dp = [0] + [v % MOD for v in s]
return sum(dp) % MOD
def solve(n, x):
ans = 1
starts = []
flags = []
for i in range(1, n + 1):
if x[i - 1] == -1:
starts.append(i)
flags.append(False)
continue
l = x[i - 1] + 1
if l > i:
return 0
k = bisect_left(starts, l)
if l < i and (k == len(starts) or starts[k] != l):
return 0
ans = ans * count(flags[k:]) % MOD
del starts[k:]
del flags[k:]
starts.append(l)
flags.append(True)
return ans * count(flags) % MOD
t = int(input())
for _ in range(t):
n = int(input())
x = list(map(int, input().split()))
print(solve(n, x))

starts は列の各要素が元の列のどこから始まるか、flags はその要素が左の子を持たない頂点かどうかです。starts は昇順なので、xi+1x_i + 1 から始まる要素を bisect_left で探しています。

count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。

SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R

長さ nn の数列 aa と整数 L,RL, R が与えられます。連続する部分列のうち、総和が LL 以上 RR 以下のものの個数を求める問題です(n≤105n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、−1014≤L≤R≤1014-10^{14} \le L \le R \le 10^{14})。aia_i は負になることもあります。

累積和を S0=0S_0 = 0、Sj=a1+⋯+ajS_j = a_1 + \cdots + a_j とすると、区間 [i+1,j][i + 1, j] の総和は Sj−SiS_j - S_i です。条件 L≤Sj−Si≤RL \le S_j - S_i \le R を SiS_i について書き直すと

Sj−R≤Si≤Sj−LS_j - R \le S_i \le S_j - L

です。したがって、各 jj について「i<ji < j で SiS_i が [Sj−R,Sj−L][S_j - R, S_j - L] に入るものの個数」を足し合わせれば答えになります。

aia_i が負になることもあるので SS は単調ではなく、しゃくとり法は使えません。そこで j=1,2,…,nj = 1, 2, \ldots, n の順に見ていき、それまでに出てきた SiS_i を、値ごとの個数として管理します。必要な操作は次の 2 つです。

  • SjS_j を 1 個追加する
  • 値が [Sj−R,Sj−L][S_j - R, S_j - L] の範囲にある SiS_i の個数を数える

SS の値は最大 101410^{14} 程度と大きいので、S0,…,SnS_0, \ldots, S_n を座標圧縮して添字にし、区間和を求めるセグメント木(または BIT)で管理します。値の範囲 [Sj−R,Sj−L][S_j - R, S_j - L] は、圧縮後の添字では二分探索で求まります。全体で O(nlog⁡n)O(n \log n) です。

C++(セグメント木)
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
void solve() {
LL(N, L, R);
VL(A, N);
ll t = 0;
sl s;
s.insert(t);
for (ll a : A) {
t += a;
s.insert(t);
}
vl v(all(s));
RSumQ<ll> seg(v.size());
ll ans = 0;
t = 0;
seg.apply(bisect_left(v, t), 1);
for (ll a : A) {
t += a;
ans += seg.prod(bisect_left(v, t - R), bisect_right(v, t - L));
seg.apply(bisect_left(v, t), 1);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

前半では累積和の値を std::set に入れ、ソート済みで重複のない v にしています(座標圧縮)。値 xx の添字は bisect_left(v, x) です。

後半では t が SjS_j で、seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)) が「値が [Sj−R,Sj−L][S_j - R, S_j - L] にある SiS_i の個数」です。数えてから seg.apply(..., 1) で SjS_j を追加するので、i<ji < j のものだけが数えられます。RSumQ は区間和のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

Python(BIT)
from bisect import bisect_left, bisect_right
from itertools import accumulate
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
S = [0, *accumulate(A)]
v = sorted(set(S))
M = len(v)
bit = [0] * (M + 1)
def add(i):
i += 1
while i <= M:
bit[i] += 1
i += i & -i
def count(i):
res = 0
while i:
res += bit[i]
i -= i & -i
return res
ans = 0
add(bisect_left(v, 0))
for t in S[1:]:
ans += count(bisect_right(v, t - L)) - count(bisect_left(v, t - R))
add(bisect_left(v, t))
print(ans)

C++ 版と同じ処理を BIT で書いています。count(i) は添字が ii 未満の個数なので、2 つの差が範囲内の個数になります。

SamCoding Round 7 (Div. 2) F - Subarrays Divisible by K

長さ nn の数列 aa と整数 kk が与えられます。連続する部分列 al,…,ara_l, \ldots, a_r のうち、総和が kk で割り切れるものの個数を求める問題です(n≤105n \le 10^5、k≤109k \le 10^9、0≤ai≤1090 \le a_i \le 10^9)。

累積和を S0=0S_0 = 0、Si=a1+⋯+aiS_i = a_1 + \cdots + a_i とすると、区間 [l,r][l, r] の総和は Sr−Sl−1S_r - S_{l-1} です。これが kk で割り切れるのは

Sr≡Sl−1(modk)S_r \equiv S_{l-1} \pmod{k}

のときです。つまり、0≤i<j≤n0 \le i < j \le n で Si mod kS_i \bmod k と Sj mod kS_j \bmod k が等しい組 (i,j)(i, j) の個数が答えです。

j=0,1,…,nj = 0, 1, \ldots, n の順に見ていき、それまでに出てきた余りの個数を数えておけば、各 jj について「Sj mod kS_j \bmod k と同じ余りの SiS_i が前に何個あったか」がすぐに分かります。全体で O(n)O(n) です。

Python
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
t = 0
C = Counter()
C[0] += 1
ans = 0
for a in A:
t += a
t %= K
ans += C[t]
C[t] += 1
print(ans)

t が累積和を kk で割った余り、C が余りごとの出現回数です。最初に C[0] += 1 で S0=0S_0 = 0 の分を数えておき、各要素を足すたびに同じ余りの個数を答えに加えています。

kk は最大 10910^9 なので、配列ではなく Counter(辞書)で数えています。

ABC478 F - Min-First Search

頂点 1,…,N1, \ldots, N の木 TT について、頂点 11 から始めて「訪問候補の集合 SS から番号が最小の頂点を取り出して訪問し、その未訪問の隣接頂点を SS に加える」ことを繰り返したときの訪問順を f(T)f(T) とします。順列 QQ (Q1=1Q_1 = 1) が与えられるので、f(T)=Qf(T) = Q となる木 TT の個数を 998244353998244353 で割った余りを求める問題です(N≤2×105N \le 2 \times 10^5)。

以下、添字を 00 始まりにして Q0=1Q_0 = 1 とします。

i≥1i \ge 1 について、QiQ_i を SS に加えたのは、QiQ_i より先に訪問された隣接頂点です。木なので、QiQ_i に隣接する頂点のうち QiQ_i より先に訪問されるものはちょうど 1 つで、これを QiQ_i の親 QkQ_k (k<ik < i) と呼ぶことにします。木は「各 i≥1i \ge 1 の親の選び方」と 1 対 1 に対応するので、条件を満たす親の選び方を数えればよいです。

QkQ_k を訪問した時点で QiQ_i が SS に入り、QiQ_i は ii 番目に取り出されるまで SS に残ります。その間に取り出される Qk+1,…,Qi−1Q_{k+1}, \ldots, Q_{i-1} はそのときの SS の最小値なので、すべて QiQ_i より小さくなければなりません。

そこで、QiQ_i より前にある QiQ_i より大きい要素のうち最も後ろのものの位置を pip_i とします(なければ pi=0p_i = 0)。すると親の位置 kk の条件は

pi≤k≤i−1p_i \le k \le i - 1

で、選び方は i−pii - p_i 通りです(QpiQ_{p_i} 自身は大きくても、親として先に訪問されるので構いません)。

逆に、すべての ii についてこの範囲で親を選べば、ii 番目の時点で SS に残っている他の頂点 QmQ_m (m>im > i) は、親が ii より前にあるので条件から Qi<QmQ_i < Q_m となり、QiQ_i が最小として正しく取り出されます。したがって各 ii の選び方は独立で、答えは

∏i=1N−1(i−pi)\prod_{i=1}^{N-1} (i - p_i)

です。

pip_i は「直前にある自分より大きい要素の位置」なので、

  • 区間最大値のセグメント木で min_left を使って二分探索する(O(Nlog⁡N)O(N \log N))
  • 単調スタックの要領で、直前の大きい要素へのポインタをたどる(全体で O(N)O(N))

のどちらでも求められます。

C++(セグメント木)
#include "ou-library/modint.hpp"
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
using mint = modint998244353;
void solve() {
LL(N);
VL(Q, N);
Q--;
mint ans = 1;
RMaxQ<ll> seg(Q);
rep(i, 1, N) {
ll j = seg.min_left(i, [&](ll x) { return x <= Q[i]; });
if (j)
j--;
ans *= i - j;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

min_left(i, x <= Q[i]) で「Ql,…,Qi−1Q_l, \ldots, Q_{i-1} がすべて QiQ_i 以下になる最小の ll」を求め、その 1 つ前が pip_i です。RMaxQ は区間最大値のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

cLay(ポインタをたどる)
#define MD 998244353
ll@N,@Q[N],g[N],p;mint x=1;rep(i,1,N){p=i-1;while(p&&Q[p]<Q[i])p=g[p];g[i]=p;x*=i-p;}wt(x);

g[i] に pip_i を記録しておき、Qi−1Q_{i-1} から始めて自分より小さい間は g をたどることで pip_i を求めています。Q0=1Q_0 = 1 は最小なので、より大きい要素がなければ p=0p = 0 で止まります。