Fshl0

Cow Poetry

Jun 13th, 2021
526
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const int MAXN = 5e3 + 9;
  7. const int MAXM = 1e5 + 9;
  8. const int MAXS = 5e3 + 9;
  9.  
  10. const ll MOD = 1000000007;
  11.  
  12. ll bp (ll a, ll b) {
  13.     if (b == 0)
  14.         return 1;
  15.     ll tmp = bp (a, b / 2);
  16.     if (b & 1)
  17.         return (((tmp * tmp) % MOD) * a) % MOD;
  18.     return (tmp * tmp) % MOD;
  19. }
  20.  
  21. ll dp[MAXS], r[MAXN];                        
  22. unordered_map <char, int> umap;
  23. pair <int, int> words[MAXN];
  24.  
  25. int main(){
  26.     freopen ("poetry.in", "r", stdin);
  27.     freopen ("poetry.out", "w", stdout);
  28.     int n, m, s;
  29.     cin >> n >> m >> s;
  30.     for (int i = 0; i < n; i++)
  31.         cin >> words[i].first >> words[i].second;
  32.     for (int i = 0; i < m; i++) {
  33.         char c;
  34.         cin >> c;
  35.         umap[c]++;
  36.     }
  37.     dp[0] = 1;
  38.     for (int i = 0; i <= s; i++) {
  39.         for (int j = 0; j < n; j++) {
  40.             if (words[j].first + i > s)
  41.                 continue;
  42.             if (words[j].first + i == s)
  43.                 r[words[j].second] = (r[words[j].second] + dp[i] + MOD) % MOD;
  44.             else dp[words[j].first + i] = (dp[words[j].first + i] + dp[i] + MOD) % MOD;
  45.         }
  46.     }
  47.     long long answer = 1;
  48.     for (auto a: umap) {
  49.         int freq = a.second;
  50.         long long sum = 0;
  51.         for (int k = 0; k <= n; k++) {
  52.             if (r[k] == 0)
  53.                 continue;
  54.             sum = (sum + bp (r[k], freq) + MOD) % MOD;
  55.         }
  56.         answer = (answer * sum + MOD) % MOD;
  57.     }
  58.     cout << answer % MOD << "\n";
  59.     return 0;
  60. }
  61.  
RAW Paste Data