Advertisement
a_chn

Untitled

Jul 27th, 2024
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. using namespace std;
  5.  
  6. #define io ios_base::sync_with_stdio(false); cin.tie(NULL);
  7.  
  8. typedef long long ll;
  9.  
  10. ll mod = 1e9 + 7;
  11.  
  12. ll modpow(ll b, ll e) {
  13.     b %= mod; ll r {1};
  14.     while (e > 0) {
  15.         if (e % 2 == 1) r = r * b % mod;
  16.  
  17.         b = b * b % mod;
  18.         e /= 2;
  19.     }
  20.  
  21.     return r;
  22. }
  23.  
  24. int main() {
  25.     io freopen("poetry.in", "r", stdin); freopen("poetry.out", "w", stdout);
  26.  
  27.     ll n {}, m {}, k {}; cin >> n >> m >> k;
  28.  
  29.     vector<pair<ll, ll>> words (n); for (ll i {0}; i < n; ++i) {
  30.         cin >> words[i].first >> words[i].second; --words[i].second;
  31.     }
  32.     vector<ll> scheme (26); for (ll i {0}; i < m; ++i) {
  33.         char r {}; cin >> r; ++scheme[r - 'A'];
  34.     }
  35.  
  36.     vector<ll> dp (k + 1);
  37.     dp[0] = 1;
  38.     for (ll i {0}; i <= k; ++i) {
  39.         if (!dp[i]) continue;
  40.  
  41.         for (auto word : words) {
  42.             if (word.first + i > k) continue;
  43.  
  44.             dp[i] %= mod; dp[word.first + i] += dp[i]; dp[word.first + i] %= mod;
  45.         }
  46.     }
  47.  
  48.     vector<ll> c (n); for (auto word: words) {
  49.         dp[k - word.first] %= mod; c[word.second] += dp[k - word.first]; c[word.second] %= mod;
  50.     }
  51.  
  52.     ll poems {1};
  53.     for (ll i {0}; i < 26; ++i) {
  54.         if (!scheme[i]) continue;
  55.  
  56.         ll p {0};
  57.         for (ll c_ : c) {
  58.             if (!c_) continue;
  59.  
  60.             p += modpow(c_ , scheme[i]); p %= mod;
  61.         }
  62.  
  63.         poems *= p; poems %= mod;
  64.     }
  65.  
  66.     cout << poems % mod;
  67.  
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement