SHARE
TWEET

peti.cpp

a guest Jan 27th, 2019 55 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.  
  5. typedef pair<int, int> pii;
  6. typedef long long ll;
  7. const int mn = 1e5 + 10;
  8. const ll mod = 998244353;
  9. int b[mn], c[mn], n, m;
  10.  
  11. vector<vector<int> > path;
  12. vector<vector<int> > cycle;
  13.  
  14. bool incyc[mn];
  15. pii loc[mn];
  16. bool vis[mn];
  17. bool ts[mn];
  18. int hd;
  19.  
  20. void dfs(int x)
  21. {
  22.     vis[x] = ts[x] = 1;
  23.     if (ts[c[x]])
  24.         hd = c[x], cycle.push_back({});
  25.     else if (!vis[c[x]]) {
  26.         dfs(c[x]);
  27.     }
  28.     if (hd) {
  29.         cycle[cycle.size() - 1].push_back(x);
  30.         loc[x] = { cycle.size() - 1, cycle[cycle.size() - 1].size() - 1 };
  31.         incyc[x] = 1;
  32.     }
  33.     if (hd == 0) {
  34.         if (incyc[c[x]])
  35.             path.push_back({ c[x], x });
  36.         else
  37.             path[loc[c[x]].first].push_back(x);
  38.         loc[x] = { path.size() - 1, path[path.size() - 1].size() - 1 };
  39.     }
  40.     if (x == hd)
  41.         hd = 0;
  42.     ts[x] = 0;
  43. }
  44. int main()
  45. {
  46.     int i;
  47.     scanf("%d%d", &n, &m);
  48.     for (i = 1; i <= m; i++)
  49.         scanf("%d", b + i), c[i] = i;
  50.     for (i = 1; i <= m; i++)
  51.         c[b[i]] = c[i];
  52.     for (i = 1; i <= m; i++)
  53.         c[i]++;
  54.     c[m + 1] = m + 1;
  55.     for (i = 1; i <= m; i++)
  56.         if (!vis[i])
  57.             dfs(i);
  58.     ll C, cur = 1, ans = 0;
  59.     scanf("%lld", &C);
  60.     for (i = 1; i <= n; i++) {
  61.         ll v;
  62.         cur = cur * C % mod;
  63.         int st = 1, rem = min(i, n - m + 1);
  64.         if (i > n - m)
  65.             st = i - (n - m);
  66.         if (incyc[st])
  67.             v = cycle[loc[st].first][(loc[st].second - rem + cycle[loc[st].first].size() * 1000000LL) % cycle[loc[st].first].size()];
  68.         else if (i <= loc[st].second)
  69.             v = path[loc[st].first][loc[st].second - rem];
  70.         else {
  71.             rem -= loc[st].second;
  72.             st = path[loc[st].first][0];
  73.             if (st == m + 1)
  74.                 v = m + rem;
  75.             else
  76.                 v = cycle[loc[st].first][(loc[st].second - rem + cycle[loc[st].first].size() * 1000000LL) % cycle[loc[st].first].size()];
  77.         }
  78.         ans = (ans + (v - 1) * cur) % mod;
  79.     }
  80.     if (ans < 0)
  81.         ans += mod;
  82.     printf("%lld", ans);
  83. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top