API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2020
119
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.50 KB | None | 0 0
raw download clone embed print report
  1. // Discrete log
  2.  
  3. int solve (int a, int b, int m) {
  4. int n = (int) sqrt (m + .0) + 1;
  5.  
  6. int an = 1;
  7. for (int i=0; i<n; ++i)
  8. an = (an * a) % m;
  9.  
  10. map<int,int> vals;
  11. for (int i=1, cur=an; i<=n; ++i) {
  12. if (!vals.count(cur))
  13. vals[cur] = i;
  14. cur = (cur * an) % m;
  15. }
  16.  
  17. for (int i=0, cur=b; i<=n; ++i) {
  18. if (vals.count(cur)) {
  19. int ans = vals[cur] * n - i;
  20. if (ans < m)
  21. return ans;
  22. }
  23. cur = (cur * a) % m;
  24. }
  25. return -1;
  26. }
  27.  
  28. /*
  29.  
  30. Пусть дан граф G с n вершинами. Построим соответствующий ему двудольный граф H стандартным образом, т.е.: в каждой доле графа H будет по n вершин, обозначим их через a_i и b_i соответственно. Тогда для каждого ребра (i, j) исходного графа G проведём соответствующее ребро (a_i, b_j).
  31. */
  32.  
  33. /*
  34. Формула Кэли
  35. s1 * s2 ... * sk * n ^ (k - 2)
  36. */
  37.  
  38.  
  39. template<class T> struct MinDeque {
  40. int lo = 0, hi = -1;
  41. deque<pair<T,int>> d;
  42. int size() { return hi-lo+1; }
  43. void push(T x) { // add to back
  44. while (sz(d) && d.back().f >= x) d.pop_back();
  45. d.pb({x,++hi});
  46. }
  47. void pop() { // delete from front
  48. assert(size());
  49. if (d.front().s == lo++) d.pop_front();
  50. }
  51. T mn() { return size() ? d.front().f : MOD; }
  52. // change MOD based on T
  53. };
  54.  
  55.  
  56.  
  57. template<int SZ> struct Wavelet {
  58. vi nexl[SZ], nexr[SZ];
  59. void build(vi a, int ind = 1, int L = 0, int R = SZ-1) {
  60. if (L == R) return;
  61. nexl[ind] = nexr[ind] = {0};
  62. vi A[2]; int M = (L+R)/2;
  63. trav(t,a) {
  64. A[t>M].pb(t);
  65. nexl[ind].pb(sz(A[0])), nexr[ind].pb(sz(A[1]));
  66. }
  67. build(A[0],2*ind,L,M), build(A[1],2*ind+1,M+1,R);
  68. }
  69. int query(int lo,int hi,int k,int ind=1,int L=0,int R=SZ-1) {
  70. if (L == R) return L;
  71. int M = (L+R)/2, t = nexl[ind][hi]-nexl[ind][lo];
  72. if (t >= k) return query(nexl[ind][lo],
  73. nexl[ind][hi],k,2*ind,L,M);
  74. return query(nexr[ind][lo],
  75. nexr[ind][hi],k-t,2*ind+1,M+1,R);
  76. }
  77. };
  78.  
  79.  
  80.  
  81. template<class T, int SZ> struct BITrange {
  82. BIT<T,SZ> bit[2]; // piecewise linear functions
  83. // let cum[x] = sum_{i=1}^{x}a[i]
  84. void upd(int hi, T val) { // add val to a[1..hi]
  85. // if x <= hi, cum[x] += val*x
  86. bit[1].upd(1,val), bit[1].upd(hi+1,-val);
  87. // if x > hi, cum[x] += val*hi
  88. bit[0].upd(hi+1,hi*val);
  89. }
  90. void upd(int lo, int hi, T val) {
  91. upd(lo-1,-val), upd(hi,val); }
  92. T sum(int x) { return bit[1].sum(x)*x+bit[0].sum(x); }
  93. T query(int x, int y) { return sum(y)-sum(x-1); }
  94. };
  95.  
  96. /**
  97. * Description: Supports modifications in the form \texttt{ckmin(a\_i,t)}
  98. * for all $l\le i\le r$, range max and sum queries. SZ should be a power of 2.
  99. * Time: O(\log N)
  100. * Source: http://codeforces.com/blog/entry/57319
  101. * Verification: http://acm.hdu.edu.cn/showproblem.php?pid=5306
  102. */
  103.  
  104. template<int SZ> struct SegTreeBeats {
  105. int N, mx[2*SZ][2], maxCnt[2*SZ];
  106. ll sum[2*SZ];
  107. void pull(int ind) {
  108. F0R(i,2) mx[ind][i] = max(mx[2*ind][i],mx[2*ind+1][i]);
  109. maxCnt[ind] = 0;
  110. F0R(i,2) {
  111. if (mx[2*ind+i][0] == mx[ind][0])
  112. maxCnt[ind] += maxCnt[2*ind+i];
  113. else ckmax(mx[ind][1],mx[2*ind+i][0]);
  114. }
  115. sum[ind] = sum[2*ind]+sum[2*ind+1];
  116. }
  117. void build(vi& a, int ind = 1, int L = 0, int R = -1) {
  118. if (R == -1) { R = (N = sz(a))-1; }
  119. if (L == R) {
  120. mx[ind][0] = sum[ind] = a[L];
  121. maxCnt[ind] = 1; mx[ind][1] = -1;
  122. return;
  123. }
  124. int M = (L+R)/2;
  125. build(a,2*ind,L,M); build(a,2*ind+1,M+1,R); pull(ind);
  126. }
  127. void push(int ind, int L, int R) {
  128. if (L == R) return;
  129. F0R(i,2) if (mx[2*ind^i][0] > mx[ind][0]) {
  130. sum[2*ind^i] -= (ll)maxCnt[2*ind^i]*
  131. (mx[2*ind^i][0]-mx[ind][0]);
  132. mx[2*ind^i][0] = mx[ind][0];
  133. }
  134. }
  135. void upd(int x, int y, int t, int ind=1, int L=0, int R=-1) {
  136. if (R == -1) R += N;
  137. if (R < x || y < L || mx[ind][0] <= t) return;
  138. push(ind,L,R);
  139. if (x <= L && R <= y && mx[ind][1] < t) {
  140. sum[ind] -= (ll)maxCnt[ind]*(mx[ind][0]-t);
  141. mx[ind][0] = t;
  142. return;
  143. }
  144. if (L == R) return;
  145. int M = (L+R)/2;
  146. upd(x,y,t,2*ind,L,M); upd(x,y,t,2*ind+1,M+1,R); pull(ind);
  147. }
  148. ll qsum(int x, int y, int ind = 1, int L = 0, int R = -1) {
  149. if (R == -1) R += N;
  150. if (R < x || y < L) return 0;
  151. push(ind,L,R);
  152. if (x <= L && R <= y) return sum[ind];
  153. int M = (L+R)/2;
  154. return qsum(x,y,2*ind,L,M)+qsum(x,y,2*ind+1,M+1,R);
  155. }
  156. int qmax(int x, int y, int ind = 1, int L = 0, int R = -1) {
  157. if (R == -1) R += N;
  158. if (R < x || y < L) return -1;
  159. push(ind,L,R);
  160. if (x <= L && R <= y) return mx[ind][0];
  161. int M = (L+R)/2;
  162. return max(qmax(x,y,2*ind,L,M),qmax(x,y,2*ind+1,M+1,R));
  163. }
  164. };
  165.  
  166.  
  167.  
  168. // Directed MST
  169.  
  170.  
  171. struct Edge { int a, b; ll w; };
  172. struct Node { // lazy skew heap node
  173. Edge key;
  174. Node *l, *r;
  175. ll delta;
  176. void prop() {
  177. key.w += delta;
  178. if (l) l->delta += delta;
  179. if (r) r->delta += delta;
  180. delta = 0;
  181. }
  182. Edge top() { prop(); return key; }
  183. };
  184. Node *merge(Node *a, Node *b) {
  185. if (!a || !b) return a ?: b;
  186. a->prop(), b->prop();
  187. if (a->key.w > b->key.w) swap(a, b);
  188. swap(a->l, a->r = merge(b, a->r));
  189. return a;
  190. }
  191. void pop(Node*& a) { a->prop(); a = merge(a->l, a->r); }
  192.  
  193. pair<ll,vi> dmst(int n, int r, const vector<Edge>& g) {
  194. DSUrb dsu; dsu.init(n);
  195. vector<Node*> heap(n); // store edges entering each vertex
  196. // in increasing order of weight
  197. trav(e,g) heap[e.b] = merge(heap[e.b], new Node{e});
  198. ll res = 0; vi seen(n,-1); seen[r] = r;
  199. vpi in(n,{-1,-1}); // edge entering each vertex in MST
  200. vector<pair<int,vector<Edge>>> cycs;
  201. F0R(s,n) {
  202. int u = s, w;
  203. vector<pair<int,Edge>> path;
  204. while (seen[u] < 0) {
  205. if (!heap[u]) return {-1,{}};
  206. seen[u] = s;
  207. Edge e = heap[u]->top(); path.pb({u,e});
  208. heap[u]->delta -= e.w, pop(heap[u]);
  209. res += e.w, u = dsu.get(e.a);
  210. if (seen[u] == s) { // found cycle, contract
  211. Node* cyc = 0; cycs.eb();
  212. do {
  213. cyc = merge(cyc, heap[w = path.bk.f]);
  214. cycs.bk.s.pb(path.bk.s);
  215. path.pop_back();
  216. } while (dsu.unite(u,w));
  217. u = dsu.get(u); heap[u] = cyc, seen[u] = -1;
  218. cycs.bk.f = u;
  219. }
  220. }
  221. trav(t,path) in[dsu.get(t.s.b)] = {t.s.a,t.s.b};
  222. // found path from root to s, done
  223. }
  224. while (sz(cycs)) { // expand cycs to restore sol
  225. auto c = cycs.bk; cycs.pop_back();
  226. pi inEdge = in[c.f];
  227. trav(t,c.s) dsu.rol.bk;
  228. trav(t,c.s) in[dsu.get(t.b)] = {t.a,t.b};
  229. in[dsu.get(inEdge.s)] = inEdge;
  230. }
  231. vi par(n); F0R(i,n) par[i] = in[i].f;
  232. // i == r ? in[i].s == -1 : in[i].s == i
  233. return {res,par};
  234. }
  235.  
  236.  
  237.  
  238. template<int SZ> struct EdgeColor {
  239. int N = 0, maxDeg = 0, adj[SZ][SZ], deg[SZ];
  240. EdgeColor() {
  241. memset(adj,0,sizeof adj);
  242. memset(deg,0,sizeof deg);
  243. }
  244. void ae(int a, int b, int c) {
  245. adj[a][b] = adj[b][a] = c; }
  246. int delEdge(int a, int b) {
  247. int c = adj[a][b]; adj[a][b] = adj[b][a] = 0;
  248. return c;
  249. }
  250. vector<bool> genCol(int x) {
  251. vector<bool> col(N+1); F0R(i,N) col[adj[x][i]] = 1;
  252. return col;
  253. }
  254. int freeCol(int u) {
  255. auto col = genCol(u);
  256. int x = 1; while (col[x]) x ++; return x;
  257. }
  258. void invert(int x, int d, int c) {
  259. F0R(i,N) if (adj[x][i] == d)
  260. delEdge(x,i), invert(i,c,d), ae(x,i,c);
  261. }
  262. void ae(int u, int v) { // follows wikipedia steps
  263. // check if you can add edge w/o doing any work
  264. assert(N); ckmax(maxDeg,max(++deg[u],++deg[v]));
  265. auto a = genCol(u), b = genCol(v);
  266. FOR(i,1,maxDeg+2) if (!a[i] && !b[i])
  267. return ae(u,v,i);
  268. // 2. find maximal fan of u starting at v
  269. vector<bool> use(N); vi fan = {v}; use[v] = 1;
  270. while (1) {
  271. auto col = genCol(fan.bk);
  272. if (sz(fan) > 1) col[adj[fan.bk][u]] = 0;
  273. int i = 0; while (i < N && (use[i] || col[adj[u][i]])) i ++;
  274. if (i < N) fan.pb(i), use[i] = 1;
  275. else break;
  276. }
  277. // 3/4. choose free cols for endpoints of fan, invert cd_u path
  278. int c = freeCol(u), d = freeCol(fan.bk); invert(u,d,c);
  279. // 5. find i such that d is free on fan[i]
  280. int i = 0; while (i < sz(fan) && genCol(fan[i])[d]
  281. && adj[u][fan[i]] != d) i ++;
  282. assert (i != sz(fan));
  283. // 6. rotate fan from 0 to i
  284. F0R(j,i) ae(u,fan[j],delEdge(u,fan[j+1]));
  285. // 7. add new edge
  286. ae(u,fan[i],d);
  287. }
  288. };
  289.  
  290.  
  291. /**
  292. * Description: Used only once. Finds all maximal cliques.
  293. * Time: O(3^{N/3})
  294. * Source: KACTL
  295. * Verification: BOSPRE 2016 gaudy
  296. */
  297.  
  298. typedef bitset<128> B;
  299. int N;
  300. B adj[128];
  301.  
  302. // possibly in clique, not in clique, in clique
  303. void cliques(B P = ~B(), B X={}, B R={}) {
  304. if (!P.any()) {
  305. if (!X.any()) {
  306. // do smth with R
  307. }
  308. return;
  309. }
  310. int q = (P|X)._Find_first();
  311. // clique must contain q or non-neighbor of q
  312. B cands = P&~adj[q];
  313. F0R(i,N) if (cands[i]) {
  314. R[i] = 1;
  315. cliques(P&adj[i],X&adj[i],R);
  316. R[i] = P[i] = 0; X[i] = 1;
  317. }
  318. }
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325. // Linear Recurence
  326.  
  327. vector<int> berlekamp(vector<int> s) {
  328. int l = 0;
  329. vector<int> la(1, 1);
  330. vector<int> b(1, 1);
  331. for (int r = 1; r <= (int)s.size(); r++) {
  332. int delta = 0;
  333. for (int j = 0; j <= l; j++) {
  334. delta = (delta + 1LL * s[r - 1 - j] * la[j]) % MOD;
  335. }
  336. b.insert(b.begin(), 0);
  337. if (delta != 0) {
  338. vector<int> t(max(la.size(), b.size()));
  339. for (int i = 0; i < (int)t.size(); i++) {
  340. if (i < (int)la.size()) t[i] = (t[i] + la[i]) % MOD;
  341. if (i < (int)b.size()) t[i] = (t[i] - 1LL * delta * b[i] % MOD + MOD) % MOD;
  342. }
  343. if (2 * l <= r - 1) {
  344. b = la;
  345. int od = inv(delta);
  346. for (int &x : b) x = 1LL * x * od % MOD;
  347. l = r - l;
  348. }
  349. la = t;
  350. }
  351. }
  352. assert((int)la.size() == l + 1);
  353. assert(l * 2 + 30 < (int)s.size());
  354. reverse(la.begin(), la.end());
  355. return la;
  356. }
  357.  
  358. vector<int> mul(vector<int> a, vector<int> b) {
  359. vector<int> c(a.size() + b.size() - 1);
  360. for (int i = 0; i < (int)a.size(); i++) {
  361. for (int j = 0; j < (int)b.size(); j++) {
  362. c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % MOD;
  363. }
  364. }
  365. vector<int> res(c.size());
  366. for (int i = 0; i < (int)res.size(); i++) res[i] = c[i] % MOD;
  367. return res;
  368. }
  369.  
  370. vector<int> mod(vector<int> a, vector<int> b) {
  371. if (a.size() < b.size()) a.resize(b.size() - 1);
  372.  
  373. int o = inv(b.back());
  374. for (int i = (int)a.size() - 1; i >= (int)b.size() - 1; i--) {
  375. if (a[i] == 0) continue;
  376. int coef = 1LL * o * (MOD - a[i]) % MOD;
  377. for (int j = 0; j < (int)b.size(); j++) {
  378. a[i - (int)b.size() + 1 + j] = (a[i - (int)b.size() + 1 + j] + 1LL * coef * b[j]) % MOD;
  379. }
  380. }
  381. while (a.size() >= b.size()) {
  382. assert(a.back() == 0);
  383. a.pop_back();
  384. }
  385. return a;
  386. }
  387.  
  388. vector<int> bin(int n, vector<int> p) {
  389. vector<int> res(1, 1);
  390. vector<int> a(2); a[1] = 1;
  391. while (n) {
  392. if (n & 1) res = mod(mul(res, a), p);
  393. a = mod(mul(a, a), p);
  394. n >>= 1;
  395. }
  396. return res;
  397. }
  398.  
  399. int f(vector<int> t, int m) {
  400. vector<int> v = berlekamp(t);
  401. vector<int> o = bin(m - 1, v);
  402. int res = 0;
  403. for (int i = 0; i < (int)o.size(); i++) res = (res + 1LL * o[i] * t[i]) % MOD;
  404. return res;
  405. }
  406.  
  407.  
  408.  
  409. // Split-merge sqrt
  410.  
  411. const int pivo = 3e5 + 555, magic = 700;
  412. int ex[pivo];
  413. vector<int> s[magic];
  414. int mn[pivo], mx[pivo], psz[pivo];
  415. int n, q;
  416.  
  417. void rebuild() {
  418. vector<int> order;
  419. for (int i = 0; i < magic; i++) {
  420. for (auto j : s[i]) order.push_back(j);
  421. s[i].clear();
  422. }
  423. for (int i = 0; i < n; i++) {
  424. s[i / magic].push_back(order[i]);
  425. ex[order[i]] = i / magic;
  426. }
  427. }
  428.  
  429. signed main() {
  430. ios::sync_with_stdio(0);
  431. cin.tie(0);
  432. cin >> n >> q;
  433. for (int i = 1; i <= n; i++) {
  434. mx[i] = mn[i] = i;
  435. s[i / magic].push_back(i);
  436. ex[i] = i / magic;
  437. }
  438. while(q--) {
  439. int x;
  440. cin >> x;
  441. int sz = 0;
  442. for (int i = 0; i < magic; i++) {
  443. if (ex[x] == i) {
  444. ex[x] = 0;
  445. auto it = find(s[i].begin(), s[i].end(), x);
  446. mx[x] = max(mx[x], sz + 1 + (it - s[i].begin()));
  447. mn[x] = 1;
  448. s[i].erase(it);
  449. s[0].insert(s[0].begin(), x);
  450. break;
  451. }
  452. sz += s[i].size();
  453. }
  454. if (s[0].size() > 4 * magic) rebuild();
  455. }
  456. vector<int> order;
  457. for (int i = 0; i < magic; i++) {
  458. for (auto j : s[i]) order.push_back(j);
  459. }
  460. for (int i = 0; i < n; i++) mn[order[i]] = min(mn[order[i]], i + 1), mx[order[i]] = max(mx[order[i]], i + 1);
  461. for (int i = 1; i <= n; i++) cout << mn[i] << " " << mx[i] << endl;
  462. }
  463.  
  464.  
  465.  
  466.  
  467. template<int SZ> struct EdgeColor {
  468. int N = 0, maxDeg = 0, adj[SZ][SZ], deg[SZ];
  469. EdgeColor() {
  470. memset(adj,0,sizeof adj);
  471. memset(deg,0,sizeof deg);
  472. }
  473. void ae(int a, int b, int c) {
  474. adj[a][b] = adj[b][a] = c; }
  475. int delEdge(int a, int b) {
  476. int c = adj[a][b]; adj[a][b] = adj[b][a] = 0;
  477. return c;
  478. }
  479. vector<bool> genCol(int x) {
  480. vector<bool> col(N+1); F0R(i,N) col[adj[x][i]] = 1;
  481. return col;
  482. }
  483. int freeCol(int u) {
  484. auto col = genCol(u);
  485. int x = 1; while (col[x]) x ++; return x;
  486. }
  487. void invert(int x, int d, int c) {
  488. F0R(i,N) if (adj[x][i] == d)
  489. delEdge(x,i), invert(i,c,d), ae(x,i,c);
  490. }
  491. void ae(int u, int v) { // follows wikipedia steps
  492. // check if you can add edge w/o doing any work
  493. assert(N); ckmax(maxDeg,max(++deg[u],++deg[v]));
  494. auto a = genCol(u), b = genCol(v);
  495. FOR(i,1,maxDeg+2) if (!a[i] && !b[i])
  496. return ae(u,v,i);
  497. // 2. find maximal fan of u starting at v
  498. vector<bool> use(N); vi fan = {v}; use[v] = 1;
  499. while (1) {
  500. auto col = genCol(fan.bk);
  501. if (sz(fan) > 1) col[adj[fan.bk][u]] = 0;
  502. int i = 0; while (i < N && (use[i] || col[adj[u][i]])) i ++;
  503. if (i < N) fan.pb(i), use[i] = 1;
  504. else break;
  505. }
  506. // 3/4. choose free cols for endpoints of fan, invert cd_u path
  507. int c = freeCol(u), d = freeCol(fan.bk); invert(u,d,c);
  508. // 5. find i such that d is free on fan[i]
  509. int i = 0; while (i < sz(fan) && genCol(fan[i])[d]
  510. && adj[u][fan[i]] != d) i ++;
  511. assert (i != sz(fan));
  512. // 6. rotate fan from 0 to i
  513. F0R(j,i) ae(u,fan[j],delEdge(u,fan[j+1]));
  514. // 7. add new edge
  515. ae(u,fan[i],d);
  516. }
  517. };
  518.  
  519.  
  520.  
  521. vector<pair<int,pi>> manhattanMst(vpi v) {
  522. vi id(sz(v)); iota(all(id),0);
  523. vector<pair<int,pi>> ed;
  524. F0R(k,4) {
  525. sort(all(id),[&](int i, int j) {
  526. return v[i].f+v[i].s < v[j].f+v[j].s; });
  527. map<int,int> sweep;
  528. trav(i,id) { // find neighbors for first octant
  529. for (auto it = sweep.lb(-v[i].s);
  530. it != end(sweep); sweep.erase(it++)) {
  531. int j = it->s;
  532. pi d = {v[i].f-v[j].f,v[i].s-v[j].s};
  533. if (d.s > d.f) break;
  534. ed.pb({d.f+d.s,{i,j}});
  535. }
  536. sweep[-v[i].s] = i;
  537. }
  538. trav(p,v) {
  539. if (k&1) p.f *= -1;
  540. else swap(p.f,p.s);
  541. }
  542. }
  543. return ed;
  544. }
  545.  
  546.  
  547.  
  548. // Perm
  549.  
  550.  
  551.  
  552. vi decode(int n, int a) {
  553. vi el(n), b; iota(all(el),0);
  554. F0R(i,n) {
  555. int z = a%sz(el);
  556. b.pb(el[z]); a /= sz(el);
  557. swap(el[z],el.bk); el.pop_back();
  558. }
  559. return b;
  560. }
  561. int encode(vi b) {
  562. int n = sz(b), a = 0, mul = 1;
  563. vi pos(n); iota(all(pos),0); vi el = pos;
  564. F0R(i,n) {
  565. int z = pos[b[i]]; a += mul*z; mul *= sz(el);
  566. swap(pos[el[z]],pos[el.bk]);
  567. swap(el[z],el.bk); el.pop_back();
  568. }
  569. return a;
  570. }
  571.  
  572. // PermGroup
  573.  
  574.  
  575.  
  576. int n;
  577. vi inv(vi v) { vi V(sz(v)); F0R(i,sz(v)) V[v[i]]=i; return V; }
  578. vi id() { vi v(n); iota(all(v),0); return v; }
  579. vi operator*(const vi& a, const vi& b) {
  580. vi c(sz(a)); F0R(i,sz(a)) c[i] = a[b[i]];
  581. return c;
  582. }
  583.  
  584. const int N = 15;
  585. struct Group {
  586. bool flag[N];
  587. vi sigma[N]; // sigma[t][k] = t, sigma[t][x] = x if x > k
  588. vector<vi> gen;
  589. void clear(int p) {
  590. memset(flag,0, sizeof flag);
  591. flag[p] = 1; sigma[p] = id();
  592. gen.clear();
  593. }
  594. } g[N];
  595.  
  596. bool check(const vi& cur, int k) {
  597. if (!k) return 1;
  598. int t = cur[k];
  599. return g[k].flag[t] ? check(inv(g[k].sigma[t])*cur,k-1) : 0;
  600. }
  601. void updateX(const vi& cur, int k);
  602. void ins(const vi& cur, int k) {
  603. if (check(cur,k)) return;
  604. g[k].gen.pb(cur);
  605. F0R(i,n) if (g[k].flag[i]) updateX(cur*g[k].sigma[i],k);
  606. }
  607. void updateX(const vi& cur, int k) {
  608. int t = cur[k]; // if flag, fixes k -> k
  609. if (g[k].flag[t]) ins(inv(g[k].sigma[t])*cur,k-1);
  610. else {
  611. g[k].flag[t] = 1, g[k].sigma[t] = cur;
  612. trav(x,g[k].gen) updateX(x*cur,k);
  613. }
  614. }
  615.  
  616. ll order(vector<vi> gen) {
  617. assert(sz(gen)); n = sz(gen[0]); F0R(i,n) g[i].clear(i);
  618. trav(a,gen) ins(a,n-1); // insert perms into group one by one
  619. ll tot = 1;
  620. F0R(i,n) {
  621. int cnt = 0; F0R(j,i+1) cnt += g[i].flag[j];
  622. tot *= cnt;
  623. }
  624. return tot;
  625. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!