問題一覧 > 通常問題

No.329 Surjection

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 48
作問者 : shimomire
お気に入りにしたユーザー ProblemId : 663 / 自分の提出
問題文最終更新日: 2026-06-25 09:46:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2015 (順位表) の他の問題:

Problem Statement

You are given the sizes $w_1,\dots,w_N$ of $N$ distinct sets $A_1,\dots,A_N$ (that is, $w_i = |A_i|$ for $1 \le i \le N$ holds), and
a set $E$ of pairs $(i,j)$ satisfying $1 \le i \le N$, $1 \le j \le N$.
A function $f : A_i \to A_j$ is defined to be "alive" as follows.

  1. If $i = j$, then $f$ is "alive".
  2. If $(i,j) \in E$, then $f$ is "alive".
  3. If $f : A_i \to A_j$ and $g : A_j \to A_k$ are "alive", then the composite function $g \circ f$ of $f$ and $g$ is "alive".
  4. Only functions that can be shown to be "alive" from 1. 2. 3. are "alive" functions.
Output the number of surjective functions among the "alive" functions.

Here, functions that return the same output for every input are considered to be the same function.
(For example, for $A_1 = \{0\}$, the function $f : A_1 \to A_1$ and the function $f \circ f$ return the same output for every input, so they are considered to be the same function.)
Also, all elements of the sets $A_1,\dots,A_N$ are assumed to be distinct.

Input

$N$ $M$
$w_1$ $w_2$ $\dots$ $w_N$
$i_1$ $j_1$
$\vdots$
$i_M$ $j_M$

$N$($1 \le N \le 200$) represents the number of given sets.
$M$($0 \le M \le N^2$) represents the size of the set of pairs $E$.
$w_k$ ($1 \le k \le N$, $1 \le w_k \le 1000$) represents the number of elements of the set $A_k$.
$i_k$, $j_k$ ($1 \le k \le M$, $1 \le i_k \le N$, $1 \le j_k \le N$) represent a pair $(i_k,j_k)$ that is an element of $E$.
The pairs $(i_k,j_k)$ for different $k$ are all distinct.

Output

Output the number of surjective functions among the "alive" functions. Since the answer can be very large, output the remainder when divided by 1000000007($10^9+7$). Print a newline at the end.

Sample

Sample 1
Input
1 0
3
Output
6

If we let the elements be {1,2,3}, there are 6 surjections: $\{1 \mapsto 1,2 \mapsto 2,3 \mapsto 3\}$,$\{1 \mapsto 1,2 \mapsto 3,3 \mapsto 2\}$,$\dots$

Sample 2
Input
3 4
2 1 2
1 2
2 1
2 3
3 2
Output
7

There are $2$ surjections $A_1 \to A_1$.
There is $1$ surjection $A_1 \to A_2$.
There is $1$ surjection $A_2 \to A_2$.
There are $2$ surjections $A_3 \to A_3$.
There is $1$ surjection $A_3 \to A_2$.
In total, there are $7$ surjections.

Note that the functions $A_1 \to A_3$ formed by composing functions $A_1 \to A_2$ and $A_2 \to A_3$ are not surjective.

Sample 3
Input
4 3
1 2 3 4
4 2
2 3
3 1
Output
50

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。