Advertisement
Guest User

Untitled

a guest
Oct 16th, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <fstream>
  6.  
  7. #define pb push_back
  8. #define mp make_pair
  9. #define int long long
  10. #define f first
  11.  
  12. using namespace std;
  13.  
  14. vector<pair<short, char>> v[32];
  15. bool is_term[32];
  16. int dp[65][32][32];
  17.  
  18. const int md = 1e9+7;
  19.  
  20. signed main() {
  21. ifstream cin;
  22. ofstream cout;
  23. cin.open("numwords.in");
  24. cout.open("numwords.out");
  25. int n, m; cin >> n >> m;
  26. for (int i = 0; i < m; ++i) {
  27. int a, b; char c;
  28. cin >> a >> c >> b;
  29. v[a].pb(mp(b, c));
  30. }
  31.  
  32. int t; cin >> t;
  33. for (int i = 0; i < t; ++i) {
  34. int id; cin >> id;
  35. is_term[id] = 1;
  36. }
  37.  
  38. int k; cin >> k;
  39. if (!k) {
  40. cout << (is_term[1] ? 1 : 0);
  41. return 0;
  42. }
  43.  
  44. for (int i = 1; i <= n; ++i)
  45. for (int j = 1; j <= n; ++j)
  46. for (auto u : v[i])
  47. if (u.f == j) ++dp[0][i][j];
  48.  
  49. for (int q = 1; (1 << q) <= k; ++q)
  50. for (int i = 1; i <= n; ++i)
  51. for (int j = 1; j <= n; ++j) {
  52. for (int u = 1; u <= n; ++u)
  53. dp[q][i][j] += (dp[q-1][i][u]*dp[q-1][u][j])%md;
  54. }
  55.  
  56. int ans = 1;
  57. bool fl = 0;
  58. for (int l = log2(k)+1; l >= 0; --l) {
  59. int sum = 0;
  60. if (k < (1 << l)) continue;
  61. for (int i = 1; i <= n; ++i)
  62. for (int j = 1; j <= n; ++j) {
  63. if (!fl && i != 1) continue;
  64. if (k == (1 << l) ? is_term[j] : 1) sum += dp[l][i][j];
  65. }
  66. fl = 1;
  67. sum %= md;
  68. ans *= sum;
  69. ans %= md;
  70. k -= (1 << l);
  71. }
  72. cout << (fl ? ans : 0);
  73. return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement