Artifact 76c58f82b36b80e2aa9df082d49df2c5c76b799e:
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 2d TCO10 R3 LV3.//-
0080: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0090: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 73 74 ------------..st
00c0: 61 74 69 63 20 63 6f 6e 73 74 20 69 6e 74 20 4d atic const int M
00d0: 4f 44 56 41 4c 20 3d 20 31 30 30 30 30 30 30 30 ODVAL = 10000000
00e0: 30 37 3b 20 2f 2f 20 6d 75 73 74 20 62 65 20 70 07; // must be p
00f0: 72 69 6d 65 20 66 6f 72 20 6f 70 2f 0a 73 74 72 rime for op/.str
0100: 75 63 74 20 6d 69 6e 74 0a 7b 0a 09 69 6e 74 20 uct mint.{..int
0110: 76 61 6c 3b 0a 09 6d 69 6e 74 28 29 3a 76 61 6c val;..mint():val
0120: 28 30 29 7b 7d 0a 09 6d 69 6e 74 28 69 6e 74 20 (0){}..mint(int
0130: 20 20 20 78 29 3a 76 61 6c 28 78 25 4d 4f 44 56 x):val(x%MODV
0140: 41 4c 29 20 7b 7d 20 2f 2f 20 78 3e 3d 30 0a 09 AL) {} // x>=0..
0150: 6d 69 6e 74 28 73 69 7a 65 5f 74 20 78 29 3a 76 mint(size_t x):v
0160: 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b 7d 20 al(x%MODVAL) {}
0170: 2f 2f 20 78 3e 3d 30 0a 09 6d 69 6e 74 28 4c 4c // x>=0..mint(LL
0180: 20 20 20 20 20 78 29 3a 76 61 6c 28 78 25 4d 4f x):val(x%MO
0190: 44 56 41 4c 29 20 7b 7d 20 2f 2f 20 78 3e 3d 30 DVAL) {} // x>=0
01a0: 0a 7d 3b 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 .};.mint& operat
01b0: 6f 72 2b 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 or+=(mint& x, mi
01c0: 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 nt y) { return x
01d0: 20 3d 20 78 2e 76 61 6c 2b 79 2e 76 61 6c 3b 20 = x.val+y.val;
01e0: 7d 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 6f 72 }.mint& operator
01f0: 2d 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 6e 74 -=(mint& x, mint
0200: 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 20 3d y) { return x =
0210: 20 78 2e 76 61 6c 2d 79 2e 76 61 6c 2b 4d 4f 44 x.val-y.val+MOD
0220: 56 41 4c 3b 20 7d 0a 6d 69 6e 74 26 20 6f 70 65 VAL; }.mint& ope
0230: 72 61 74 6f 72 2a 3d 28 6d 69 6e 74 26 20 78 2c rator*=(mint& x,
0240: 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 mint y) { retur
0250: 6e 20 78 20 3d 20 4c 4c 28 78 2e 76 61 6c 29 2a n x = LL(x.val)*
0260: 79 2e 76 61 6c 3b 20 7d 0a 6d 69 6e 74 20 50 4f y.val; }.mint PO
0270: 57 28 6d 69 6e 74 20 78 2c 20 4c 4c 20 65 29 20 W(mint x, LL e)
0280: 7b 20 6d 69 6e 74 20 76 3d 31 3b 20 66 6f 72 28 { mint v=1; for(
0290: 3b 65 3b 78 2a 3d 78 2c 65 3e 3e 3d 31 29 20 69 ;e;x*=x,e>>=1) i
02a0: 66 28 65 26 31 29 20 76 2a 3d 78 3b 20 72 65 74 f(e&1) v*=x; ret
02b0: 75 72 6e 20 76 3b 20 7d 0a 6d 69 6e 74 26 20 6f urn v; }.mint& o
02c0: 70 65 72 61 74 6f 72 2f 3d 28 6d 69 6e 74 26 20 perator/=(mint&
02d0: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 x, mint y) { ret
02e0: 75 72 6e 20 78 20 2a 3d 20 50 4f 57 28 79 2c 20 urn x *= POW(y,
02f0: 4d 4f 44 56 41 4c 2d 32 29 3b 20 7d 0a 6d 69 6e MODVAL-2); }.min
0300: 74 20 6f 70 65 72 61 74 6f 72 2b 28 6d 69 6e 74 t operator+(mint
0310: 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 x, mint y) { re
0320: 74 75 72 6e 20 78 2b 3d 79 3b 20 7d 0a 6d 69 6e turn x+=y; }.min
0330: 74 20 6f 70 65 72 61 74 6f 72 2d 28 6d 69 6e 74 t operator-(mint
0340: 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 x, mint y) { re
0350: 74 75 72 6e 20 78 2d 3d 79 3b 20 7d 0a 6d 69 6e turn x-=y; }.min
0360: 74 20 6f 70 65 72 61 74 6f 72 2a 28 6d 69 6e 74 t operator*(mint
0370: 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 x, mint y) { re
0380: 74 75 72 6e 20 78 2a 3d 79 3b 20 7d 0a 6d 69 6e turn x*=y; }.min
0390: 74 20 6f 70 65 72 61 74 6f 72 2f 28 6d 69 6e 74 t operator/(mint
03a0: 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 x, mint y) { re
03b0: 74 75 72 6e 20 78 2f 3d 79 3b 20 7d 0a 76 65 63 turn x/=y; }.vec
03c0: 74 6f 72 3c 6d 69 6e 74 3e 20 46 41 43 5f 28 31 tor<mint> FAC_(1
03d0: 2c 31 29 3b 0a 6d 69 6e 74 20 46 41 43 28 4c 4c ,1);.mint FAC(LL
03e0: 20 6e 29 20 7b 20 77 68 69 6c 65 28 20 46 41 43 n) { while( FAC
03f0: 5f 2e 73 69 7a 65 28 29 3c 3d 6e 20 29 20 46 41 _.size()<=n ) FA
0400: 43 5f 2e 70 75 73 68 5f 62 61 63 6b 28 20 46 41 C_.push_back( FA
0410: 43 5f 2e 62 61 63 6b 28 29 2a 46 41 43 5f 2e 73 C_.back()*FAC_.s
0420: 69 7a 65 28 29 20 29 3b 20 72 65 74 75 72 6e 20 ize() ); return
0430: 46 41 43 5f 5b 6e 5d 3b 20 7d 0a 6d 69 6e 74 20 FAC_[n]; }.mint
0440: 43 28 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 20 7b 20 C(LL n, LL k) {
0450: 72 65 74 75 72 6e 20 6b 3c 30 20 7c 7c 20 6e 3c return k<0 || n<
0460: 6b 20 3f 20 30 20 3a 20 46 41 43 28 6e 29 20 2f k ? 0 : FAC(n) /
0470: 20 28 46 41 43 28 6b 29 20 2a 20 46 41 43 28 6e (FAC(k) * FAC(n
0480: 2d 6b 29 29 3b 20 7d 0a 0a 0a 0a 0a 2f 2a 0a 2f -k)); }...../*./
0490: 2f 20 4d 4f 44 56 41 4c 20 6d 75 73 74 20 62 65 / MODVAL must be
04a0: 20 61 20 70 72 69 6d 65 21 21 0a 4c 4c 20 47 53 a prime!!.LL GS
04b0: 53 28 4c 4c 20 6b 2c 20 4c 4c 20 62 2c 20 4c 4c S(LL k, LL b, LL
04c0: 20 65 29 20 2f 2f 20 6b 5e 62 20 2b 20 6b 5e 62 e) // k^b + k^b
04d0: 2b 31 20 2b 20 2e 2e 2e 20 2b 20 6b 5e 65 0a 7b +1 + ... + k^e.{
04e0: 0a 09 69 66 28 20 62 20 3e 20 20 65 20 29 20 72 ..if( b > e ) r
04f0: 65 74 75 72 6e 20 30 3b 0a 09 69 66 28 20 6b 20 eturn 0;..if( k
0500: 3c 3d 20 31 20 29 20 72 65 74 75 72 6e 20 6b 2a <= 1 ) return k*
0510: 28 65 2d 62 2b 31 29 3b 0a 09 72 65 74 75 72 6e (e-b+1);..return
0520: 20 44 49 56 28 53 55 42 28 50 4f 57 28 6b 2c 20 DIV(SUB(POW(k,
0530: 65 2b 31 29 2c 20 50 4f 57 28 6b 2c 62 29 29 2c e+1), POW(k,b)),
0540: 20 6b 2d 31 29 3b 0a 7d 0a 0a 4c 4c 20 43 70 61 k-1);.}..LL Cpa
0550: 73 63 61 6c 28 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 scal(LL n, LL k)
0560: 0a 7b 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 .{..vector< vect
0570: 6f 72 3c 4c 4c 3e 20 3e 20 63 28 6e 2b 31 2c 20 or<LL> > c(n+1,
0580: 76 65 63 74 6f 72 3c 4c 4c 3e 28 6b 2b 31 29 29 vector<LL>(k+1))
0590: 3b 0a 09 66 6f 72 28 4c 4c 20 6e 6e 3d 31 3b 20 ;..for(LL nn=1;
05a0: 6e 6e 3c 3d 6e 3b 20 2b 2b 6e 6e 29 0a 09 09 66 nn<=n; ++nn)...f
05b0: 6f 72 28 4c 4c 20 6b 6b 3d 30 3b 20 6b 6b 3c 3d or(LL kk=0; kk<=
05c0: 6d 69 6e 28 6e 6e 2c 6b 29 3b 20 2b 2b 6b 6b 29 min(nn,k); ++kk)
05d0: 0a 09 09 09 63 5b 6e 6e 5d 5b 6b 6b 5d 20 3d 20 ....c[nn][kk] =
05e0: 6b 6b 3d 3d 30 20 7c 7c 20 6b 6b 3d 3d 6e 6e 20 kk==0 || kk==nn
05f0: 3f 20 31 20 3a 20 41 44 44 28 63 5b 6e 6e 2d 31 ? 1 : ADD(c[nn-1
0600: 5d 5b 6b 6b 2d 31 5d 2c 20 63 5b 6e 6e 2d 31 5d ][kk-1], c[nn-1]
0610: 5b 6b 6b 5d 29 3b 0a 09 72 65 74 75 72 6e 20 63 [kk]);..return c
0620: 5b 6e 5d 5b 6b 5d 3b 0a 7d 0a 0a 76 65 63 74 6f [n][k];.}..vecto
0630: 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 r< vector<LL> >
0640: 4d 41 54 4d 55 4c 28 76 65 63 74 6f 72 3c 20 76 MATMUL(vector< v
0650: 65 63 74 6f 72 3c 4c 4c 3e 20 3e 26 20 61 2c 20 ector<LL> >& a,
0660: 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c vector< vector<L
0670: 4c 3e 20 3e 26 20 62 29 0a 7b 0a 20 20 20 69 6e L> >& b).{. in
0680: 74 20 4e 20 3d 20 61 2e 73 69 7a 65 28 29 3b 0a t N = a.size();.
0690: 20 20 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f vector< vecto
06a0: 72 3c 4c 4c 3e 20 3e 20 63 28 4e 2c 20 76 65 63 r<LL> > c(N, vec
06b0: 74 6f 72 3c 4c 4c 3e 28 4e 29 29 3b 0a 20 20 20 tor<LL>(N));.
06c0: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e for(int i=0; i<N
06d0: 3b 20 2b 2b 69 29 0a 20 20 20 66 6f 72 28 69 6e ; ++i). for(in
06e0: 74 20 6a 3d 30 3b 20 6a 3c 4e 3b 20 2b 2b 6a 29 t j=0; j<N; ++j)
06f0: 0a 20 20 20 66 6f 72 28 69 6e 74 20 6b 3d 30 3b . for(int k=0;
0700: 20 6b 3c 4e 3b 20 2b 2b 6b 29 0a 20 20 20 20 20 k<N; ++k).
0710: 20 63 5b 69 5d 5b 6a 5d 20 3d 20 41 44 44 28 63 c[i][j] = ADD(c
0720: 5b 69 5d 5b 6a 5d 2c 20 4d 55 4c 28 61 5b 69 5d [i][j], MUL(a[i]
0730: 5b 6b 5d 2c 62 5b 6b 5d 5b 6a 5d 29 29 3b 0a 20 [k],b[k][j]));.
0740: 20 20 72 65 74 75 72 6e 20 63 3b 0a 7d 0a 0a 2f return c;.}../
0750: 2f 20 77 6f 72 6b 73 20 66 6f 72 20 6e 6f 6e 2d / works for non-
0760: 70 72 69 6d 65 20 4d 4f 44 56 41 4c 0a 4c 4c 20 prime MODVAL.LL
0770: 47 45 4f 28 4c 4c 20 78 5f 2c 20 4c 4c 20 65 29 GEO(LL x_, LL e)
0780: 20 2f 2f 20 78 5e 30 20 2b 20 78 5e 31 20 2b 20 // x^0 + x^1 +
0790: 2e 2e 2e 20 2b 20 78 5e 65 2d 31 0a 7b 0a 20 20 ... + x^e-1.{.
07a0: 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c vector< vector<
07b0: 4c 4c 3e 20 3e 20 76 28 32 2c 20 76 65 63 74 6f LL> > v(2, vecto
07c0: 72 3c 4c 4c 3e 28 32 29 29 3b 0a 20 20 20 76 65 r<LL>(2));. ve
07d0: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e ctor< vector<LL>
07e0: 20 3e 20 78 28 32 2c 20 76 65 63 74 6f 72 3c 4c > x(2, vector<L
07f0: 4c 3e 28 32 29 29 3b 0a 20 20 20 76 5b 30 5d 5b L>(2));. v[0][
0800: 30 5d 20 3d 20 76 5b 31 5d 5b 31 5d 20 3d 20 31 0] = v[1][1] = 1
0810: 3b 0a 20 20 20 78 5b 30 5d 5b 30 5d 20 3d 20 78 ;. x[0][0] = x
0820: 5f 3b 20 78 5b 30 5d 5b 31 5d 20 3d 20 30 3b 0a _; x[0][1] = 0;.
0830: 20 20 20 78 5b 31 5d 5b 30 5d 20 3d 20 31 20 3b x[1][0] = 1 ;
0840: 20 78 5b 31 5d 5b 31 5d 20 3d 20 31 3b 0a 20 20 x[1][1] = 1;.
0850: 20 66 6f 72 28 3b 65 3b 78 3d 4d 41 54 4d 55 4c for(;e;x=MATMUL
0860: 28 78 2c 78 29 2c 65 3e 3e 3d 31 29 0a 20 20 20 (x,x),e>>=1).
0870: 20 20 20 69 66 28 65 26 31 29 0a 20 20 20 20 20 if(e&1).
0880: 20 20 20 20 76 20 3d 20 4d 41 54 4d 55 4c 28 76 v = MATMUL(v
0890: 2c 20 78 29 3b 0a 20 20 20 72 65 74 75 72 6e 20 , x);. return
08a0: 76 5b 31 5d 5b 30 5d 3b 0a 7d 0a 0a 2f 2f 20 77 v[1][0];.}..// w
08b0: 6f 72 6b 73 20 66 6f 72 20 6e 6f 6e 2d 70 72 69 orks for non-pri
08c0: 6d 65 20 4d 4f 44 56 41 4c 0a 4c 4c 20 48 59 50 me MODVAL.LL HYP
08d0: 28 4c 4c 20 78 5f 2c 20 4c 4c 20 65 29 20 2f 2f (LL x_, LL e) //
08e0: 20 65 20 78 5e 30 20 2b 20 28 65 2d 31 29 20 78 e x^0 + (e-1) x
08f0: 5e 31 20 2b 20 2e 2e 2e 20 2b 20 31 20 78 5e 65 ^1 + ... + 1 x^e
0900: 2d 31 20 3d 20 47 45 4f 28 78 2c 31 29 2b 47 45 -1 = GEO(x,1)+GE
0910: 4f 28 78 2c 32 29 2b 2e 2e 2e 2b 47 45 4f 28 78 O(x,2)+...+GEO(x
0920: 2c 65 29 0a 7b 0a 20 20 20 76 65 63 74 6f 72 3c ,e).{. vector<
0930: 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 76 28 vector<LL> > v(
0940: 33 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e 28 33 29 3, vector<LL>(3)
0950: 29 3b 0a 20 20 20 76 65 63 74 6f 72 3c 20 76 65 );. vector< ve
0960: 63 74 6f 72 3c 4c 4c 3e 20 3e 20 78 28 33 2c 20 ctor<LL> > x(3,
0970: 76 65 63 74 6f 72 3c 4c 4c 3e 28 33 29 29 3b 0a vector<LL>(3));.
0980: 20 20 20 76 5b 30 5d 5b 30 5d 20 3d 20 76 5b 31 v[0][0] = v[1
0990: 5d 5b 31 5d 20 3d 20 76 5b 32 5d 5b 32 5d 20 3d ][1] = v[2][2] =
09a0: 20 31 3b 0a 20 20 20 78 5b 30 5d 5b 30 5d 20 3d 1;. x[0][0] =
09b0: 20 78 5f 3b 20 78 5b 30 5d 5b 31 5d 20 3d 20 30 x_; x[0][1] = 0
09c0: 3b 20 78 5b 30 5d 5b 32 5d 20 3d 20 30 3b 0a 20 ; x[0][2] = 0;.
09d0: 20 20 78 5b 31 5d 5b 30 5d 20 3d 20 31 20 3b 20 x[1][0] = 1 ;
09e0: 78 5b 31 5d 5b 31 5d 20 3d 20 31 3b 20 78 5b 31 x[1][1] = 1; x[1
09f0: 5d 5b 32 5d 20 3d 20 30 3b 0a 20 20 20 78 5b 32 ][2] = 0;. x[2
0a00: 5d 5b 30 5d 20 3d 20 30 20 3b 20 78 5b 32 5d 5b ][0] = 0 ; x[2][
0a10: 31 5d 20 3d 20 31 3b 20 78 5b 32 5d 5b 32 5d 20 1] = 1; x[2][2]
0a20: 3d 20 31 3b 0a 20 20 20 65 2b 2b 3b 0a 20 20 20 = 1;. e++;.
0a30: 66 6f 72 28 3b 65 3b 78 3d 4d 41 54 4d 55 4c 28 for(;e;x=MATMUL(
0a40: 78 2c 78 29 2c 65 3e 3e 3d 31 29 0a 20 20 20 20 x,x),e>>=1).
0a50: 20 20 69 66 28 65 26 31 29 0a 20 20 20 20 20 20 if(e&1).
0a60: 20 20 20 76 20 3d 20 4d 41 54 4d 55 4c 28 76 2c v = MATMUL(v,
0a70: 20 78 29 3b 0a 20 20 20 72 65 74 75 72 6e 20 76 x);. return v
0a80: 5b 32 5d 5b 30 5d 3b 0a 7d 0a 2a 2f 0a [2][0];.}.*/.