並列二分探索(解説なしバージョン)
並列二分探索、名前からして難しそうな感じがしていたが、特に難しいわけではなかった。
並列二分探索
個人的には並列という名前は正しくない気がします。
普通の二分探索は次の通り。
let mut ng = 0; let mut ok = m; for _ in 0..30 { let med = (ng + ok) / 2; // 何かしらの操作 if (何かしらの条件) { ok = med; } else { ng = med; } }
並列二分探索は次の通り。
let mut ng = vec![0; q]; let mut ok = vec![m; q]; for _ in 0..30 { let mut check: Vec<Vec<usize>> = vec![Vec::new(); m + 1]; // 各 med を取るようなクエリをリストアップしておく for i in 0..q { let med = (ng[i] + ok[i]) / 2; check[med].push(i); } let mut uf = UnionFind::new(n); // 順番に見ていき、 edge_id==med となるようなクエリについて ok と ng を更新する for edge_id in 0..m { uf.unite(a[edge_id], b[edge_id]); for query in check[edge_id].iter() { let from = uf.find(x[*query]); let to = uf.find(y[*query]); let count = if from == to { uf.sizes[from] } else { uf.sizes[from] + uf.sizes[to] }; if count >= z[*query] { ok[*query] = edge_id; } else { ng[*query] = edge_id; } } } }
コード
use std::io; fn main() { let (n, m) = { let v = read_values::<usize>(); (v[0], v[1]) }; let (a, b) = { let mut a = vec![0; m]; let mut b = vec![0; m]; for i in 0..m { let v = read_values::<usize>(); a[i] = v[0] - 1; b[i] = v[1] - 1; } (a, b) }; let q = read_values::<usize>()[0]; let (x, y, z) = { let mut x = vec![0; q]; let mut y = vec![0; q]; let mut z = vec![0; q]; for i in 0..q { let v = read_values::<usize>(); x[i] = v[0] - 1; y[i] = v[1] - 1; z[i] = v[2]; } (x, y, z) }; let mut ng = vec![0; q]; let mut ok = vec![m; q]; for _ in 0..30 { let mut check: Vec<Vec<usize>> = vec![Vec::new(); m + 1]; for i in 0..q { let med = (ng[i] + ok[i]) / 2; check[med].push(i); } let mut uf = UnionFind::new(n); for edge_id in 0..m { uf.unite(a[edge_id], b[edge_id]); for query in check[edge_id].iter() { let from = uf.find(x[*query]); let to = uf.find(y[*query]); let count = if from == to { uf.sizes[from] } else { uf.sizes[from] + uf.sizes[to] }; if count >= z[*query] { ok[*query] = edge_id; } else { ng[*query] = edge_id; } } } } for i in 0..q { println!("{}", ok[i] + 1); } } struct UnionFind { parent: Vec<usize>, sizes: Vec<usize>, size: usize, } impl UnionFind { fn new(n: usize) -> UnionFind { UnionFind { parent: (0..n).map(|i| { i }).collect::<Vec<usize>>(), sizes: vec![1; n], size: n, } } fn find(&mut self, x: usize) -> usize { if x == self.parent[x] { x } else { let px = self.parent[x]; self.parent[x] = self.find(px); self.parent[x] } } fn unite(&mut self, x: usize, y: usize) -> bool { let parent_x = self.find(x); let parent_y = self.find(y); if parent_x == parent_y { return false; } let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] { (parent_y, parent_x) } else { (parent_x, parent_y) }; self.parent[small] = large; self.sizes[large] += self.sizes[small]; self.sizes[small] = 0; self.size -= 1; return true; } } fn read_line() -> String { let stdin = io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf } fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug { read_line() .split(' ') .map(|a| a.trim().parse().unwrap()) .collect() }
ベイエリアでソフトウェアエンジニアとして働いてわかった、たった 1 つのこと
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
CODE FESTIVAL 2017 Final E - Combination Lock
解法
方針としては、
文字列の長さを偶数にする
文字列の長さが奇数だった場合、中央の文字に対する操作が何回行われても結果に影響はないので、中央の文字とそれに対する操作を削除して考えても変わりません。よって、入力を整理して、文字列の長さは必ず偶数であるとして考えます。
中央を覆う区間に対する操作
例えば、長さ 8 の文字列の [1, 5] 文字目に対する操作があった時、回分にするためには 4 文字目と 5 文字目を同じ文字にする必要がありますが、この操作によって 4 文字目と 5 文字目の差は変わらないため、この操作による 4 文字目と 5 文字目への影響は無視できます。よって、長さ 8 の文字列の [1, 5] 文字目に対する操作は [1, 3] 文字目に対する操作と考えることができます。
このように中央を越える区間に対する操作は、中央を挟んだ無視できる区間への影響を無視することで、より小さい区間への操作に置き換えることができます。これによって全ての操作を、中央から見て右側か左側のどちらかに収まるものとして考えることができます。
片側に寄せる
ある区間に対する操作を 26 回行うのと 0 回行うのは同じです。よってある区間に対する操作を 25 回行うのと -1 回行うのは同じことがわかります。中央から見て右側にある区間に対する操作は、中央から見て対称な左側の区間に対する操作に置き換えられます。例えば、長さ 8 の文字列について、 [6, 8] 文字目に対する操作を 1 回行うことは、 [1, 3] 文字目に対する操作を -1 回行うのと同じです。
このことから、全ての区間を左側に集め、左側に対して操作を行うことで右側の文字列を作って行く問題と考えることができます。
区間の整理
片方の端が同じ値である2つの区間に対する各操作は、区間が被らない操作として考えることが出来ます。例えば、区間 [a, b] に対する操作 1 と、区間 [a, b+k] に対する操作 2 があって操作 1 を m 回行って操作 2 を n 回行うのは、区間 [a, b] に対する操作を 2m 回行って、区間 [b+1, b+k] に対する操作を n 回行うのと同じです。
よって上の図のように 4 つの区間がある時、下の図のようにそれぞれが被らない区間の操作に置き換えることができます。
累積和
imos 法
コード
use std::io; use std::cmp; use std::collections::BTreeMap; use std::collections::VecDeque; use std::collections::BTreeSet; fn main() { let s = read_line().trim().to_owned(); let n = s.len(); let methods = read_values::<usize>()[0]; let mut segments = Vec::new(); for _ in 0..methods { let input = read_values::<usize>(); let mut l: usize = input[0] - 1; let mut r: usize = input[1] - 1; let half = n >> 1; if (n & 1) == 1 { // 文字列の長さが奇数の時、中央の文字を削除するために区間を整理する if l == half && r == half { // 中央の 1 文字のみに対する操作は意味がないので無視する continue; } // 中央の文字を削除する分だけ 1 文字分ずらす if half < l { l -= 1; } if half <= r { r -= 1; } } segments.push((l, r)); } // 長さが奇数の時、中央の文字を削除する let s = { let t = s.bytes().map(|c| { c - "a".bytes().next().unwrap() }).collect::<Vec<_>>(); let mut polished = Vec::new(); for i in 0..n { if (n & 1) != 1 || (n >> 1) != i { polished.push(t[i]); } } polished }; // 新しい文字列の長さ let n = s.len(); // 区間の左端をキーにして、左端の値の set を持つ let mut right_map: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new(); for x in segments.iter() { let (l, r) = *x; let half = n >> 1; let (l, r) = if r < half { // 中央から見て左側の区間はそのまま使う (l, r) } else if l >= half { // 中央から見て右側の区間は左側に移す (n - 1 - r, n - 1 - l) } else { // 中央を越える区間を整理する let right_side = r - (half - 1); let left_side = half - l; if right_side > left_side { // 中央から見て右のほうが大きい区間 let tmp_l = half + left_side; (n - 1 - r, n - 1 - tmp_l) } else if right_side == left_side { // 中央から見て対称な区間に対する操作は結果に影響がないので無視する continue; } else { // 中央から見て左のほうが大きい区間 (l, half - 1 - right_side) } }; if !right_map.contains_key(&l) { right_map.insert(l, BTreeSet::new()); } right_map.get_mut(&l).unwrap().insert(r); } // 区間の右端をキーとした map も作る let mut left_map = BTreeMap::new(); for (left, rights) in right_map.iter() { for r in rights.iter() { if !left_map.contains_key(&(r + 1)) { left_map.insert(r + 1, BTreeSet::new()); } left_map.get_mut(&(r + 1)).unwrap().insert(*left); } } // 区間を整理する let mut merged_map = BTreeMap::new(); for left in 0..n { // left を左端に持つ区間がなければスルー if !right_map.contains_key(&left) { continue; } let mut lefts = BTreeSet::new(); let mut queue = VecDeque::new(); queue.push_back(left); let mut right = left; while !queue.is_empty() { let v = queue.pop_front().unwrap(); lefts.insert(v); if let Some(set) = right_map.remove(&v) { for r in set.iter() { queue.push_back(*r + 1); right = cmp::max(right, *r + 1); } } if let Some(set) = left_map.remove(&v) { for l in set.iter() { queue.push_back(*l); } } } lefts.insert(right); let list = lefts.iter().map(|x| x.clone()).collect::<Vec<_>>(); for i in 0..(list.len() - 1) { let cur = list[i]; let next = list[i + 1]; merged_map.insert(cur, next); } } let mut sum = vec![0; n / 2 + 1]; let mut cur = 0; for i in 0..(n / 2) { cur += sum[i]; let from = (s[i] as i64 + cur) % 26; let to = (s[n - 1 - i] as i64) % 26; let add = (to + 26 - from) % 26; if add == 0 { continue; } if !merged_map.contains_key(&i) { println!("NO"); return; } let x = *merged_map.get(&i).unwrap(); cur += add; sum[x] -= add; } println!("YES"); } fn read_line() -> String { let stdin = io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf } fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug { read_line() .split(' ') .map(|a| a.trim().parse().unwrap()) .collect() }
AtCoder Problems を支える技術
はじめに
AtCoder Problems というサービスを作っています。最近作り直しています。
http://beta.kenkoooo.com/atcoder/
これは AtCoder の提出を全部クロールして、一覧で見れるようにしたものです。最近は機能が増えすぎていますが・・・
ソースコードも公開しています。このプログラムの中でどんなことをしているのかを書いていきたいと思います。競技プログラミングはそんなに関係ないです。
スクレイパー
Scala で書いています。ScalaScraper でクロールもスクレイピングもやってくれるので、それに任せています。
やっていることは以下のとおりです。
- コンテスト一覧をクロールして DB に入れる。
- DB のコンテストを順番に見ていき、そのコンテストの問題をクロールして DB に入れる。
- コンテストを順番に見ていき、そのコンテストの提出をクロールして DB に入れる。全てクロールすると多すぎるので、既に DB に入っている提出が出るまで最新の方から見てクロールする。
- クロール漏れするかもしれないので 1 日に 4 回だけ全ての提出をクロールする。
集計
ユーザーが問題を解いた数や、各問題の正解者数、実行速度最速の提出やコード長が最短の提出などを集計しています。これらの値は API でリクエストが来ますが、来るたびに計算していると遅いので予め計算しておきます。やっていることは SQL クエリを投げるだけです。ユーザーの提出をできるだけ早めに反映するため 5 分ごとくらいで実行しています。
API サーバー
フロントエンドからは JSON で出力を返す API を叩いています。API サーバーも Scala で書かれていて、サーバーは Akka HTTP で、SQL 部分は ScalikeJDBC を使って書いています。
可能ならレスポンスを gzip で返したり、ETag を見て変更がなければ 304 を返してキャッシュを使ってもらったりなどの工夫がありますが、このへんは Akka HTTP がよしなにやってくれています。
フロントエンド
フロントエンドは TypeScript と React で書いています。JS 業界は gulp だの bower だの browserify だの webpack だの mocha だの chai だの無限にインストールしなければならないイメージでしたが、TypeScript のチュートリアルどおりにやったところ、トランスパイルは webpack 、テストは jest だけで十分でした。
TypeScript は VSCode でプラグイン無しで快適に書けるのでとても良いです。素の JavaScript を書くことは一生ないでしょう。
得点の予測
AtCoder の rated のコンテストでは各問題に得点が設定されていますが、そうでない問題は rated の問題と違う基準で得点が設定されているので、推定してみることにしました。
AtCoder で 300 問以上解いているユーザーをヘビーユーザーとして、ヘビーユーザーの各問題についての「解けた」「提出したが不正解だった」「提出していない」を特徴量にして、思考停止 XGBoost で predict しました。
AtCoder で問題を解くと、ヘビーユーザーとして特徴量作成に使われたり、各問題の特徴が正確になったりして、反映される予測値も正確になっていくはずなので、みなさん問題を解きましょう。
まとめ
Scala はいい。TypeScript もまあいい。
フィボナッチヒープ
フィボナッチヒープとは
この記事ではヒープは最小値を求めるものとします。
フィボナッチヒープとは、フィボナッチ数の性質をうまく使ってならし計算量で高い性能を持ったヒープです。
ヒープ | フィボナッチヒープ | 二分ヒープ |
---|---|---|
最小値の削除 | ならし O(log n) | O(log n) |
値の追加 | O(1) | O(log n) |
値の追加が非常に多く、最小値の削除が非常に少ない場合は、二分ヒープより速くなることもあるかもしれません。他にもヒープ同士をマージできたり、ヒープ内の値の減少ができたりしますが、この記事では扱いません。すみません。
構造
図は wikipedia からの引用です。
フィボナッチヒープは、下図のようにいくつかのツリーを並べたような構造を持っています。ツリーの各ノードに、ヒープ内の値が入っています。各ツリーでは、上の根に近いほうが小さい値になるようになっています。このとき、ヒープ内の値の最小値は 1 で、実際に最小値のポインタも 1 のノードを指しています。
次に、最小値を削除 (pop) することを考えます。先ほど最小値とされていた 1 のノードが削除され、1 を根としたツリーが分解し、新たに 3, 4, 7 をそれぞれ根とした新しいツリーができます。新しいツリーたちはヒープのツリーのリストに入ります。
今度はツリーのリストを整理します。ツリーを順番に見ていき、以下の操作を施します。
見ているツリーの根の次数を i とする。
- 次数 i のツリーとして登録されているツリーが他になければ、今見ているツリーを次数 i のツリーとして登録する。
- 次数 i のツリーとして登録されているツリーが既にある場合、登録されているツリーの根の値と、今見ているツリーの根の値を比べ、大きい方の根を小さい方の根の下に接続する。この操作で次数 i の根を持ったツリーが 2 つ消え、次数 i+1 を持ったツリーが新たに生成される。
この操作を全て終えると、ヒープ内のツリーの根の次数が全て相異なるようになります。(後述しますが、これは重要なことです)
最後に残っているツリーの根をもう一度全て見て、最小の値を持つ根を最小値として指すようにします。
計算量
ツリーのリストを走査するときにノードを参照する回数は、新たに追加されたノードの数 + 最小値のノードの子ノードの数であるが、新たに追加されたノードの数はノードを追加する計算量に含めるとして、最小値のノードの子ノードの数、すなわち最小値のノードの次数が となることを示す。
補題 1
あるノード x について、 x の次数を と表す。 として、x の k 個の子ノードをそれぞれ として、この順番で x の子として接続されたとする。この時 かつ である。
証明
は自明。
に対して を x に接続する時、 は既に x の子ノードとして接続されている。つまり が成り立っている。
ここで が x に子として接続されるためには が成り立っていなければならない。よって が成り立つ。
値が減少するバージョンではまだやることがありますが、とりあえずこれで が成り立ったのでこのまま行きます。
実装
import java.util.ArrayList; import java.util.List; public class LongFibonacciHeap { class Node { long key = -1; int degree = 0; Node p = null; Node right = null; Node left = null; List<Node> children = new ArrayList<>(); boolean mark = false; } private Node min = null; private int size = 0; public void insert(Node x) { if (min == null) { min = x; x.right = x; x.left = x; } else { addRoot(x); if (x.key < min.key) { min = x; } } size++; } /** * Add node x to linked root list * * @param x node to add */ private void addRoot(Node x) { if (min == null) { min = x; min.right = x; min.left = x; return; } Node l = min.left; l.right = x; min.left = x; x.right = min; x.left = l; } /** * Remove node x from linked root list * * @param x node to remove */ private void removeRoot(Node x) { Node r = x.right; Node l = x.left; r.left = l; l.right = r; } /** * merge h1 and h2 to generate new one * * @param h1 heap1 to merge * @param h2 heap2 to merge * @return merged heap */ public static LongFibonacciHeap unite(LongFibonacciHeap h1, LongFibonacciHeap h2) { LongFibonacciHeap h = new LongFibonacciHeap(); h.min = h1.min; if ((h1.min == null) || (h2.min != null && h2.min.key < h1.min.key)) { h.min = h2.min; } // link h1's root list & h2's root list if (h1.min != null && h2.min != null) { Node n1 = h1.min; Node n2 = h2.min; Node n1l = n1.left; Node n2r = n2.right; n1.left = n2; n2.right = n1; n2r.left = n1l; n1l.right = n2r; } h.size = h1.size + h2.size; return h; } public Node extractMinNode() { Node z = min; if (z == null) { return null; } for (Node child : z.children) { addRoot(child); child.p = null; } removeRoot(z); if (z == z.right) { min = null; } else { min = z.right; consolidate(); } size--; return z; } public int size() { return size; } private void consolidate() { //list up rooted nodes ArrayList<Node> rootList = new ArrayList<>(); rootList.add(min); while (rootList.get(rootList.size() - 1).right != rootList.get(0)) { Node lastRight = rootList.get(rootList.size() - 1).right; rootList.add(lastRight); } Node[] rootOfDegree = new Node[size + 1]; for (Node parent : rootList) { int d = parent.degree; while (rootOfDegree[d] != null) { Node child = rootOfDegree[d]; if (parent.key > child.key) { Node t = parent; parent = child; child = t; } link(child, parent); rootOfDegree[d] = null; d++; } rootOfDegree[d] = parent; } min = null; for (Node node : rootOfDegree) { if (node == null) { continue; } if (min == null) { node.right = node; node.left = node; min = node; } else { addRoot(node); if (node.key < min.key) { min = node; } } } } private void link(Node child, Node parent) { removeRoot(child); parent.degree++; parent.children.add(child); child.p = parent; child.mark = false; } public void insert(long key) { Node x = new Node(); x.key = key; insert(x); } }
フィボナッチヒープを使ってダイクストラやってみた
問題
コード
use std::cmp; use std::collections::HashMap; const INF: u64 = std::u64::MAX / 2; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let m: usize = sc.read(); let s = sc.read::<usize>() - 1; let t = sc.read::<usize>() - 1; let mut graph = vec![vec![]; n]; for _ in 0..m { let a = sc.read::<usize>() - 1; let b = sc.read::<usize>() - 1; let c = sc.read::<u64>(); graph[a].push((b, c)); graph[b].push((a, c)); } let dist1 = dijkstra(s, &graph); let dist2 = dijkstra(t, &graph); for i in 0..n { if dist1[i] == dist2[i] && dist1[i] != INF { println!("{}", i + 1); return; } } println!("-1"); } fn dijkstra(s: usize, graph: &Vec<Vec<(usize, u64)>>) -> Vec<u64> { let n = graph.len(); let mut dist = vec![INF; n]; dist[s] = 0; let mut heap = FibonacciHeap::new(cmp::min); heap.push((0, s)); while let Some((_, v)) = heap.pop() { for &(next, cost) in graph[v].iter() { if dist[next] > dist[v] + cost { dist[next] = dist[v] + cost; heap.push((dist[next], next)); } } } dist } fn store_to_map<T, F>(map: &mut HashMap<usize, Node<T>>, mut node: Node<T>, ordering: F) where T: Copy + PartialEq, F: Fn(T, T) -> T, { let d = node.children.len(); match map.remove(&d) { Some(mut other) => { let node = if (ordering)(node.key, other.key) == node.key { node.children.push(other); node } else { other.children.push(node); other }; store_to_map(map, node, ordering); } None => { map.insert(d, node); } } } pub struct FibonacciHeap<T, F> { pub nodes: Vec<Node<T>>, min_index: usize, ordering: F, } impl<T, F> FibonacciHeap<T, F> where T: Copy + PartialEq, F: Fn(T, T) -> T + Copy, { pub fn new(ordering: F) -> FibonacciHeap<T, F> { FibonacciHeap { nodes: Vec::new(), min_index: 0, ordering: ordering, } } pub fn push(&mut self, x: T) { let node = Node::new(x); self.nodes.push(node); let cur_min = self.nodes[self.min_index].key; if (self.ordering)(cur_min, x) == x { self.min_index = self.nodes.len() - 1; } } pub fn pop(&mut self) -> Option<T> { let mut map: HashMap<usize, Node<T>> = HashMap::new(); let mut popped = None; let mut nodes = Vec::new(); std::mem::swap(&mut self.nodes, &mut nodes); for (i, node) in nodes.into_iter().enumerate() { if i == self.min_index { popped = Some(node.key); for node in node.children.into_iter() { store_to_map(&mut map, node, self.ordering); } } else { store_to_map(&mut map, node, self.ordering); } } self.nodes = map.into_iter().map(|(_, node)| node).collect(); if !self.nodes.is_empty() { let mut min = self.nodes[0].key; for i in 0..self.nodes.len() { if (self.ordering)(min, self.nodes[i].key) == self.nodes[i].key { min = self.nodes[i].key; } } self.min_index = self .nodes .iter() .enumerate() .find(|&(_, node)| node.key == min) .unwrap() .0; } else { self.min_index = 0; } popped } } #[derive(Debug)] pub struct Node<T> { pub key: T, pub children: Vec<Node<T>>, } impl<T> Node<T> { fn new(x: T) -> Node<T> { Node { key: x, children: Vec::new(), } } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
リクルートコミュニケーションズを退職しました
豆知識
この記事のタイトルでググると、まともな記事が出てきます。
退職しました
20 ヶ月ほど勤務したリクルートコミュニケーションズ (RCO) を退職しました。RCO ではウェブ広告リアルタイム配信チームで、主に高速化を頑張りました。かなり面白かったです。また、 2 年目に並行して始めた、流通を線形計画問題に落とし込んで解くという仕事も割と面白かったです。
自由な雰囲気で、給料も良く、良い同僚に恵まれもしましたが、若いうちに色んな環境を経験しておきたかったのと、上司いわく「うちは出入り自由なんで」とのことだったので、気楽な気持ちで退職しました。
これが罠で、12月末で退職すれば良かったものを、何故かうっかり 11 月末で退職してしまったがために、12 月のボーナスを貰い損ねてしまいました。さすがに適当に退職し過ぎた・・・
まとめ
積極的な理由がないなら、賞与の後に退職すると良い。
AOJ 2829 Room Assignment
解法
JAG の wiki に分かりやすい解説があります。
2017/Practice/模擬国内予選/講評 - ACM-ICPC Japanese Alumni Group
場合分けとしては以下の 3 つです
- 長さ 3 以上の閉路が存在する場合は 0
- 閉路を潰した時に、全てのツリーの葉の数が 2 以下でなければ 0
- 長さ 3 以上の弱連結成分が存在しない時
- それ以外
コード
import java.util.Scanner import scala.collection.mutable.ArrayBuffer object Main { private val Mod = (1e9 + 7).toInt // 階乗を前計算しておく private val Fact = { var cur = 1L for (i <- 0 to 200000) yield { if (i == 0) { 1 } else { cur = (cur * i) % Mod cur } } } // 2 の累乗を前計算しておく private val Pow = { val pow = new Array[Int](200000) pow(0) = 1 for (i <- 1 until pow.length) pow(i) = pow(i - 1) * 2 % Mod pow } def main(args: Array[String]): Unit = { val in = new Scanner(System.in) while (true) { val n = in.nextInt() if (n == 0) { return } val a = for (_ <- 0 until n) yield { in.nextInt() - 1 } println(solve(a.toArray)) } } // 長さ 3 以上の閉路が存在しないことを確認する def cycleCheck(graph: IndexedSeq[Seq[Int]]): Boolean = { val cmp = StronglyConnectedComponents.decompose(graph) var map = Map[Int, Int]() cmp.foreach { c => map += (c -> (map.getOrElse(c, 0) + 1)) } map.values.forall(count => count <= 2) } // 全ての弱連結成分がパスが閉路を潰すとパスになることを確認する def pathCheck(graph: IndexedSeq[Seq[Int]]): Boolean = { val uf = new UnionFind(graph.size) for { i <- graph.indices j <- graph(i) } uf.unite(i, j) var map = Map[Int, Int]() for { i <- graph.indices if graph(i).isEmpty } { val count = map.getOrElse(uf.find(i), 0) map += (uf.find(i) -> (count + 1)) } map.values.forall(count => count <= 2) } // 要素数 2 の弱連結成分の数と、要素数 3 以上の弱連結成分の数を算出する def getSize(array: Array[Int]): (Int, Int) = { val N = array.length val uf = new UnionFind(N) for (i <- array.indices) uf.unite(i, array(i)) val sizes = for { i <- 0 until N if i == 0 || !uf.isSame(i, 0) } yield { if (i == 0) { uf.partialSizeOf(i) } else { val s = uf.partialSizeOf(i) uf.unite(i, 0) s } } var three = 0 var two = 0 sizes.foreach(size => if (size == 2) { two += 1 } else { three += 1 }) (two, three) } def solve(parent: Array[Int]): Int = { val n = parent.length val combination = new Combination(n + 1, Mod) val graph = parent.indices.map(i => new ArrayBuffer[Int]()) parent.indices.foreach(i => graph(parent(i)).append(i)) if (cycleCheck(graph) && pathCheck(graph)) { val (two, three) = getSize(parent) if (three == 0) { // 長さ 3 以上の弱連結成分が存在しないとき var cur: Long = ((two + 2) / 2) % Mod cur = cur * Pow(two) % Mod cur = cur * Fact(two) % Mod cur.toInt } else { var ans = 0L for (i <- 0 to math.min(two + three - 2, two)) { var cur = combination.get(two + three - i - 2, two - i).toLong cur = cur * Fact(two) % Mod cur = cur * Fact(three) % Mod cur = cur * Pow(two + three) % Mod cur = cur * (two + three - i - 1) % Mod cur = cur * ((i + 2) / 2) % Mod ans = (ans + cur) % Mod } for (i <- 0 to math.min(two + three - 1, two)) { var cur = combination.get(two + three - i - 1, two - i).toLong cur = cur * Fact(two) % Mod cur = cur * Fact(three) % Mod cur = cur * Pow(two + three) % Mod cur = cur * ((i + 2) / 2) % Mod ans = (ans + cur * 2) % Mod } ans.toInt } } else { 0 } } class UnionFind(n: Int) { private val parent = (0 until n).toArray private val sizes = Array.fill[Int](n)(1) private var _size = n def find(x: Int): Int = { if (x == parent(x)) { x } else { parent(x) = find(parent(x)) parent(x) } } def unite(a: Int, b: Int): Boolean = { val fa = find(a) val fb = find(b) if (fa == fb) { false } else { val (x, y) = if (sizes(fa) >= sizes(fb)) { (fa, fb) } else { (fb, fa) } parent(y) = x sizes(x) += sizes(y) sizes(y) = 0 _size -= 1 true } } def isSame(x: Int, y: Int): Boolean = find(x) == find(y) def partialSizeOf(x: Int): Int = sizes(find(x)) def size(): Int = _size } class Combination(max: Int, mod: Int) { private val inv = new Array[Long](max + 1) private val fact = new Array[Long](max + 1) private val invFact = new Array[Long](max + 1) inv(1) = 1 for (i <- 2 to max) inv(i) = inv(mod % i) * (mod - mod / i) % mod fact(0) = 1 invFact(0) = 1 for (i <- 1 to max) fact(i) = (fact(i - 1) * i) % mod for (i <- 1 to max) invFact(i) = (invFact(i - 1) * inv(i)) % mod /** * get nCm */ def get(n: Int, m: Int): Int = { if (n < m) { 0 } else fact(n) * invFact(m) % mod * invFact(n - m) % mod }.toInt } object StronglyConnectedComponents { def decompose(graph: IndexedSeq[Seq[Int]]): Array[Int] = { val vs = new ArrayBuffer[Int]() val V = graph.size val cmp = new Array[Int](V) val rg = graph.indices.map(_ => new ArrayBuffer[Int]()) for { from <- graph.indices to <- graph(from) } rg(to).append(from) var used = Array.fill[Boolean](V)(false) var stack = List[Int]() val added = Array.fill[Boolean](V)(false) for { i <- used.indices if !used(i) } { stack = i :: stack while (stack.nonEmpty) { val v = stack.head used(v) = true var pushed = false for { u <- graph(v).reverse if !used(u) } { stack = u :: stack pushed = true } if (!pushed) { stack = stack.tail if (!added(v)) { vs.append(v) added(v) = true } } } } used = Array.fill[Boolean](V)(false) var k = 0 for { i <- vs.reverse if !used(i) } { stack = i :: stack used(i) = true cmp(i) = k while (stack.nonEmpty) { val v = stack.head var pushed = false for { u <- rg(v) if !used(u) } { used(u) = true cmp(u) = k stack = u :: stack pushed = true } if (!pushed) { stack = stack.tail } } k += 1 } cmp } } }