競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 114B

 

ARC114B

f の定義域を T に制限したとき 値域が T になり単射となる T を数え上げる． つまり， f の値域と定義域を T に制限したときに 全単射となる T を数え上げる問題．

f は functional graph と呼ばれるグラフになる． 連結成分毎にサイクルが一つあり，そこに枝が何本か生えた形． 枝からサイクルに向かっていく．
f : T \rightarrow T が全単射になって欲しいので， 枝の部分があってはならない． また， Im(f) \subset T であることから，サイクルの一部分だけ T にとることは出来ない． つまり， T の元は，いくつかのサイクルの和集合で表せる必要がある． 逆に，これが十分であることも分かる．

したがって，連結成分の個数が答え． Union-find でも求まるが，今回はDFSで求めた． DFSで計算するときは，頂点に3つの値のどれかを割り振りながら遷移する．

  • 0 : まだ訪れてない，
  • 1: 訪れたが，その点を始点とするDFSは，まだ完了してない，
  • 2: 訪れて，その点を始点とするDFSが完了している．

DFSから戻るときに 2 に書き換える． また，その点を始点とするDFSが完了したときに，DFSでtrueを返す様にして区別する．
この方法は，DFSを用いてサイクル検出するときにも使える．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {
  ll n;
  cin >> n;
  vvll to(n);
  vll a(n); rep(i,n) { cin >> a[i]; a[i]--; to[i].emplace_back(a[i]); }

  vll v(n);
  ll cnt = 0;
  auto dfs = [&](auto f, ll cu, ll pa) -> bool {
    if(v[cu] == 1){
      cnt++;
      v[cu] = 2;
      return true;
    }
    if(v[cu] == 2){
      return true;
    }
    v[cu] = 1;

    bool flg = false;
    fore(ne, to[cu]) {//  if(ne!=pa){ // ne != pa をつけると，長さ2のサイクルでWA
      if(f(f, ne, cu)){
        v[cu] = 2;
        flg = true;
      }
    }
    return flg;
  };
 
  rep(i,n) if(v[i] == 0){
    dfs(dfs, i, -1);
  }

  cout << (mint(2).pow(cnt) - 1).val() << endl;

  return 0;
}