Artifact a7ea12621faece166b9ab971f1ed03c96d22059a:
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 4c 4c 28 46 41 AC_.back()*LL(FA
0430: 43 5f 2e 73 69 7a 65 28 29 29 20 29 3b 20 72 65 C_.size()) ); re
0440: 74 75 72 6e 20 46 41 43 5f 5b 6e 5d 3b 20 7d 0a turn FAC_[n]; }.
0450: 0a 2f 2f 20 6e 43 6b 20 3a 3a 20 4f 28 6c 6f 67 .// nCk :: O(log
0460: 20 4d 4f 44 56 41 4c 29 20 74 69 6d 65 2c 20 4f MODVAL) time, O
0470: 28 6e 29 20 73 70 61 63 65 2e 0a 6d 69 6e 74 20 (n) space..mint
0480: 43 28 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 20 7b 20 C(LL n, LL k) {
0490: 72 65 74 75 72 6e 20 6b 3c 30 20 7c 7c 20 6e 3c return k<0 || n<
04a0: 6b 20 3f 20 30 20 3a 20 46 41 43 28 6e 29 20 2f k ? 0 : FAC(n) /
04b0: 20 28 46 41 43 28 6b 29 20 2a 20 46 41 43 28 6e (FAC(k) * FAC(n
04c0: 2d 6b 29 29 3b 20 7d 0a 0a 2f 2f 20 6e 43 6b 20 -k)); }..// nCk
04d0: 3a 3a 20 4f 28 31 29 20 74 69 6d 65 2c 20 4f 28 :: O(1) time, O(
04e0: 6e 5e 32 29 20 73 70 61 63 65 2e 0a 76 65 63 74 n^2) space..vect
04f0: 6f 72 3c 20 76 65 63 74 6f 72 3c 6d 69 6e 74 3e or< vector<mint>
0500: 20 3e 20 43 50 5f 3b 0a 6d 69 6e 74 20 43 28 69 > CP_;.mint C(i
0510: 6e 74 20 6e 2c 20 69 6e 74 20 6b 29 20 7b 0a 09 nt n, int k) {..
0520: 77 68 69 6c 65 28 20 43 50 5f 2e 73 69 7a 65 28 while( CP_.size(
0530: 29 20 3c 3d 20 6e 20 29 20 7b 0a 09 09 69 6e 74 ) <= n ) {...int
0540: 20 6e 6e 20 3d 20 43 50 5f 2e 73 69 7a 65 28 29 nn = CP_.size()
0550: 3b 0a 09 09 43 50 5f 2e 70 75 73 68 5f 62 61 63 ;...CP_.push_bac
0560: 6b 28 76 65 63 74 6f 72 3c 6d 69 6e 74 3e 28 6e k(vector<mint>(n
0570: 6e 2b 31 2c 31 29 29 3b 0a 09 09 66 6f 72 28 69 n+1,1));...for(i
0580: 6e 74 20 6b 6b 3d 31 3b 20 6b 6b 3c 6e 6e 3b 20 nt kk=1; kk<nn;
0590: 2b 2b 6b 6b 29 0a 09 09 09 43 50 5f 5b 6e 6e 5d ++kk)....CP_[nn]
05a0: 5b 6b 6b 5d 20 3d 20 43 50 5f 5b 6e 6e 2d 31 5d [kk] = CP_[nn-1]
05b0: 5b 6b 6b 2d 31 5d 20 2b 20 43 50 5f 5b 6e 6e 2d [kk-1] + CP_[nn-
05c0: 31 5d 5b 6b 6b 5d 3b 0a 09 7d 0a 09 72 65 74 75 1][kk];..}..retu
05d0: 72 6e 20 6b 3c 30 20 7c 7c 20 6e 3c 6b 20 3f 20 rn k<0 || n<k ?
05e0: 30 20 3a 20 43 50 5f 5b 6e 5d 5b 6b 5d 3b 0a 7d 0 : CP_[n][k];.}
05f0: 0a 0a 2f 2f 20 4f 28 6c 6f 67 20 4d 4f 44 56 41 ..// O(log MODVA
0600: 4c 29 2c 20 4d 4f 44 56 41 4c 20 6d 75 73 74 20 L), MODVAL must
0610: 62 65 20 70 72 69 6d 65 3a 20 6b 5e 62 20 2b 20 be prime: k^b +
0620: 6b 5e 62 2b 31 20 2b 20 2e 2e 2e 20 2b 20 6b 5e k^b+1 + ... + k^
0630: 65 0a 6d 69 6e 74 20 47 53 53 28 6d 69 6e 74 20 e.mint GSS(mint
0640: 6b 2c 20 4c 4c 20 62 2c 20 4c 4c 20 65 29 20 0a k, LL b, LL e) .
0650: 7b 0a 09 69 66 28 20 62 20 3e 20 65 20 29 20 72 {..if( b > e ) r
0660: 65 74 75 72 6e 20 30 3b 0a 09 69 66 28 20 6b 2e eturn 0;..if( k.
0670: 76 61 6c 20 3c 3d 20 31 20 29 20 72 65 74 75 72 val <= 1 ) retur
0680: 6e 20 6b 2a 28 65 2d 62 2b 31 29 3b 0a 09 72 65 n k*(e-b+1);..re
0690: 74 75 72 6e 20 28 50 4f 57 28 6b 2c 20 65 2b 31 turn (POW(k, e+1
06a0: 29 20 2d 20 50 4f 57 28 6b 2c 62 29 29 20 2f 20 ) - POW(k,b)) /
06b0: 28 6b 2d 31 29 3b 0a 7d 0a 0a 2f 2f 20 68 74 74 (k-1);.}..// htt
06c0: 70 73 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 ps://en.wikipedi
06d0: 61 2e 6f 72 67 2f 77 69 6b 69 2f 53 74 69 72 6c a.org/wiki/Stirl
06e0: 69 6e 67 5f 6e 75 6d 62 65 72 73 5f 6f 66 5f 74 ing_numbers_of_t
06f0: 68 65 5f 73 65 63 6f 6e 64 5f 6b 69 6e 64 0a 2f he_second_kind./
0700: 2f 20 4e 75 6d 62 65 72 20 6f 66 20 77 61 79 73 / Number of ways
0710: 20 74 6f 20 73 70 6c 69 74 20 7c 6e 7c 20 6c 61 to split |n| la
0720: 62 65 6c 6c 65 64 20 6f 62 6a 65 63 74 73 20 74 belled objects t
0730: 6f 20 65 78 61 63 74 6c 79 20 7c 6b 7c 20 75 6e o exactly |k| un
0740: 6c 61 62 62 6c 65 64 20 73 65 74 73 2e 0a 2f 2f labbled sets..//
0750: 20 20 20 20 2a 20 49 66 20 77 65 20 64 72 6f 70 * If we drop
0760: 20 22 65 78 61 63 74 6c 79 22 2c 20 74 68 65 20 "exactly", the
0770: 61 6e 73 77 65 72 20 77 61 73 20 6b 5e 6e 0a 2f answer was k^n./
0780: 2f 20 20 20 20 2a 20 49 66 20 77 65 20 73 70 6c / * If we spl
0790: 69 74 20 74 6f 20 22 6c 61 62 65 6c 65 64 22 20 it to "labeled"
07a0: 73 65 74 73 2c 20 74 68 65 20 61 6e 73 77 65 72 sets, the answer
07b0: 20 77 69 6c 6c 20 62 65 20 53 28 6e 2c 6b 29 2a will be S(n,k)*
07c0: 6b 21 0a 2f 2f 20 20 20 20 2a 20 49 66 20 75 6e k!.// * If un
07d0: 6c 61 62 65 6c 65 64 2f 75 6e 6c 61 62 65 6c 64 labeled/unlabeld
07e0: 20 62 61 72 2d 61 6e 64 2d 62 61 6c 6c 2d 61 72 bar-and-ball-ar
07f0: 72 61 6e 67 69 6e 67 20 61 72 67 75 6d 65 6e 74 ranging argument
0800: 2e 0a 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 ..vector< vector
0810: 3c 6d 69 6e 74 3e 20 3e 20 53 50 5f 3b 0a 6d 69 <mint> > SP_;.mi
0820: 6e 74 20 53 28 69 6e 74 20 6e 2c 20 69 6e 74 20 nt S(int n, int
0830: 6b 29 20 7b 0a 09 77 68 69 6c 65 20 28 53 50 5f k) {..while (SP_
0840: 2e 73 69 7a 65 28 29 20 3c 3d 20 6e 29 20 7b 0a .size() <= n) {.
0850: 09 09 69 6e 74 20 6e 6e 20 3d 20 53 50 5f 2e 73 ..int nn = SP_.s
0860: 69 7a 65 28 29 3b 0a 09 09 53 50 5f 2e 70 75 73 ize();...SP_.pus
0870: 68 5f 62 61 63 6b 28 76 65 63 74 6f 72 3c 6d 69 h_back(vector<mi
0880: 6e 74 3e 28 6e 6e 20 2b 20 31 2c 20 31 29 29 3b nt>(nn + 1, 1));
0890: 0a 09 09 66 6f 72 20 28 69 6e 74 20 6b 6b 20 3d ...for (int kk =
08a0: 20 32 3b 20 6b 6b 3c 6e 6e 3b 20 2b 2b 6b 6b 29 2; kk<nn; ++kk)
08b0: 0a 09 09 09 53 50 5f 5b 6e 6e 5d 5b 6b 6b 5d 20 ....SP_[nn][kk]
08c0: 3d 20 53 50 5f 5b 6e 6e 20 2d 20 31 5d 5b 6b 6b = SP_[nn - 1][kk
08d0: 20 2d 20 31 5d 20 2b 20 6b 6b 2a 53 50 5f 5b 6e - 1] + kk*SP_[n
08e0: 6e 20 2d 20 31 5d 5b 6b 6b 5d 3b 0a 09 7d 0a 09 n - 1][kk];..}..
08f0: 72 65 74 75 72 6e 20 6b 3c 3d 30 20 7c 7c 20 6e return k<=0 || n
0900: 3c 6b 20 3f 20 30 20 3a 20 53 50 5f 5b 6e 5d 5b <k ? 0 : SP_[n][
0910: 6b 5d 3b 0a 7d 0a k];.}.