結果
問題 | No.762 PDCAパス |
ユーザー |
![]() |
提出日時 | 2018-12-20 19:34:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 3,086 bytes |
コンパイル時間 | 990 ms |
コンパイル使用メモリ | 109,300 KB |
実行使用メモリ | 12,092 KB |
最終ジャッジ日時 | 2024-09-25 09:10:02 |
合計ジャッジ時間 | 3,889 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
/* ---------- STL Libraries ---------- */// IO library#include <cstdio>#include <fstream>#include <iomanip>#include <ios>#include <iostream>// algorithm library#include <algorithm>#include <cmath>#include <numeric>#include <random>// container library#include <array>#include <bitset>#include <deque>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>/* ---------- Namespace ---------- */using namespace std;/* ---------- Type Abbreviation ---------- */using ll = long long;template <typename T>using PQ = priority_queue<T>;template <typename T>using GPQ = priority_queue<T, vector<T>, greater<T>>;#define mp make_pair#define mt make_tuple/* ---------- conversion ---------- */#define INT(c) static_cast<int>(c)#define CHAR(n) static_cast<char>(n)#define LL(n) static_cast<ll>(n)#define DOUBLE(n) static_cast<double>(n)/* ---------- container ---------- */#define gsort(b, e) sort(b, e, greater<decltype(*b)>())/* ----------- debug ---------- */template <class T>ostream& operator<<(ostream& os, vector<T> v) {os << "[";for (auto vv : v)os << vv << ",";return os << "]";}template <class T>ostream& operator<<(ostream& os, set<T> v) {os << "[";for (auto vv : v)os << vv << ",";return os << "]";}template <class L, class R>ostream& operator<<(ostream& os, pair<L, R> p) {return os << "(" << p.first << "," << p.second << ")";}/* ---------- Constants ---------- */const ll MOD = 1e9 + 7;// const int INF = 1 << 25;// const ll INF = 1LL << 50;// const double PI = acos(-1);// const double EPS = 1e-10;// mt19937 mert(LL(time(0)));/* ---------- Short Functions ---------- */template <typename T>inline T sq(T a) { return a * a; }template <typename T>T gcd(T a, T b) {if (a > b) return gcd(b, a);return a == 0 ? b : gcd(b % a, a);}template <typename T, typename U>T mypow(T b, U n) {if (n == 0) return 1;if (n == 1) return b /* % MOD */;if (n % 2 == 0) {return mypow(b * b /* % MOD */, n / 2);} else {return mypow(b, n - 1) * b /* % MOD */;}}ll pcnt(ll b) {return __builtin_popcountll(b);}/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */const string PDCA = "PDCA";int main() {int N, M;cin >> N >> M;string S;cin >> S;vector<int> path[N];for (int i = 0; i < M; ++i) {int u, v;cin >> u >> v;--u, --v;path[u].push_back(v);path[v].push_back(u);}ll dp[4][N];fill(dp[0], dp[4], 0);for (int v = 0; v < N; ++v) {if (S[v] == PDCA[0]) dp[0][v] = 1;}for (int k = 1; k < 4; ++k) {for (int v = 0; v < N; ++v) {if (S[v] != PDCA[k]) continue;for (int sv : path[v]) {dp[k][v] += dp[k - 1][sv];}dp[k][v] %= MOD;}}ll ans = 0;for (int v = 0; v < N; ++v) {ans += dp[3][v];}cout << ans % MOD << endl;return 0;}