fork(1) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long L;
  6.  
  7. class compare {
  8.   public:
  9.   bool operator() (const pair<int,int> a, const pair<int,int> b) {
  10.     return a.first > b.first;
  11.   }
  12. };
  13.  
  14. const int mod = 1000000007;
  15. const int N = 100004;
  16. const int inf = 1000000000;
  17.  
  18. inline L add(L a, L b, L MOD) {
  19.   L res = a + b;
  20.   while(res >= MOD) {
  21.     res -= MOD;
  22.   }
  23.   return res;
  24. }
  25.  
  26. inline L mul(L a, L b, L MOD) {
  27.   L res = a * b;
  28.   if(res >= MOD) res %= MOD;
  29.   return res;
  30. } 
  31.  
  32. inline L power(L a, L b) {
  33.   L res = 1;
  34.   while(b > 0) {
  35.     if(b & 1) {
  36.       res = mul(res, a, mod);
  37.     }
  38.     a = mul(a, a, mod);
  39.     b /= 2;
  40.   }
  41.   return res;
  42. }
  43.  
  44. int lp[N], a[N];
  45.  
  46. set <pair<int,int>, compare> poss[N];
  47. int posMax[N] = {0};
  48. map <int,int> mp;
  49.  
  50. struct Node {
  51.   Node * l, *r;
  52.   int prod;
  53.   Node(int p = 1) : l(0), r(0), prod(p) {}
  54.   Node(Node* l, Node* r) : l(l), r(r), prod(1) {
  55.     if(l) {
  56.       prod = mul(prod, l->prod, mod);
  57.     }
  58.     if(r) {
  59.       prod = mul(prod, r->prod, mod);
  60.     }
  61.   }
  62. } store[100 * N];
  63. int strCnt = 0;
  64.  
  65. Node* Fun(int val) {
  66.   Node* res = &store[strCnt++];
  67.   assert (strCnt < 100 * N);
  68.   res->l = 0;
  69.   res->r = 0;
  70.   res->prod = val;
  71.   return res;
  72. }
  73.  
  74. Node* Fun1(Node* ll, Node* rr) {
  75.   Node* res = &store[strCnt++];
  76.   assert (strCnt < 100 * N);
  77.   res->prod = 1;
  78.   res->l = ll;
  79.   res->r = rr;
  80.   if (ll) {
  81.     res->prod = mul(res->prod, ll->prod, mod);
  82.   }
  83.   if (rr) {
  84.     res->prod = mul(res->prod, rr->prod, mod);
  85.   }
  86.   return res;
  87. }
  88.  
  89. vector <Node*> head;
  90.  
  91. Node* build(int b, int e) {
  92.   if(b == e) {
  93.     return Fun(1);
  94.   }
  95.   int mid = (b + e)/2;
  96.   return new Node(build(b, mid), build(mid+1, e));
  97. }
  98.  
  99. int query(Node* v, int b, int e, int l, int r) {
  100.   if(b > r || e < l) {
  101.     return 1;
  102.   }
  103. 	if(b >= l && e <= r) {
  104. 	  return v->prod;
  105. 	}
  106. 	int mid = (b + e)/2;
  107. 	return mul(query(v->l, b, mid, l, r), query(v->r, mid+1, e, l, r), mod);
  108. }
  109.  
  110. Node* update(Node* v, int b, int e, int pos, int val) {
  111.   if(b == e) {
  112.     return Fun(val);
  113.   }
  114.   int mid = (b + e)/2;
  115.   if(pos <= mid) {
  116.     return Fun1(update(v->l, b, mid, pos, val), v->r);
  117.   } else {
  118.     return Fun1(v->l, update(v->r, mid+1, e, pos, val));
  119.   }
  120. }
  121.  
  122. int query1(Node* v, int b, int e, int pos) {
  123.   if(b == e) {
  124.     return v->prod;
  125.   }
  126.   int mid = (b + e)/2;
  127.   if(pos <= mid) {
  128.     return query1(v->l, b, mid, pos);
  129.   } else {
  130.     return query1(v->r, mid+1, e, pos);
  131.   }
  132. }
  133.  
  134. void updateMap(int posx, int val) {
  135.   if(!mp.count(posx)) {
  136.     mp[posx] = 1;
  137.   }
  138.   mp[posx] = mul(mp[posx], val, mod);
  139. }
  140.  
  141. int main()
  142. {
  143.   int n, q;
  144.   scanf("%d %d", &n, &q);
  145.  
  146.   assert(1 <= n && n <= 100000);
  147.   assert(1 <= q && q <= 1000000);
  148.  
  149.   fill(lp, lp + N, inf);
  150.   for(L i = 2; i < N; ++i) {
  151.     if(lp[i] == inf) {
  152.       lp[i] = i;
  153.  
  154.       for(L j = i * i; j < N; j += i) {
  155.         lp[j] = min(lp[j], (int)i);
  156.       }
  157.     }
  158.   }
  159.  
  160.   for (int i = 1; i <= n; ++i) {
  161.     scanf("%d", a + i);
  162.     assert (1 <= a[i] && a[i] <= 100000);
  163.   }
  164.  
  165.   int aa, bb, gg, dd;
  166.   scanf("%d %d %d %d", &aa, &bb, &gg, &dd);
  167.   assert (0 <= aa && aa <= 1000000000);
  168.   assert (0 <= bb && bb <= 1000000000);
  169.   assert (0 <= gg && gg <= 1000000000);
  170.   assert (0 <= dd && dd <= 1000000000);
  171.  
  172.   head.resize(N);
  173.   head[0] = build(1, n);
  174.  
  175.   for(int i = 1; i <= n; ++i) {
  176.     L cur = a[i], toAdd = 1;
  177.     mp.clear();
  178.     for(L p = lp[cur]; p * p <= cur; p = lp[cur]) {
  179.       int cont = 0;
  180.       while(cur % p == 0) {
  181.         cur /= p;
  182.         cont++;
  183.       }
  184.  
  185.       int left = cont;
  186.       while(!poss[p - 1].empty() && left > 0) {
  187.         if(left == 0) break;
  188.         if(poss[p - 1].begin()->second <= 0) {
  189.           poss[p - 1].erase(poss[p - 1].begin());
  190.           continue;
  191.         }
  192.         int posx = poss[p - 1].begin()->first;
  193.         int coun = poss[p - 1].begin()->second;
  194.         updateMap(posx, power(p - 1, mod - 2));
  195.         poss[p - 1].erase(poss[p - 1].begin());
  196.         poss[p - 1].insert({posx, coun-1});
  197.         left--;
  198.       }
  199.  
  200.       poss[p - 1].insert({i, cont});
  201.       posMax[p - 1] = max(posMax[p - 1], cont);
  202.       toAdd = mul(toAdd, power(p - 1, cont), mod);
  203.     }
  204.  
  205.     if(cur > 1) {
  206.       L p = cur;
  207.       int cont = 1;
  208.  
  209.       int left = cont;
  210.       while(!poss[p - 1].empty() && left > 0) {
  211.         if(left == 0) break;
  212.         if(poss[p - 1].begin()->second <= 0) {
  213.           poss[p - 1].erase(poss[p - 1].begin());
  214.           continue;
  215.         }
  216.         int posx = poss[p - 1].begin()->first;
  217.         int coun = poss[p - 1].begin()->second;
  218.         updateMap(posx, power(p - 1, mod - 2));
  219.         poss[p - 1].erase(poss[p - 1].begin());
  220.         poss[p - 1].insert({posx, coun-1});
  221.         left--;
  222.       }
  223.  
  224.       poss[p - 1].insert({i, cont});
  225.       posMax[p - 1] = max(posMax[p - 1], cont);
  226.       toAdd = mul(toAdd, power(p - 1, cont), mod);
  227.     }
  228.  
  229.     head[i] = update(head[i - 1], 1, n, i, toAdd);
  230.     if(!mp.empty()) {
  231.       for(pair<int,int> vv : mp) {
  232.         int val = query1(head[i], 1, n, vv.first);
  233.         head[i] = update(head[i], 1, n, vv.first, mul(val, vv.second, mod));
  234.       }
  235.     }
  236.   }
  237.  
  238.   int last = 0;
  239.   for (int i = 1; i <= q; ++i) {
  240.     int l = 1 + add(mul(last, aa, n), mul(bb, i, n), n);
  241.     int r = l + add(mul(last, gg, n - l + 1), mul(dd, i, n - l + 1), n - l + 1);
  242.  
  243.     assert (1 <= l && l <= r && r <= n);
  244.     int ans = query(head[r], 1, n, l, r);
  245.     printf("%d\n", ans);
  246.     last = ans;
  247.   }
  248.   return(0);
  249. }
Runtime error #stdin #stdout #stderr 0.12s 124160KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
prog: prog.cpp:146: int main(): Assertion `1 <= n && n <= 100000' failed.
https://ideone.com/AiBVyc
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!