Hex Artifact Content
Not logged in

Artifact 065fcd1fef379fbc20663c14ea32f056abd94704:


0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0040: 0a 2f 2f 20 4d 6f 64 75 6c 6f 20 41 72 69 74 68  .// Modulo Arith
0050: 6d 65 74 69 63 73 0a 2f 2f 0a 2f 2f 20 56 65 72  metics.//.// Ver
0060: 69 66 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20  ified by.//   - 
0070: 54 43 4f 31 30 20 52 33 20 4c 56 33 0a 2f 2f 20  TCO10 R3 LV3.// 
0080: 20 20 2d 20 53 52 4d 20 35 34 35 20 44 69 76 31    - SRM 545 Div1
0090: 20 4c 56 32 0a 2f 2f 20 20 20 2d 20 53 52 4d 20   LV2.//   - SRM 
00a0: 35 35 34 20 44 69 76 31 20 4c 56 33 0a 2f 2f 2d  554 Div1 LV3.//-
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 73 74  ------------..st
00f0: 61 74 69 63 20 63 6f 6e 73 74 20 75 6e 73 69 67  atic const unsig
0100: 6e 65 64 20 4d 4f 44 56 41 4c 20 3d 20 31 30 30  ned MODVAL = 100
0110: 30 30 30 30 30 30 37 3b 0a 73 74 72 75 63 74 20  0000007;.struct 
0120: 6d 69 6e 74 0a 7b 0a 09 75 6e 73 69 67 6e 65 64  mint.{..unsigned
0130: 20 76 61 6c 3b 0a 09 6d 69 6e 74 28 29 3a 76 61   val;..mint():va
0140: 6c 28 30 29 7b 7d 0a 09 6d 69 6e 74 28 69 6e 74  l(0){}..mint(int
0150: 20 20 20 20 20 20 78 29 3a 76 61 6c 28 78 25 4d        x):val(x%M
0160: 4f 44 56 41 4c 29 20 7b 7d 0a 09 6d 69 6e 74 28  ODVAL) {}..mint(
0170: 75 6e 73 69 67 6e 65 64 20 78 29 3a 76 61 6c 28  unsigned x):val(
0180: 78 25 4d 4f 44 56 41 4c 29 20 7b 7d 0a 09 6d 69  x%MODVAL) {}..mi
0190: 6e 74 28 4c 4c 20 20 20 20 20 20 20 78 29 3a 76  nt(LL       x):v
01a0: 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b 7d 0a  al(x%MODVAL) {}.
01b0: 7d 3b 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 6f  };.mint& operato
01c0: 72 2b 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 6e  r+=(mint& x, min
01d0: 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 20  t y) { return x 
01e0: 3d 20 78 2e 76 61 6c 2b 79 2e 76 61 6c 3b 20 7d  = x.val+y.val; }
01f0: 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 6f 72 2d  .mint& operator-
0200: 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 6e 74 20  =(mint& x, mint 
0210: 79 29 20 7b 20 72 65 74 75 72 6e 20 78 20 3d 20  y) { return x = 
0220: 78 2e 76 61 6c 2d 79 2e 76 61 6c 2b 4d 4f 44 56  x.val-y.val+MODV
0230: 41 4c 3b 20 7d 0a 6d 69 6e 74 26 20 6f 70 65 72  AL; }.mint& oper
0240: 61 74 6f 72 2a 3d 28 6d 69 6e 74 26 20 78 2c 20  ator*=(mint& x, 
0250: 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e  mint y) { return
0260: 20 78 20 3d 20 4c 4c 28 78 2e 76 61 6c 29 2a 79   x = LL(x.val)*y
0270: 2e 76 61 6c 3b 20 7d 0a 6d 69 6e 74 20 6f 70 65  .val; }.mint ope
0280: 72 61 74 6f 72 2b 28 6d 69 6e 74 20 78 2c 20 6d  rator+(mint x, m
0290: 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20  int y) { return 
02a0: 78 2b 3d 79 3b 20 7d 0a 6d 69 6e 74 20 6f 70 65  x+=y; }.mint ope
02b0: 72 61 74 6f 72 2d 28 6d 69 6e 74 20 78 2c 20 6d  rator-(mint x, m
02c0: 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20  int y) { return 
02d0: 78 2d 3d 79 3b 20 7d 0a 6d 69 6e 74 20 6f 70 65  x-=y; }.mint ope
02e0: 72 61 74 6f 72 2a 28 6d 69 6e 74 20 78 2c 20 6d  rator*(mint x, m
02f0: 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20  int y) { return 
0300: 78 2a 3d 79 3b 20 7d 0a 0a 6d 69 6e 74 20 50 4f  x*=y; }..mint PO
0310: 57 28 6d 69 6e 74 20 78 2c 20 4c 4c 20 65 29 20  W(mint x, LL e) 
0320: 7b 20 6d 69 6e 74 20 76 3d 31 3b 20 66 6f 72 28  { mint v=1; for(
0330: 3b 65 3b 78 2a 3d 78 2c 65 3e 3e 3d 31 29 20 69  ;e;x*=x,e>>=1) i
0340: 66 28 65 26 31 29 20 76 2a 3d 78 3b 20 72 65 74  f(e&1) v*=x; ret
0350: 75 72 6e 20 76 3b 20 7d 0a 6d 69 6e 74 26 20 6f  urn v; }.mint& o
0360: 70 65 72 61 74 6f 72 2f 3d 28 6d 69 6e 74 26 20  perator/=(mint& 
0370: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74  x, mint y) { ret
0380: 75 72 6e 20 78 20 2a 3d 20 50 4f 57 28 79 2c 20  urn x *= POW(y, 
0390: 4d 4f 44 56 41 4c 2d 32 29 3b 20 7d 0a 6d 69 6e  MODVAL-2); }.min
03a0: 74 20 6f 70 65 72 61 74 6f 72 2f 28 6d 69 6e 74  t operator/(mint
03b0: 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65   x, mint y) { re
03c0: 74 75 72 6e 20 78 2f 3d 79 3b 20 7d 0a 0a 76 65  turn x/=y; }..ve
03d0: 63 74 6f 72 3c 6d 69 6e 74 3e 20 46 41 43 5f 28  ctor<mint> FAC_(
03e0: 31 2c 31 29 3b 0a 6d 69 6e 74 20 46 41 43 28 4c  1,1);.mint FAC(L
03f0: 4c 20 6e 29 20 7b 20 77 68 69 6c 65 28 20 46 41  L n) { while( FA
0400: 43 5f 2e 73 69 7a 65 28 29 3c 3d 6e 20 29 20 46  C_.size()<=n ) F
0410: 41 43 5f 2e 70 75 73 68 5f 62 61 63 6b 28 20 46  AC_.push_back( F
0420: 41 43 5f 2e 62 61 63 6b 28 29 2a 46 41 43 5f 2e  AC_.back()*FAC_.
0430: 73 69 7a 65 28 29 20 29 3b 20 72 65 74 75 72 6e  size() ); return
0440: 20 46 41 43 5f 5b 6e 5d 3b 20 7d 0a 0a 2f 2f 20   FAC_[n]; }..// 
0450: 6e 43 6b 20 3a 3a 20 4f 28 6c 6f 67 20 4d 4f 44  nCk :: O(log MOD
0460: 56 41 4c 29 20 74 69 6d 65 2c 20 4f 28 6e 29 20  VAL) time, O(n) 
0470: 73 70 61 63 65 2e 0a 6d 69 6e 74 20 43 28 4c 4c  space..mint C(LL
0480: 20 6e 2c 20 4c 4c 20 6b 29 20 7b 20 72 65 74 75   n, LL k) { retu
0490: 72 6e 20 6b 3c 30 20 7c 7c 20 6e 3c 6b 20 3f 20  rn k<0 || n<k ? 
04a0: 30 20 3a 20 46 41 43 28 6e 29 20 2f 20 28 46 41  0 : FAC(n) / (FA
04b0: 43 28 6b 29 20 2a 20 46 41 43 28 6e 2d 6b 29 29  C(k) * FAC(n-k))
04c0: 3b 20 7d 0a 0a 2f 2f 20 6e 43 6b 20 3a 3a 20 4f  ; }..// nCk :: O
04d0: 28 31 29 20 74 69 6d 65 2c 20 4f 28 6e 5e 32 29  (1) time, O(n^2)
04e0: 20 73 70 61 63 65 2e 0a 76 65 63 74 6f 72 3c 20   space..vector< 
04f0: 76 65 63 74 6f 72 3c 6d 69 6e 74 3e 20 3e 20 43  vector<mint> > C
0500: 50 5f 3b 0a 6d 69 6e 74 20 43 28 4c 4c 20 6e 2c  P_;.mint C(LL n,
0510: 20 4c 4c 20 6b 29 20 7b 0a 09 77 68 69 6c 65 28   LL k) {..while(
0520: 20 43 50 5f 2e 73 69 7a 65 28 29 20 3c 3d 20 6e   CP_.size() <= n
0530: 20 29 20 7b 0a 09 09 69 6e 74 20 6e 6e 20 3d 20   ) {...int nn = 
0540: 43 50 5f 2e 73 69 7a 65 28 29 3b 0a 09 09 43 50  CP_.size();...CP
0550: 5f 2e 70 75 73 68 5f 62 61 63 6b 28 76 65 63 74  _.push_back(vect
0560: 6f 72 3c 6d 69 6e 74 3e 28 6e 6e 2b 31 2c 31 29  or<mint>(nn+1,1)
0570: 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 6b 6b 3d  );...for(int kk=
0580: 31 3b 20 6b 6b 3c 6e 6e 3b 20 2b 2b 6b 6b 29 0a  1; kk<nn; ++kk).
0590: 09 09 09 43 50 5f 5b 6e 6e 5d 5b 6b 6b 5d 20 3d  ...CP_[nn][kk] =
05a0: 20 43 50 5f 5b 6e 6e 2d 31 5d 5b 6b 6b 2d 31 5d   CP_[nn-1][kk-1]
05b0: 20 2b 20 43 50 5f 5b 6e 6e 2d 31 5d 5b 6b 6b 5d   + CP_[nn-1][kk]
05c0: 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 6b 3c 30  ;..}..return k<0
05d0: 20 7c 7c 20 6e 3c 6b 20 3f 20 30 20 3a 20 43 50   || n<k ? 0 : CP
05e0: 5f 5b 6e 5d 5b 6b 5d 3b 0a 7d 0a 0a 2f 2f 20 4f  _[n][k];.}..// O
05f0: 28 6c 6f 67 20 4d 4f 44 56 41 4c 29 2c 20 4d 4f  (log MODVAL), MO
0600: 44 56 41 4c 20 6d 75 73 74 20 62 65 20 70 72 69  DVAL must be pri
0610: 6d 65 3a 20 6b 5e 62 20 2b 20 6b 5e 62 2b 31 20  me: k^b + k^b+1 
0620: 2b 20 2e 2e 2e 20 2b 20 6b 5e 65 0a 6d 69 6e 74  + ... + k^e.mint
0630: 20 47 53 53 28 6d 69 6e 74 20 6b 2c 20 4c 4c 20   GSS(mint k, LL 
0640: 62 2c 20 4c 4c 20 65 29 20 0a 7b 0a 09 69 66 28  b, LL e) .{..if(
0650: 20 62 20 3e 20 65 20 29 20 72 65 74 75 72 6e 20   b > e ) return 
0660: 30 3b 0a 09 69 66 28 20 6b 2e 76 61 6c 20 3c 3d  0;..if( k.val <=
0670: 20 31 20 29 20 72 65 74 75 72 6e 20 6b 2a 28 65   1 ) return k*(e
0680: 2d 62 2b 31 29 3b 0a 09 72 65 74 75 72 6e 20 28  -b+1);..return (
0690: 50 4f 57 28 6b 2c 20 65 2b 31 29 20 2d 20 50 4f  POW(k, e+1) - PO
06a0: 57 28 6b 2c 62 29 29 20 2f 20 28 6b 2d 31 29 3b  W(k,b)) / (k-1);
06b0: 0a 7d 0a                                         .}.