Artifact f45d60576bba98942dba9a5e275dcaa3ce879344:
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: 78 29 3a 76 61 6c 28 78 25 4d 4f 44 56 41 4c 29 x):val(x%MODVAL)
0140: 20 7b 7d 0a 09 6d 69 6e 74 28 4c 4c 20 20 78 29 {}..mint(LL x)
0150: 3a 76 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b :val(x%MODVAL) {
0160: 7d 0a 7d 3b 0a 6d 69 6e 74 20 6f 70 65 72 61 74 }.};.mint operat
0170: 6f 72 2b 28 6d 69 6e 74 20 78 2c 20 6d 69 6e 74 or+(mint x, mint
0180: 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 2e 76 y) { return x.v
0190: 61 6c 2b 79 2e 76 61 6c 3b 20 7d 0a 6d 69 6e 74 al+y.val; }.mint
01a0: 20 6f 70 65 72 61 74 6f 72 2d 28 6d 69 6e 74 20 operator-(mint
01b0: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 x, mint y) { ret
01c0: 75 72 6e 20 78 2e 76 61 6c 2d 79 2e 76 61 6c 2b urn x.val-y.val+
01d0: 4d 4f 44 56 41 4c 3b 20 7d 0a 6d 69 6e 74 20 6f MODVAL; }.mint o
01e0: 70 65 72 61 74 6f 72 2a 28 6d 69 6e 74 20 78 2c perator*(mint x,
01f0: 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 mint y) { retur
0200: 6e 20 4c 4c 28 78 2e 76 61 6c 29 2a 79 2e 76 61 n LL(x.val)*y.va
0210: 6c 3b 20 7d 0a 6d 69 6e 74 20 50 4f 57 28 6d 69 l; }.mint POW(mi
0220: 6e 74 20 78 2c 20 69 6e 74 20 65 29 20 7b 0a 09 nt x, int e) {..
0230: 6d 69 6e 74 20 76 20 3d 20 31 3b 0a 09 66 6f 72 mint v = 1;..for
0240: 28 3b 65 3b 78 3d 78 2a 78 2c 65 3e 3e 3d 31 29 (;e;x=x*x,e>>=1)
0250: 0a 09 09 69 66 28 65 26 31 29 0a 09 09 09 76 3d ...if(e&1)....v=
0260: 76 2a 78 3b 0a 09 72 65 74 75 72 6e 20 76 3b 0a v*x;..return v;.
0270: 7d 0a 6d 69 6e 74 20 6f 70 65 72 61 74 6f 72 2f }.mint operator/
0280: 28 6d 69 6e 74 20 78 2c 20 6d 69 6e 74 20 79 29 (mint x, mint y)
0290: 20 7b 20 72 65 74 75 72 6e 20 78 20 2a 20 50 4f { return x * PO
02a0: 57 28 79 2c 20 4d 4f 44 56 41 4c 2d 32 29 3b 20 W(y, MODVAL-2);
02b0: 7d 0a 0a 76 65 63 74 6f 72 3c 6d 69 6e 74 3e 20 }..vector<mint>
02c0: 46 41 43 5f 28 31 2c 31 29 3b 0a 76 6f 69 64 20 FAC_(1,1);.void
02d0: 46 41 43 5f 49 4e 49 54 28 69 6e 74 20 6e 29 20 FAC_INIT(int n)
02e0: 7b 20 77 68 69 6c 65 28 20 46 41 43 5f 2e 73 69 { while( FAC_.si
02f0: 7a 65 28 29 3c 3d 6e 20 29 20 46 41 43 5f 2e 70 ze()<=n ) FAC_.p
0300: 75 73 68 5f 62 61 63 6b 28 20 46 41 43 5f 2e 62 ush_back( FAC_.b
0310: 61 63 6b 28 29 2a 46 41 43 5f 2e 73 69 7a 65 28 ack()*FAC_.size(
0320: 29 20 29 3b 20 7d 0a 6d 69 6e 74 20 46 41 43 28 ) ); }.mint FAC(
0330: 6d 69 6e 74 20 78 29 20 20 20 20 20 20 20 7b 20 mint x) {
0340: 72 65 74 75 72 6e 20 46 41 43 5f 5b 78 2e 76 61 return FAC_[x.va
0350: 6c 5d 3b 20 7d 0a 6d 69 6e 74 20 43 28 6d 69 6e l]; }.mint C(min
0360: 74 20 6e 2c 20 6d 69 6e 74 20 6b 29 20 7b 20 72 t n, mint k) { r
0370: 65 74 75 72 6e 20 6b 2e 76 61 6c 3c 30 20 7c 7c eturn k.val<0 ||
0380: 20 6e 2e 76 61 6c 3c 6b 2e 76 61 6c 20 3f 20 30 n.val<k.val ? 0
0390: 20 3a 20 46 41 43 28 6e 29 20 2f 20 28 46 41 43 : FAC(n) / (FAC
03a0: 28 6b 29 20 2a 20 46 41 43 28 6e 2d 6b 29 29 3b (k) * FAC(n-k));
03b0: 20 7d 0a 0a 2f 2a 0a 2f 2f 20 4d 4f 44 56 41 4c }../*.// MODVAL
03c0: 20 6d 75 73 74 20 62 65 20 61 20 70 72 69 6d 65 must be a prime
03d0: 21 21 0a 4c 4c 20 47 53 53 28 4c 4c 20 6b 2c 20 !!.LL GSS(LL k,
03e0: 4c 4c 20 62 2c 20 4c 4c 20 65 29 20 2f 2f 20 6b LL b, LL e) // k
03f0: 5e 62 20 2b 20 6b 5e 62 2b 31 20 2b 20 2e 2e 2e ^b + k^b+1 + ...
0400: 20 2b 20 6b 5e 65 0a 7b 0a 09 69 66 28 20 62 20 + k^e.{..if( b
0410: 3e 20 20 65 20 29 20 72 65 74 75 72 6e 20 30 3b > e ) return 0;
0420: 0a 09 69 66 28 20 6b 20 3c 3d 20 31 20 29 20 72 ..if( k <= 1 ) r
0430: 65 74 75 72 6e 20 6b 2a 28 65 2d 62 2b 31 29 3b eturn k*(e-b+1);
0440: 0a 09 72 65 74 75 72 6e 20 44 49 56 28 53 55 42 ..return DIV(SUB
0450: 28 50 4f 57 28 6b 2c 20 65 2b 31 29 2c 20 50 4f (POW(k, e+1), PO
0460: 57 28 6b 2c 62 29 29 2c 20 6b 2d 31 29 3b 0a 7d W(k,b)), k-1);.}
0470: 0a 0a 4c 4c 20 43 70 61 73 63 61 6c 28 4c 4c 20 ..LL Cpascal(LL
0480: 6e 2c 20 4c 4c 20 6b 29 0a 7b 0a 09 76 65 63 74 n, LL k).{..vect
0490: 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e or< vector<LL> >
04a0: 20 63 28 6e 2b 31 2c 20 76 65 63 74 6f 72 3c 4c c(n+1, vector<L
04b0: 4c 3e 28 6b 2b 31 29 29 3b 0a 09 66 6f 72 28 4c L>(k+1));..for(L
04c0: 4c 20 6e 6e 3d 31 3b 20 6e 6e 3c 3d 6e 3b 20 2b L nn=1; nn<=n; +
04d0: 2b 6e 6e 29 0a 09 09 66 6f 72 28 4c 4c 20 6b 6b +nn)...for(LL kk
04e0: 3d 30 3b 20 6b 6b 3c 3d 6d 69 6e 28 6e 6e 2c 6b =0; kk<=min(nn,k
04f0: 29 3b 20 2b 2b 6b 6b 29 0a 09 09 09 63 5b 6e 6e ); ++kk)....c[nn
0500: 5d 5b 6b 6b 5d 20 3d 20 6b 6b 3d 3d 30 20 7c 7c ][kk] = kk==0 ||
0510: 20 6b 6b 3d 3d 6e 6e 20 3f 20 31 20 3a 20 41 44 kk==nn ? 1 : AD
0520: 44 28 63 5b 6e 6e 2d 31 5d 5b 6b 6b 2d 31 5d 2c D(c[nn-1][kk-1],
0530: 20 63 5b 6e 6e 2d 31 5d 5b 6b 6b 5d 29 3b 0a 09 c[nn-1][kk]);..
0540: 72 65 74 75 72 6e 20 63 5b 6e 5d 5b 6b 5d 3b 0a return c[n][k];.
0550: 7d 0a 0a 76 65 63 74 6f 72 3c 20 76 65 63 74 6f }..vector< vecto
0560: 72 3c 4c 4c 3e 20 3e 20 4d 41 54 4d 55 4c 28 76 r<LL> > MATMUL(v
0570: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c ector< vector<LL
0580: 3e 20 3e 26 20 61 2c 20 76 65 63 74 6f 72 3c 20 > >& a, vector<
0590: 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 26 20 62 29 vector<LL> >& b)
05a0: 0a 7b 0a 20 20 20 69 6e 74 20 4e 20 3d 20 61 2e .{. int N = a.
05b0: 73 69 7a 65 28 29 3b 0a 20 20 20 76 65 63 74 6f size();. vecto
05c0: 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 r< vector<LL> >
05d0: 63 28 4e 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e 28 c(N, vector<LL>(
05e0: 4e 29 29 3b 0a 20 20 20 66 6f 72 28 69 6e 74 20 N));. for(int
05f0: 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0a 20 i=0; i<N; ++i).
0600: 20 20 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a for(int j=0; j
0610: 3c 4e 3b 20 2b 2b 6a 29 0a 20 20 20 66 6f 72 28 <N; ++j). for(
0620: 69 6e 74 20 6b 3d 30 3b 20 6b 3c 4e 3b 20 2b 2b int k=0; k<N; ++
0630: 6b 29 0a 20 20 20 20 20 20 63 5b 69 5d 5b 6a 5d k). c[i][j]
0640: 20 3d 20 41 44 44 28 63 5b 69 5d 5b 6a 5d 2c 20 = ADD(c[i][j],
0650: 4d 55 4c 28 61 5b 69 5d 5b 6b 5d 2c 62 5b 6b 5d MUL(a[i][k],b[k]
0660: 5b 6a 5d 29 29 3b 0a 20 20 20 72 65 74 75 72 6e [j]));. return
0670: 20 63 3b 0a 7d 0a 0a 2f 2f 20 77 6f 72 6b 73 20 c;.}..// works
0680: 66 6f 72 20 6e 6f 6e 2d 70 72 69 6d 65 20 4d 4f for non-prime MO
0690: 44 56 41 4c 0a 4c 4c 20 47 45 4f 28 4c 4c 20 78 DVAL.LL GEO(LL x
06a0: 5f 2c 20 4c 4c 20 65 29 20 2f 2f 20 78 5e 30 20 _, LL e) // x^0
06b0: 2b 20 78 5e 31 20 2b 20 2e 2e 2e 20 2b 20 78 5e + x^1 + ... + x^
06c0: 65 2d 31 0a 7b 0a 20 20 20 76 65 63 74 6f 72 3c e-1.{. vector<
06d0: 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 76 28 vector<LL> > v(
06e0: 32 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e 28 32 29 2, vector<LL>(2)
06f0: 29 3b 0a 20 20 20 76 65 63 74 6f 72 3c 20 76 65 );. vector< ve
0700: 63 74 6f 72 3c 4c 4c 3e 20 3e 20 78 28 32 2c 20 ctor<LL> > x(2,
0710: 76 65 63 74 6f 72 3c 4c 4c 3e 28 32 29 29 3b 0a vector<LL>(2));.
0720: 20 20 20 76 5b 30 5d 5b 30 5d 20 3d 20 76 5b 31 v[0][0] = v[1
0730: 5d 5b 31 5d 20 3d 20 31 3b 0a 20 20 20 78 5b 30 ][1] = 1;. x[0
0740: 5d 5b 30 5d 20 3d 20 78 5f 3b 20 78 5b 30 5d 5b ][0] = x_; x[0][
0750: 31 5d 20 3d 20 30 3b 0a 20 20 20 78 5b 31 5d 5b 1] = 0;. x[1][
0760: 30 5d 20 3d 20 31 20 3b 20 78 5b 31 5d 5b 31 5d 0] = 1 ; x[1][1]
0770: 20 3d 20 31 3b 0a 20 20 20 66 6f 72 28 3b 65 3b = 1;. for(;e;
0780: 78 3d 4d 41 54 4d 55 4c 28 78 2c 78 29 2c 65 3e x=MATMUL(x,x),e>
0790: 3e 3d 31 29 0a 20 20 20 20 20 20 69 66 28 65 26 >=1). if(e&
07a0: 31 29 0a 20 20 20 20 20 20 20 20 20 76 20 3d 20 1). v =
07b0: 4d 41 54 4d 55 4c 28 76 2c 20 78 29 3b 0a 20 20 MATMUL(v, x);.
07c0: 20 72 65 74 75 72 6e 20 76 5b 31 5d 5b 30 5d 3b return v[1][0];
07d0: 0a 7d 0a 0a 2f 2f 20 77 6f 72 6b 73 20 66 6f 72 .}..// works for
07e0: 20 6e 6f 6e 2d 70 72 69 6d 65 20 4d 4f 44 56 41 non-prime MODVA
07f0: 4c 0a 4c 4c 20 48 59 50 28 4c 4c 20 78 5f 2c 20 L.LL HYP(LL x_,
0800: 4c 4c 20 65 29 20 2f 2f 20 65 20 78 5e 30 20 2b LL e) // e x^0 +
0810: 20 28 65 2d 31 29 20 78 5e 31 20 2b 20 2e 2e 2e (e-1) x^1 + ...
0820: 20 2b 20 31 20 78 5e 65 2d 31 20 3d 20 47 45 4f + 1 x^e-1 = GEO
0830: 28 78 2c 31 29 2b 47 45 4f 28 78 2c 32 29 2b 2e (x,1)+GEO(x,2)+.
0840: 2e 2e 2b 47 45 4f 28 78 2c 65 29 0a 7b 0a 20 20 ..+GEO(x,e).{.
0850: 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c vector< vector<
0860: 4c 4c 3e 20 3e 20 76 28 33 2c 20 76 65 63 74 6f LL> > v(3, vecto
0870: 72 3c 4c 4c 3e 28 33 29 29 3b 0a 20 20 20 76 65 r<LL>(3));. ve
0880: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e ctor< vector<LL>
0890: 20 3e 20 78 28 33 2c 20 76 65 63 74 6f 72 3c 4c > x(3, vector<L
08a0: 4c 3e 28 33 29 29 3b 0a 20 20 20 76 5b 30 5d 5b L>(3));. v[0][
08b0: 30 5d 20 3d 20 76 5b 31 5d 5b 31 5d 20 3d 20 76 0] = v[1][1] = v
08c0: 5b 32 5d 5b 32 5d 20 3d 20 31 3b 0a 20 20 20 78 [2][2] = 1;. x
08d0: 5b 30 5d 5b 30 5d 20 3d 20 78 5f 3b 20 78 5b 30 [0][0] = x_; x[0
08e0: 5d 5b 31 5d 20 3d 20 30 3b 20 78 5b 30 5d 5b 32 ][1] = 0; x[0][2
08f0: 5d 20 3d 20 30 3b 0a 20 20 20 78 5b 31 5d 5b 30 ] = 0;. x[1][0
0900: 5d 20 3d 20 31 20 3b 20 78 5b 31 5d 5b 31 5d 20 ] = 1 ; x[1][1]
0910: 3d 20 31 3b 20 78 5b 31 5d 5b 32 5d 20 3d 20 30 = 1; x[1][2] = 0
0920: 3b 0a 20 20 20 78 5b 32 5d 5b 30 5d 20 3d 20 30 ;. x[2][0] = 0
0930: 20 3b 20 78 5b 32 5d 5b 31 5d 20 3d 20 31 3b 20 ; x[2][1] = 1;
0940: 78 5b 32 5d 5b 32 5d 20 3d 20 31 3b 0a 20 20 20 x[2][2] = 1;.
0950: 65 2b 2b 3b 0a 20 20 20 66 6f 72 28 3b 65 3b 78 e++;. for(;e;x
0960: 3d 4d 41 54 4d 55 4c 28 78 2c 78 29 2c 65 3e 3e =MATMUL(x,x),e>>
0970: 3d 31 29 0a 20 20 20 20 20 20 69 66 28 65 26 31 =1). if(e&1
0980: 29 0a 20 20 20 20 20 20 20 20 20 76 20 3d 20 4d ). v = M
0990: 41 54 4d 55 4c 28 76 2c 20 78 29 3b 0a 20 20 20 ATMUL(v, x);.
09a0: 72 65 74 75 72 6e 20 76 5b 32 5d 5b 30 5d 3b 0a return v[2][0];.
09b0: 7d 0a 2a 2f 0a }.*/.