コンテンツにスキップ

ShareOJ Programming Contest vol.1 E - Solicitation of Murder

サイト
ShareOJ
コンテスト
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