Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <fstream>
- #define pb push_back
- #define mp make_pair
- #define int long long
- #define f first
- using namespace std;
- vector<pair<short, char>> v[32];
- bool is_term[32];
- int dp[65][32][32];
- const int md = 1e9+7;
- signed main() {
- ifstream cin;
- ofstream cout;
- cin.open("numwords.in");
- cout.open("numwords.out");
- int n, m; cin >> n >> m;
- for (int i = 0; i < m; ++i) {
- int a, b; char c;
- cin >> a >> c >> b;
- v[a].pb(mp(b, c));
- }
- int t; cin >> t;
- for (int i = 0; i < t; ++i) {
- int id; cin >> id;
- is_term[id] = 1;
- }
- int k; cin >> k;
- if (!k) {
- cout << (is_term[1] ? 1 : 0);
- return 0;
- }
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= n; ++j)
- for (auto u : v[i])
- if (u.f == j) ++dp[0][i][j];
- for (int q = 1; (1 << q) <= k; ++q)
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= n; ++j) {
- for (int u = 1; u <= n; ++u)
- dp[q][i][j] += (dp[q-1][i][u]*dp[q-1][u][j])%md;
- }
- int ans = 1;
- bool fl = 0;
- for (int l = log2(k)+1; l >= 0; --l) {
- int sum = 0;
- if (k < (1 << l)) continue;
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= n; ++j) {
- if (!fl && i != 1) continue;
- if (k == (1 << l) ? is_term[j] : 1) sum += dp[l][i][j];
- }
- fl = 1;
- sum %= md;
- ans *= sum;
- ans %= md;
- k -= (1 << l);
- }
- cout << (fl ? ans : 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement