No.762 PDCAパス
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 163
作問者 :
mai
/ テスター :
matsu7874
タグ : / 解いたユーザー数 163
作問者 :

問題文最終更新日: 2025-02-10 00:15:56
問題文
個の頂点と個の無向辺から構成されるグラフが与えられます.
番目の頂点には,P
,D
,C
,A
のいずれかの文字が書き込まれています.
番目の辺は,番目の頂点と,番目の頂点に接続しています.
始点と終点が異なり,どの頂点も高々一度しか通らない,ある頂点からある頂点への行き方をパスと呼びます.
長さ3のパスとは,3つの辺と4つの頂点によって構成されているパスのことです.
長さ3のパスについて,端から端へ頂点を辿るとPDCA
と読むことができる時,PDCAパスと呼ぶことにします.
グラフを構成する長さ3のパスの中で,PDCAパスは幾つ存在するでしょうか?で割った余りを求めてください.
入力
N M S u_1 v_1 ... u_M v_M
多重辺・自己ループ辺が存在するグラフは与えられない.
文字列 を構成する文字はP
,D
,C
,A
のいずれかである
の 文字目は,頂点番号 にその文字が書き込まれていることを示す.
出力
PDCAパスの個数を1000000007
で割った余りを出力してください.
最後に改行してください。
サンプル
サンプル1
入力
7 11 PAAPCDD 1 3 1 5 1 6 2 5 2 6 3 5 5 6 4 5 5 7 4 7 2 7
出力
4
1,6,5,2
,1,6,5,3
,4,7,5,2
,4,7,5,3
の4通りがあります.
サンプル2
入力
6 3 ACPPPD 1 2 3 4 4 5
出力
0
グラフは連結とは限りませんし,PDCAパスが存在しないかもしれません.
サンプル3
入力
11 11 AAACCCDDPPP 1 4 1 5 2 5 4 7 5 7 7 9 7 10 2 4 3 6 6 8 8 11
出力
9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。