Advertisement
mzh_pb

Untitled

Dec 8th, 2023
919
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #define int int64_t
  5.  
  6. #define rng(i, a, b) for (int i = a; i < b; i++)
  7. #define rep(i, b) rng(i, 0, b)
  8. #define gnr(i, a, b) for (int i = b - 1; i >= a; i--)
  9. #define per(i, b) gnr(i, 0, b)
  10.  
  11. #define all(x) begin(x), end(x)
  12. #define sz(x) int(size(x))
  13.  
  14. #define pb push_back
  15. #define eb emplace_back
  16. #define lb lower_bound
  17. #define ub upper_bound
  18.  
  19. #define f first
  20. #define s second
  21.  
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24.  
  25. constexpr int MOD = 1e9 + 7; // 998244353
  26.  
  27. struct Mint {
  28.     int v;
  29.  
  30.     Mint() : v(0) {}
  31.     Mint(int64_t _v) {
  32.         v = (-MOD < _v && _v < MOD ? _v : _v % MOD);
  33.         if (v < 0) {
  34.             v += MOD;
  35.         }
  36.     };
  37.  
  38.     Mint operator+(Mint b) { return Mint(v + b.v); }
  39.     Mint operator-(Mint b) { return Mint(v - b.v); }
  40.     Mint operator*(Mint b) { return Mint(1ll * v * b.v); }
  41.     Mint operator/(Mint b) { return Mint(1ll * v * b.inv().v); }
  42.  
  43.     Mint pow(int e) {
  44.         Mint b = *this;
  45.         Mint ret = 1;
  46.         while (e != 0) {
  47.             if (e & 1) {
  48.                 ret = ret * b;
  49.             }
  50.             b = b * b;
  51.             e >>= 1;
  52.         }
  53.         return ret;
  54.     }
  55.  
  56.     Mint inv() {
  57.         return pow(MOD - 2);
  58.     }
  59. };
  60.  
  61. void solve() {
  62.     int n, m, k;
  63.     cin >> n >> m >> k;
  64.  
  65.     vector<pair<int, int>> words(n);
  66.     for (auto &[f, s] : words) {
  67.         cin >> f >> s;
  68.         s--;
  69.     }
  70.  
  71.     vector<Mint> dp(k + 1); // dp[i] = ways to form a prefix of i syllables
  72.     dp[0] = 1;
  73.     rep(i, k) {
  74.         for (auto [len, _] : words) {
  75.             if (i + len <= k) {
  76.                 dp[i + len] = dp[i + len] + dp[i];
  77.             }
  78.         }
  79.     }
  80.  
  81.     vector<Mint> lines(n); // lines[i] = ways to form a line with end class i
  82.     for (auto [len, cla] : words) {
  83.         lines[cla] = lines[cla] + dp[k - len];
  84.     }
  85.  
  86.     vector<int> cnt(26);
  87.     rep(i, m) {
  88.         char c;
  89.         cin >> c;
  90.         cnt[c - 'A']++;
  91.     }
  92.  
  93.     Mint ans = 1;
  94.     rep(i, 26) {
  95.         if (cnt[i] > 0) {
  96.             Mint cur = 0;
  97.             rep(j, n) {
  98.                 cur = cur + lines[j].pow(cnt[i]);
  99.             }
  100.             ans = ans * cur;
  101.         }
  102.     }
  103.     cout << ans.v << '\n';
  104. }
  105.  
  106. int32_t main() {
  107. #ifndef LOCAL
  108.     freopen("poetry.in", "r", stdin);
  109.     freopen("poetry.out", "w", stdout);
  110. #endif
  111.     ios::sync_with_stdio(false);
  112.     cin.tie(nullptr);
  113.  
  114.     int tc = 1;
  115.     // cin >> tc;
  116.     while (tc--) {
  117.         solve();
  118.     }
  119.  
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement