0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 74 75 70 6c 65 3e 0d 0a 75 73 69 6e 67 20 6e <tuple>..using n
0150: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
0160: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
0170: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0180: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0190: 50 3b 0d 0a 0d 0a 73 74 61 74 69 63 20 63 6f 6e P;....static con
01a0: 73 74 20 75 6e 73 69 67 6e 65 64 20 4d 4f 44 56 st unsigned MODV
01b0: 41 4c 20 3d 20 31 30 30 30 30 30 30 30 30 37 3b AL = 1000000007;
01c0: 0d 0a 73 74 72 75 63 74 20 6d 69 6e 74 0d 0a 7b ..struct mint..{
01d0: 0d 0a 09 75 6e 73 69 67 6e 65 64 20 76 61 6c 3b ...unsigned val;
01e0: 0d 0a 09 6d 69 6e 74 28 29 3a 76 61 6c 28 30 29 ...mint():val(0)
01f0: 7b 7d 0d 0a 09 6d 69 6e 74 28 69 6e 74 20 20 20 {}...mint(int
0200: 20 20 20 78 29 3a 76 61 6c 28 78 25 4d 4f 44 56 x):val(x%MODV
0210: 41 4c 29 20 7b 7d 0d 0a 09 6d 69 6e 74 28 75 6e AL) {}...mint(un
0220: 73 69 67 6e 65 64 20 78 29 3a 76 61 6c 28 78 25 signed x):val(x%
0230: 4d 4f 44 56 41 4c 29 20 7b 7d 0d 0a 09 6d 69 6e MODVAL) {}...min
0240: 74 28 4c 4c 20 20 20 20 20 20 20 78 29 3a 76 61 t(LL x):va
0250: 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b 7d 0d 0a l(x%MODVAL) {}..
0260: 7d 3b 0d 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 };..mint& operat
0270: 6f 72 2b 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 or+=(mint& x, mi
0280: 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 nt y) { return x
0290: 20 3d 20 78 2e 76 61 6c 2b 79 2e 76 61 6c 3b 20 = x.val+y.val;
02a0: 7d 0d 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 6f }..mint& operato
02b0: 72 2d 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 6e r-=(mint& x, min
02c0: 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 20 t y) { return x
02d0: 3d 20 78 2e 76 61 6c 2d 79 2e 76 61 6c 2b 4d 4f = x.val-y.val+MO
02e0: 44 56 41 4c 3b 20 7d 0d 0a 6d 69 6e 74 26 20 6f DVAL; }..mint& o
02f0: 70 65 72 61 74 6f 72 2a 3d 28 6d 69 6e 74 26 20 perator*=(mint&
0300: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 x, mint y) { ret
0310: 75 72 6e 20 78 20 3d 20 4c 4c 28 78 2e 76 61 6c urn x = LL(x.val
0320: 29 2a 79 2e 76 61 6c 3b 20 7d 0d 0a 6d 69 6e 74 )*y.val; }..mint
0330: 20 6f 70 65 72 61 74 6f 72 2b 28 6d 69 6e 74 20 operator+(mint
0340: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 x, mint y) { ret
0350: 75 72 6e 20 78 2b 3d 79 3b 20 7d 0d 0a 6d 69 6e urn x+=y; }..min
0360: 74 20 6f 70 65 72 61 74 6f 72 2d 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 2d 3d 79 3b 20 7d 0d 0a 6d 69 turn x-=y; }..mi
0390: 6e 74 20 6f 70 65 72 61 74 6f 72 2a 28 6d 69 6e nt operator*(min
03a0: 74 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 t x, mint y) { r
03b0: 65 74 75 72 6e 20 78 2a 3d 79 3b 20 7d 0d 0a 0d eturn x*=y; }...
03c0: 0a 6d 69 6e 74 20 50 4f 57 28 6d 69 6e 74 20 78 .mint POW(mint x
03d0: 2c 20 4c 4c 20 65 29 20 7b 20 6d 69 6e 74 20 76 , LL e) { mint v
03e0: 3d 31 3b 20 66 6f 72 28 3b 65 3b 78 2a 3d 78 2c =1; for(;e;x*=x,
03f0: 65 3e 3e 3d 31 29 20 69 66 28 65 26 31 29 20 76 e>>=1) if(e&1) v
0400: 2a 3d 78 3b 20 72 65 74 75 72 6e 20 76 3b 20 7d *=x; return v; }
0410: 0d 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 6f 72 ..mint& operator
0420: 2f 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 6e 74 /=(mint& x, mint
0430: 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 20 2a y) { return x *
0440: 3d 20 50 4f 57 28 79 2c 20 4d 4f 44 56 41 4c 2d = POW(y, MODVAL-
0450: 32 29 3b 20 7d 0d 0a 6d 69 6e 74 20 6f 70 65 72 2); }..mint oper
0460: 61 74 6f 72 2f 28 6d 69 6e 74 20 78 2c 20 6d 69 ator/(mint x, mi
0470: 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 nt y) { return x
0480: 2f 3d 79 3b 20 7d 0d 0a 0d 0a 76 65 63 74 6f 72 /=y; }....vector
0490: 3c 6d 69 6e 74 3e 20 46 41 43 5f 28 31 2c 31 29 <mint> FAC_(1,1)
04a0: 3b 0d 0a 6d 69 6e 74 20 46 41 43 28 4c 4c 20 6e ;..mint FAC(LL n
04b0: 29 20 7b 20 77 68 69 6c 65 28 20 46 41 43 5f 2e ) { while( FAC_.
04c0: 73 69 7a 65 28 29 3c 3d 6e 20 29 20 46 41 43 5f size()<=n ) FAC_
04d0: 2e 70 75 73 68 5f 62 61 63 6b 28 20 46 41 43 5f .push_back( FAC_
04e0: 2e 62 61 63 6b 28 29 2a 46 41 43 5f 2e 73 69 7a .back()*FAC_.siz
04f0: 65 28 29 20 29 3b 20 72 65 74 75 72 6e 20 46 41 e() ); return FA
0500: 43 5f 5b 73 69 7a 65 5f 74 28 6e 29 5d 3b 20 7d C_[size_t(n)]; }
0510: 0d 0a 0d 0a 76 65 63 74 6f 72 3c 20 76 65 63 74 ....vector< vect
0520: 6f 72 3c 6d 69 6e 74 3e 20 3e 20 43 50 5f 3b 0d or<mint> > CP_;.
0530: 0a 6d 69 6e 74 20 43 28 69 6e 74 20 6e 2c 20 69 .mint C(int n, i
0540: 6e 74 20 6b 29 20 7b 0d 0a 09 77 68 69 6c 65 28 nt k) {...while(
0550: 20 43 50 5f 2e 73 69 7a 65 28 29 20 3c 3d 20 6e CP_.size() <= n
0560: 20 29 20 7b 0d 0a 09 09 69 6e 74 20 6e 6e 20 3d ) {....int nn =
0570: 20 43 50 5f 2e 73 69 7a 65 28 29 3b 0d 0a 09 09 CP_.size();....
0580: 43 50 5f 2e 70 75 73 68 5f 62 61 63 6b 28 76 65 CP_.push_back(ve
0590: 63 74 6f 72 3c 6d 69 6e 74 3e 28 6e 6e 2b 31 2c ctor<mint>(nn+1,
05a0: 31 29 29 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 1));....for(int
05b0: 6b 6b 3d 31 3b 20 6b 6b 3c 6e 6e 3b 20 2b 2b 6b kk=1; kk<nn; ++k
05c0: 6b 29 0d 0a 09 09 09 43 50 5f 5b 6e 6e 5d 5b 6b k).....CP_[nn][k
05d0: 6b 5d 20 3d 20 43 50 5f 5b 6e 6e 2d 31 5d 5b 6b k] = CP_[nn-1][k
05e0: 6b 2d 31 5d 20 2b 20 43 50 5f 5b 6e 6e 2d 31 5d k-1] + CP_[nn-1]
05f0: 5b 6b 6b 5d 3b 0d 0a 09 7d 0d 0a 09 72 65 74 75 [kk];...}...retu
0600: 72 6e 20 6b 3c 30 20 7c 7c 20 6e 3c 6b 20 3f 20 rn k<0 || n<k ?
0610: 30 20 3a 20 43 50 5f 5b 6e 5d 5b 6b 5d 3b 0d 0a 0 : CP_[n][k];..
0620: 7d 0d 0a 0d 0a 63 6c 61 73 73 20 54 77 6f 45 6e }....class TwoEn
0630: 74 72 61 6e 63 65 73 20 7b 20 70 75 62 6c 69 63 trances { public
0640: 3a 0d 0a 09 69 6e 74 20 63 6f 75 6e 74 28 76 65 :...int count(ve
0650: 63 74 6f 72 20 3c 69 6e 74 3e 20 61 2c 20 76 65 ctor <int> a, ve
0660: 63 74 6f 72 20 3c 69 6e 74 3e 20 62 2c 20 69 6e ctor <int> b, in
0670: 74 20 73 31 2c 20 69 6e 74 20 73 32 29 0d 0a 09 t s1, int s2)...
0680: 7b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 4e {....const int N
0690: 20 3d 20 61 2e 73 69 7a 65 28 29 20 2b 20 31 3b = a.size() + 1;
06a0: 0d 0a 0d 0a 09 09 2f 2f 20 47 72 61 70 68 0d 0a ......// Graph..
06b0: 09 09 76 65 63 74 6f 72 3c 76 65 63 74 6f 72 3c ..vector<vector<
06c0: 69 6e 74 3e 3e 20 67 28 4e 29 3b 0d 0a 09 09 66 int>> g(N);....f
06d0: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 61 2e or(int i=0; i<a.
06e0: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a size(); ++i) {..
06f0: 09 09 09 67 5b 61 5b 69 5d 5d 2e 70 75 73 68 5f ...g[a[i]].push_
0700: 62 61 63 6b 28 62 5b 69 5d 29 3b 0d 0a 09 09 09 back(b[i]);.....
0710: 67 5b 62 5b 69 5d 5d 2e 70 75 73 68 5f 62 61 63 g[b[i]].push_bac
0720: 6b 28 61 5b 69 5d 29 3b 0d 0a 09 09 7d 0d 0a 0d k(a[i]);....}...
0730: 0a 09 09 2f 2f 20 54 72 65 65 20 28 61 73 20 72 ...// Tree (as r
0740: 6f 6f 74 3d 73 31 29 0d 0a 09 09 76 65 63 74 6f oot=s1)....vecto
0750: 72 3c 76 65 63 74 6f 72 3c 69 6e 74 3e 3e 20 63 r<vector<int>> c
0760: 68 69 6c 64 72 65 6e 28 4e 29 3b 0d 0a 09 09 76 hildren(N);....v
0770: 65 63 74 6f 72 3c 69 6e 74 3e 20 70 61 72 65 6e ector<int> paren
0780: 74 28 4e 2c 20 2d 31 29 3b 0d 0a 09 09 76 65 63 t(N, -1);....vec
0790: 74 6f 72 3c 69 6e 74 3e 20 74 72 65 65 5f 73 69 tor<int> tree_si
07a0: 7a 65 28 4e 29 3b 0d 0a 09 09 66 75 6e 63 74 69 ze(N);....functi
07b0: 6f 6e 3c 69 6e 74 28 69 6e 74 2c 69 6e 74 29 3e on<int(int,int)>
07c0: 20 72 65 63 3b 20 72 65 63 20 3d 20 5b 26 5d 28 rec; rec = [&](
07d0: 69 6e 74 20 70 72 65 2c 20 69 6e 74 20 76 29 20 int pre, int v)
07e0: 7b 0d 0a 09 09 09 69 6e 74 20 73 75 62 5f 73 69 {.....int sub_si
07f0: 7a 65 20 3d 20 31 3b 0d 0a 09 09 09 66 6f 72 28 ze = 1;.....for(
0800: 61 75 74 6f 20 75 3a 20 67 5b 76 5d 29 20 69 66 auto u: g[v]) if
0810: 28 75 20 21 3d 20 70 72 65 29 20 7b 0d 0a 09 09 (u != pre) {....
0820: 09 09 63 68 69 6c 64 72 65 6e 5b 76 5d 2e 70 75 ..children[v].pu
0830: 73 68 5f 62 61 63 6b 28 75 29 3b 0d 0a 09 09 09 sh_back(u);.....
0840: 09 70 61 72 65 6e 74 5b 75 5d 20 3d 20 76 3b 0d .parent[u] = v;.
0850: 0a 09 09 09 09 73 75 62 5f 73 69 7a 65 20 2b 3d .....sub_size +=
0860: 20 72 65 63 28 76 2c 20 75 29 3b 0d 0a 09 09 09 rec(v, u);.....
0870: 7d 0d 0a 09 09 09 74 72 65 65 5f 73 69 7a 65 5b }.....tree_size[
0880: 76 5d 20 3d 20 73 75 62 5f 73 69 7a 65 3b 0d 0a v] = sub_size;..
0890: 09 09 7d 3b 0d 0a 09 09 72 65 63 28 2d 31 2c 20 ..};....rec(-1,
08a0: 73 31 29 3b 0d 0a 0d 0a 09 09 2f 2f 20 4d 61 72 s1);......// Mar
08b0: 6b 20 73 31 2d 2d 73 32 0d 0a 09 09 76 65 63 74 k s1--s2....vect
08c0: 6f 72 3c 62 6f 6f 6c 3e 20 73 32 5f 70 61 74 68 or<bool> s2_path
08d0: 28 4e 29 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 (N);....for(int
08e0: 76 3d 73 32 3b 20 76 21 3d 2d 31 3b 20 76 3d 70 v=s2; v!=-1; v=p
08f0: 61 72 65 6e 74 5b 76 5d 29 0d 0a 09 09 09 73 32 arent[v]).....s2
0900: 5f 70 61 74 68 5b 76 5d 20 3d 20 74 72 75 65 3b _path[v] = true;
0910: 0d 0a 0d 0a 09 09 2f 2f 20 50 61 72 74 73 20 65 ......// Parts e
0920: 78 63 65 70 74 20 73 31 2d 2d 73 32 20 70 61 74 xcept s1--s2 pat
0930: 68 20 69 73 20 65 61 73 79 2e 0d 0a 09 09 2f 2f h is easy.....//
0940: 20 49 74 27 73 20 64 70 2d 6f 6e 2d 74 72 65 65 It's dp-on-tree
0950: 5b 73 31 20 5c 73 65 74 6d 69 6e 75 73 20 73 32 [s1 \setminus s2
0960: 5d 20 2a 20 64 70 2d 6f 6e 2d 74 72 65 65 5b 73 ] * dp-on-tree[s
0970: 31 5d 20 2a 20 43 28 4e 2c 20 7c 73 31 7c 29 20 1] * C(N, |s1|)
0980: 2a 20 43 28 4e 2d 7c 73 31 7c 2c 20 7c 73 32 7c * C(N-|s1|, |s2|
0990: 29 2e 0d 0a 09 09 2f 2f 20 43 41 55 54 49 4f 4e ).....// CAUTION
09a0: 3a 20 45 4e 53 55 52 45 20 73 31 20 61 6e 64 20 : ENSURE s1 and
09b0: 73 32 20 4e 4f 54 20 62 65 20 69 6e 63 6c 75 64 s2 NOT be includ
09c0: 65 64 20 6f 6e 20 64 70 2d 6f 6e 2d 74 72 65 65 ed on dp-on-tree
09d0: 20 61 6e 64 20 7c 73 7c 2e 0d 0a 09 09 2f 2f 20 and |s|.....//
09e0: 6f 74 68 65 72 77 69 73 65 20 43 28 4e 2c 20 7c otherwise C(N, |
09f0: 73 31 7c 29 20 77 69 6c 6c 20 66 69 78 20 74 68 s1|) will fix th
0a00: 65 20 74 69 6d 69 6e 67 20 73 31 20 69 73 20 66 e timing s1 is f
0a10: 69 6c 6c 65 64 2c 20 77 68 69 63 68 20 72 65 64 illed, which red
0a20: 75 63 65 73 20 74 68 65 20 66 72 65 65 64 6f 6d uces the freedom
0a30: 20 69 6e 0d 0a 09 09 2f 2f 20 70 61 74 68 20 6d in....// path m
0a40: 6f 64 65 2e 0d 0a 0d 0a 09 09 2f 2f 20 57 68 61 ode.......// Wha
0a50: 74 20 61 62 6f 75 74 20 74 68 65 20 72 65 73 74 t about the rest
0a60: 20 4e 2d 7c 73 31 7c 2d 7c 73 32 7c 3f 0d 0a 09 N-|s1|-|s2|?...
0a70: 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 49 }..};....// BEGI
0a80: 4e 20 43 55 54 20 48 45 52 45 0d 0a 23 69 6e 63 N CUT HERE..#inc
0a90: 6c 75 64 65 20 3c 63 74 69 6d 65 3e 0d 0a 64 6f lude <ctime>..do
0aa0: 75 62 6c 65 20 73 74 61 72 74 5f 74 69 6d 65 3b uble start_time;
0ab0: 20 73 74 72 69 6e 67 20 74 69 6d 65 72 28 29 0d string timer().
0ac0: 0a 20 7b 20 6f 73 74 72 69 6e 67 73 74 72 65 61 . { ostringstrea
0ad0: 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 22 20 28 22 m os; os << " ("
0ae0: 20 3c 3c 20 69 6e 74 28 28 63 6c 6f 63 6b 28 29 << int((clock()
0af0: 2d 73 74 61 72 74 5f 74 69 6d 65 29 2f 43 4c 4f -start_time)/CLO
0b00: 43 4b 53 5f 50 45 52 5f 53 45 43 2a 31 30 30 30 CKS_PER_SEC*1000
0b10: 29 20 3c 3c 20 22 20 6d 73 65 63 29 22 3b 20 72 ) << " msec)"; r
0b20: 65 74 75 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 eturn os.str();
0b30: 7d 0d 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 }..template<type
0b40: 6e 61 6d 65 20 54 3e 20 6f 73 74 72 65 61 6d 26 name T> ostream&
0b50: 20 6f 70 65 72 61 74 6f 72 3c 3c 28 6f 73 74 72 operator<<(ostr
0b60: 65 61 6d 26 20 6f 73 2c 20 63 6f 6e 73 74 20 76 eam& os, const v
0b70: 65 63 74 6f 72 3c 54 3e 26 20 76 29 0d 0a 20 7b ector<T>& v).. {
0b80: 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 0d 0a 20 20 os << "{ ";..
0b90: 20 66 6f 72 28 74 79 70 65 6e 61 6d 65 20 76 65 for(typename ve
0ba0: 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 ctor<T>::const_i
0bb0: 74 65 72 61 74 6f 72 20 69 74 3d 76 2e 62 65 67 terator it=v.beg
0bc0: 69 6e 28 29 3b 20 69 74 21 3d 76 2e 65 6e 64 28 in(); it!=v.end(
0bd0: 29 3b 20 2b 2b 69 74 29 0d 0a 20 20 20 6f 73 20 ); ++it).. os
0be0: 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a 69 74 20 3c << '\"' << *it <
0bf0: 3c 20 27 5c 22 27 20 3c 3c 20 28 69 74 2b 31 3d < '\"' << (it+1=
0c00: 3d 76 2e 65 6e 64 28 29 20 3f 20 22 22 20 3a 20 =v.end() ? "" :
0c10: 22 2c 20 22 29 3b 20 6f 73 20 3c 3c 20 22 20 7d ", "); os << " }
0c20: 22 3b 20 72 65 74 75 72 6e 20 6f 73 3b 20 7d 0d "; return os; }.
0c30: 0a 76 6f 69 64 20 76 65 72 69 66 79 5f 63 61 73 .void verify_cas
0c40: 65 28 63 6f 6e 73 74 20 69 6e 74 26 20 45 78 70 e(const int& Exp
0c50: 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 69 6e 74 ected, const int
0c60: 26 20 52 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 & Received) {..
0c70: 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 70 65 63 bool ok = (Expec
0c80: 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 ted == Received)
0c90: 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 72 20 ;.. if(ok) cerr
0ca0: 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c 20 74 << "PASSED" << t
0cb0: 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 imer() << endl;
0cc0: 20 65 6c 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 else { cerr <<
0cd0: 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 6d 65 "FAILED" << time
0ce0: 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 63 r() << endl;.. c
0cf0: 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 22 err << "\to: \""
0d00: 20 3c 3c 20 45 78 70 65 63 74 65 64 20 3c 3c 20 << Expected <<
0d10: 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 '\"' << endl <<
0d20: 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 65 63 "\tx: \"" << Rec
0d30: 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c eived << '\"' <<
0d40: 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 66 endl; } }..#def
0d50: 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 65 72 ine CASE(N) {cer
0d60: 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 65 20 r << "Test Case
0d70: 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e 22 #" << N << "..."
0d80: 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 72 74 << flush; start
0d90: 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d 0a _time=clock();..
0da0: 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 65 72 #define END. ver
0db0: 69 66 79 5f 63 61 73 65 28 5f 2c 20 54 77 6f 45 ify_case(_, TwoE
0dc0: 6e 74 72 61 6e 63 65 73 28 29 2e 63 6f 75 6e 74 ntrances().count
0dd0: 28 61 2c 20 62 2c 20 73 31 2c 20 73 32 29 29 3b (a, b, s1, s2));
0de0: 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a }..int main(){..
0df0: 0d 0a 43 41 53 45 28 30 29 0d 0a 09 69 6e 74 20 ..CASE(0)...int
0e00: 61 5f 5b 5d 20 3d 20 7b 30 2c 20 31 2c 20 32 7d a_[] = {0, 1, 2}
0e10: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
0e20: 74 3e 20 61 28 61 5f 2c 20 61 5f 2b 73 69 7a 65 t> a(a_, a_+size
0e30: 6f 66 28 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 61 of(a_)/sizeof(*a
0e40: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 5f 5b 5d _)); ...int b_[]
0e50: 20 3d 20 7b 31 2c 20 32 2c 20 33 7d 3b 0d 0a 09 = {1, 2, 3};...
0e60: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 vector <int> b
0e70: 28 62 5f 2c 20 62 5f 2b 73 69 7a 65 6f 66 28 62 (b_, b_+sizeof(b
0e80: 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 5f 29 29 3b _)/sizeof(*b_));
0e90: 20 0d 0a 09 69 6e 74 20 73 31 20 3d 20 30 3b 20 ...int s1 = 0;
0ea0: 0d 0a 09 69 6e 74 20 73 32 20 3d 20 31 3b 20 0d ...int s2 = 1; .
0eb0: 0a 09 69 6e 74 20 5f 20 3d 20 34 3b 20 0d 0a 45 ..int _ = 4; ..E
0ec0: 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 69 6e ND..CASE(1)...in
0ed0: 74 20 61 5f 5b 5d 20 3d 20 7b 30 2c 20 31 2c 20 t a_[] = {0, 1,
0ee0: 32 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 2};... vector <
0ef0: 69 6e 74 3e 20 61 28 61 5f 2c 20 61 5f 2b 73 69 int> a(a_, a_+si
0f00: 7a 65 6f 66 28 61 5f 29 2f 73 69 7a 65 6f 66 28 zeof(a_)/sizeof(
0f10: 2a 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 5f *a_)); ...int b_
0f20: 5b 5d 20 3d 20 7b 31 2c 20 32 2c 20 33 7d 3b 0d [] = {1, 2, 3};.
0f30: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0f40: 20 62 28 62 5f 2c 20 62 5f 2b 73 69 7a 65 6f 66 b(b_, b_+sizeof
0f50: 28 62 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 5f 29 (b_)/sizeof(*b_)
0f60: 29 3b 20 0d 0a 09 69 6e 74 20 73 31 20 3d 20 30 ); ...int s1 = 0
0f70: 3b 20 0d 0a 09 69 6e 74 20 73 32 20 3d 20 32 3b ; ...int s2 = 2;
0f80: 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 39 3b 20 0d ...int _ = 9; .
0f90: 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 .END..CASE(2)...
0fa0: 69 6e 74 20 61 5f 5b 5d 20 3d 20 7b 30 2c 20 31 int a_[] = {0, 1
0fb0: 2c 20 31 2c 20 33 2c 20 33 2c 20 33 2c 20 36 2c , 1, 3, 3, 3, 6,
0fc0: 20 37 2c 20 36 7d 3b 0d 0a 09 20 20 76 65 63 74 7, 6};... vect
0fd0: 6f 72 20 3c 69 6e 74 3e 20 61 28 61 5f 2c 20 61 or <int> a(a_, a
0fe0: 5f 2b 73 69 7a 65 6f 66 28 61 5f 29 2f 73 69 7a _+sizeof(a_)/siz
0ff0: 65 6f 66 28 2a 61 5f 29 29 3b 20 0d 0a 09 69 6e eof(*a_)); ...in
1000: 74 20 62 5f 5b 5d 20 3d 20 7b 31 2c 20 32 2c 20 t b_[] = {1, 2,
1010: 33 2c 20 34 2c 20 35 2c 20 36 2c 20 37 2c 20 38 3, 4, 5, 6, 7, 8
1020: 2c 20 39 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 , 9};... vector
1030: 20 3c 69 6e 74 3e 20 62 28 62 5f 2c 20 62 5f 2b <int> b(b_, b_+
1040: 73 69 7a 65 6f 66 28 62 5f 29 2f 73 69 7a 65 6f sizeof(b_)/sizeo
1050: 66 28 2a 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 f(*b_)); ...int
1060: 73 31 20 3d 20 31 3b 20 0d 0a 09 69 6e 74 20 73 s1 = 1; ...int s
1070: 32 20 3d 20 39 3b 20 0d 0a 09 69 6e 74 20 5f 20 2 = 9; ...int _
1080: 3d 20 31 36 30 30 30 3b 20 0d 0a 45 4e 44 0d 0a = 16000; ..END..
1090: 43 41 53 45 28 33 29 0d 0a 09 69 6e 74 20 61 5f CASE(3)...int a_
10a0: 5b 5d 20 3d 20 7b 30 2c 20 30 2c 20 31 2c 20 32 [] = {0, 0, 1, 2
10b0: 2c 20 33 2c 20 31 2c 20 32 2c 20 30 2c 20 36 2c , 3, 1, 2, 0, 6,
10c0: 20 35 2c 20 31 30 2c 20 31 30 7d 3b 0d 0a 09 20 5, 10, 10};...
10d0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 61 28 vector <int> a(
10e0: 61 5f 2c 20 61 5f 2b 73 69 7a 65 6f 66 28 61 5f a_, a_+sizeof(a_
10f0: 29 2f 73 69 7a 65 6f 66 28 2a 61 5f 29 29 3b 20 )/sizeof(*a_));
1100: 0d 0a 09 69 6e 74 20 62 5f 5b 5d 20 3d 20 7b 31 ...int b_[] = {1
1110: 20 2c 32 20 2c 33 20 2c 34 20 2c 35 20 2c 36 20 ,2 ,3 ,4 ,5 ,6
1120: 2c 37 20 2c 38 20 2c 39 20 2c 31 30 2c 20 31 31 ,7 ,8 ,9 ,10, 11
1130: 2c 20 31 32 7d 3b 0d 0a 09 20 20 76 65 63 74 6f , 12};... vecto
1140: 72 20 3c 69 6e 74 3e 20 62 28 62 5f 2c 20 62 5f r <int> b(b_, b_
1150: 2b 73 69 7a 65 6f 66 28 62 5f 29 2f 73 69 7a 65 +sizeof(b_)/size
1160: 6f 66 28 2a 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 of(*b_)); ...int
1170: 20 73 31 20 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 s1 = 3; ...int
1180: 73 32 20 3d 20 36 3b 20 0d 0a 09 69 6e 74 20 5f s2 = 6; ...int _
1190: 20 3d 20 33 31 30 34 36 34 3b 20 0d 0a 45 4e 44 = 310464; ..END
11a0: 0d 0a 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 ..CASE(4)...int
11b0: 61 5f 5b 5d 20 3d 20 7b 30 7d 3b 0d 0a 09 20 20 a_[] = {0};...
11c0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 61 28 61 vector <int> a(a
11d0: 5f 2c 20 61 5f 2b 73 69 7a 65 6f 66 28 61 5f 29 _, a_+sizeof(a_)
11e0: 2f 73 69 7a 65 6f 66 28 2a 61 5f 29 29 3b 20 0d /sizeof(*a_)); .
11f0: 0a 09 69 6e 74 20 62 5f 5b 5d 20 3d 20 7b 31 7d ..int b_[] = {1}
1200: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1210: 74 3e 20 62 28 62 5f 2c 20 62 5f 2b 73 69 7a 65 t> b(b_, b_+size
1220: 6f 66 28 62 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 of(b_)/sizeof(*b
1230: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 73 31 20 3d _)); ...int s1 =
1240: 20 31 3b 20 0d 0a 09 69 6e 74 20 73 32 20 3d 20 1; ...int s2 =
1250: 30 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 32 3b 0; ...int _ = 2;
1260: 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d 0a 43 41 53 45 ..END../*..CASE
1270: 28 35 29 0d 0a 09 69 6e 74 20 61 5f 5b 5d 20 3d (5)...int a_[] =
1280: 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 ;... vector <i
1290: 6e 74 3e 20 61 28 61 5f 2c 20 61 5f 2b 73 69 7a nt> a(a_, a_+siz
12a0: 65 6f 66 28 61 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(a_)/sizeof(*
12b0: 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 5f 5b a_)); ...int b_[
12c0: 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 ] = ;... vector
12d0: 20 3c 69 6e 74 3e 20 62 28 62 5f 2c 20 62 5f 2b <int> b(b_, b_+
12e0: 73 69 7a 65 6f 66 28 62 5f 29 2f 73 69 7a 65 6f sizeof(b_)/sizeo
12f0: 66 28 2a 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 f(*b_)); ...int
1300: 73 31 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 73 32 s1 = ; ...int s2
1310: 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 = ; ...int _ =
1320: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 36 29 ; ..END..CASE(6)
1330: 0d 0a 09 69 6e 74 20 61 5f 5b 5d 20 3d 20 3b 0d ...int a_[] = ;.
1340: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
1350: 20 61 28 61 5f 2c 20 61 5f 2b 73 69 7a 65 6f 66 a(a_, a_+sizeof
1360: 28 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 61 5f 29 (a_)/sizeof(*a_)
1370: 29 3b 20 0d 0a 09 69 6e 74 20 62 5f 5b 5d 20 3d ); ...int b_[] =
1380: 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 ;... vector <i
1390: 6e 74 3e 20 62 28 62 5f 2c 20 62 5f 2b 73 69 7a nt> b(b_, b_+siz
13a0: 65 6f 66 28 62 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(b_)/sizeof(*
13b0: 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 73 31 20 b_)); ...int s1
13c0: 3d 20 3b 20 0d 0a 09 69 6e 74 20 73 32 20 3d 20 = ; ...int s2 =
13d0: 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 3b 20 0d ; ...int _ = ; .
13e0: 0a 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 .END..*/..}..//
13f0: 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a END CUT HERE..