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 20 3a 76 61 6c 28 30 ...mint() :val(0
01f0: 29 20 7b 7d 0d 0a 09 6d 69 6e 74 28 69 6e 74 20 ) {}...mint(int
0200: 20 20 20 20 20 78 29 20 3a 76 61 6c 28 78 25 4d x) :val(x%M
0210: 4f 44 56 41 4c 29 20 7b 7d 0d 0a 09 6d 69 6e 74 ODVAL) {}...mint
0220: 28 75 6e 73 69 67 6e 65 64 20 78 29 20 3a 76 61 (unsigned x) :va
0230: 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b 7d 0d 0a l(x%MODVAL) {}..
0240: 09 6d 69 6e 74 28 4c 4c 20 20 20 20 20 20 20 78 .mint(LL x
0250: 29 20 3a 76 61 6c 28 78 25 4d 4f 44 56 41 4c 29 ) :val(x%MODVAL)
0260: 20 7b 7d 0d 0a 7d 3b 0d 0a 6d 69 6e 74 26 20 6f {}..};..mint& o
0270: 70 65 72 61 74 6f 72 2b 3d 28 6d 69 6e 74 26 20 perator+=(mint&
0280: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 x, mint y) { ret
0290: 75 72 6e 20 78 20 3d 20 78 2e 76 61 6c 20 2b 20 urn x = x.val +
02a0: 79 2e 76 61 6c 3b 20 7d 0d 0a 6d 69 6e 74 26 20 y.val; }..mint&
02b0: 6f 70 65 72 61 74 6f 72 2d 3d 28 6d 69 6e 74 26 operator-=(mint&
02c0: 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 x, mint y) { re
02d0: 74 75 72 6e 20 78 20 3d 20 78 2e 76 61 6c 20 2d turn x = x.val -
02e0: 20 79 2e 76 61 6c 20 2b 20 4d 4f 44 56 41 4c 3b y.val + MODVAL;
02f0: 20 7d 0d 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 }..mint& operat
0300: 6f 72 2a 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 or*=(mint& x, mi
0310: 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 nt y) { return x
0320: 20 3d 20 4c 4c 28 78 2e 76 61 6c 29 2a 79 2e 76 = LL(x.val)*y.v
0330: 61 6c 3b 20 7d 0d 0a 6d 69 6e 74 20 6f 70 65 72 al; }..mint oper
0340: 61 74 6f 72 2b 28 6d 69 6e 74 20 78 2c 20 6d 69 ator+(mint x, mi
0350: 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 nt y) { return x
0360: 20 2b 3d 20 79 3b 20 7d 0d 0a 6d 69 6e 74 20 6f += y; }..mint o
0370: 70 65 72 61 74 6f 72 2d 28 6d 69 6e 74 20 78 2c perator-(mint x,
0380: 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 mint y) { retur
0390: 6e 20 78 20 2d 3d 20 79 3b 20 7d 0d 0a 6d 69 6e n x -= y; }..min
03a0: 74 20 6f 70 65 72 61 74 6f 72 2a 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 20 2a 3d 20 79 3b 20 7d 0d 0a turn x *= y; }..
03d0: 0d 0a 63 6c 61 73 73 20 53 68 6f 72 74 42 75 67 ..class ShortBug
03e0: 50 61 74 68 73 20 7b 20 70 75 62 6c 69 63 3a 0d Paths { public:.
03f0: 0a 09 69 6e 74 20 63 6f 75 6e 74 28 69 6e 74 20 ..int count(int
0400: 4e 2c 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 N, vector <int>
0410: 44 2c 20 69 6e 74 20 4a 29 0d 0a 09 7b 0d 0a 09 D, int J)...{...
0420: 09 69 66 20 28 4e 20 3c 3d 20 32 30 30 29 20 7b .if (N <= 200) {
0430: 0d 0a 09 09 09 76 65 63 74 6f 72 3c 76 65 63 74 .....vector<vect
0440: 6f 72 3c 69 6e 74 3e 3e 20 63 28 4e 2c 20 76 65 or<int>> c(N, ve
0450: 63 74 6f 72 3c 69 6e 74 3e 28 4e 2c 20 31 29 29 ctor<int>(N, 1))
0460: 3b 0d 0a 09 09 09 76 65 63 74 6f 72 3c 76 65 63 ;.....vector<vec
0470: 74 6f 72 3c 69 6e 74 3e 3e 20 63 32 28 4e 2c 20 tor<int>> c2(N,
0480: 76 65 63 74 6f 72 3c 69 6e 74 3e 28 4e 2c 20 31 vector<int>(N, 1
0490: 29 29 3b 0d 0a 09 09 09 66 6f 72 20 28 69 6e 74 ));.....for (int
04a0: 20 5f 20 3d 20 30 3b 20 5f 20 3c 20 4a 3b 20 2b _ = 0; _ < J; +
04b0: 2b 5f 29 20 7b 0d 0a 09 09 09 09 66 6f 72 20 28 +_) {......for (
04c0: 69 6e 74 20 79 20 3d 20 30 3b 20 79 20 3c 20 4e int y = 0; y < N
04d0: 3b 20 2b 2b 79 29 0d 0a 09 09 09 09 66 6f 72 20 ; ++y)......for
04e0: 28 69 6e 74 20 78 20 3d 20 30 3b 20 78 20 3c 20 (int x = 0; x <
04f0: 4e 3b 20 2b 2b 78 29 20 7b 0d 0a 09 09 09 09 09 N; ++x) {.......
0500: 4c 4c 20 73 75 6d 20 3d 20 30 3b 0d 0a 09 09 09 LL sum = 0;.....
0510: 09 09 66 6f 72 20 28 69 6e 74 20 44 44 20 3a 20 ..for (int DD :
0520: 44 29 20 7b 0d 0a 09 09 09 09 09 09 69 6e 74 20 D) {........int
0530: 79 79 20 3d 20 79 20 2d 20 44 44 2c 20 78 78 20 yy = y - DD, xx
0540: 3d 20 78 3b 0d 0a 09 09 09 09 09 09 66 6f 72 20 = x;........for
0550: 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 (int d = 0; d <
0560: 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 DD; ++d) {......
0570: 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 26 26 ...if (0 <= yy&&
0580: 79 79 3c 4e 20 26 26 20 30 20 3c 3d 20 78 78 26 yy<N && 0 <= xx&
0590: 26 78 78 3c 4e 29 20 73 75 6d 20 2b 3d 20 63 5b &xx<N) sum += c[
05a0: 79 79 5d 5b 78 78 5d 3b 0d 0a 09 09 09 09 09 09 yy][xx];........
05b0: 09 79 79 2b 2b 2c 20 78 78 2b 2b 3b 0d 0a 09 09 .yy++, xx++;....
05c0: 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 66 6f 72 ....}........for
05d0: 20 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c (int d = 0; d <
05e0: 20 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 DD; ++d) {.....
05f0: 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 26 ....if (0 <= yy&
0600: 26 79 79 3c 4e 20 26 26 20 30 20 3c 3d 20 78 78 &yy<N && 0 <= xx
0610: 26 26 78 78 3c 4e 29 20 73 75 6d 20 2b 3d 20 63 &&xx<N) sum += c
0620: 5b 79 79 5d 5b 78 78 5d 3b 0d 0a 09 09 09 09 09 [yy][xx];.......
0630: 09 09 79 79 2b 2b 2c 20 78 78 2d 2d 3b 0d 0a 09 ..yy++, xx--;...
0640: 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 66 6f .....}........fo
0650: 72 20 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 r (int d = 0; d
0660: 3c 20 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 < DD; ++d) {....
0670: 09 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 .....if (0 <= yy
0680: 26 26 79 79 3c 4e 20 26 26 20 30 20 3c 3d 20 78 &&yy<N && 0 <= x
0690: 78 26 26 78 78 3c 4e 29 20 73 75 6d 20 2b 3d 20 x&&xx<N) sum +=
06a0: 63 5b 79 79 5d 5b 78 78 5d 3b 0d 0a 09 09 09 09 c[yy][xx];......
06b0: 09 09 09 79 79 2d 2d 2c 20 78 78 2d 2d 3b 0d 0a ...yy--, xx--;..
06c0: 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 66 ......}........f
06d0: 6f 72 20 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 or (int d = 0; d
06e0: 20 3c 20 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 < DD; ++d) {...
06f0: 09 09 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 ......if (0 <= y
0700: 79 26 26 79 79 3c 4e 20 26 26 20 30 20 3c 3d 20 y&&yy<N && 0 <=
0710: 78 78 26 26 78 78 3c 4e 29 20 73 75 6d 20 2b 3d xx&&xx<N) sum +=
0720: 20 63 5b 79 79 5d 5b 78 78 5d 3b 0d 0a 09 09 09 c[yy][xx];.....
0730: 09 09 09 09 79 79 2d 2d 2c 20 78 78 2b 2b 3b 0d ....yy--, xx++;.
0740: 0a 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 .......}........
0750: 69 66 20 28 44 44 20 3d 3d 20 30 29 0d 0a 09 09 if (DD == 0)....
0760: 09 09 09 09 09 73 75 6d 20 2b 3d 20 63 5b 79 5d .....sum += c[y]
0770: 5b 78 5d 3b 0d 0a 09 09 09 09 09 7d 0d 0a 09 09 [x];.......}....
0780: 09 09 09 63 32 5b 79 5d 5b 78 5d 20 3d 20 73 75 ...c2[y][x] = su
0790: 6d 20 25 20 4d 4f 44 56 41 4c 3b 0d 0a 09 09 09 m % MODVAL;.....
07a0: 09 7d 0d 0a 09 09 09 09 63 2e 73 77 61 70 28 63 .}......c.swap(c
07b0: 32 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 09 6d 69 2);.....}.....mi
07c0: 6e 74 20 61 6e 73 20 3d 20 30 3b 0d 0a 09 09 09 nt ans = 0;.....
07d0: 66 6f 72 20 28 69 6e 74 20 79 20 3d 20 30 3b 20 for (int y = 0;
07e0: 79 20 3c 20 4e 3b 20 2b 2b 79 29 0d 0a 09 09 09 y < N; ++y).....
07f0: 09 66 6f 72 20 28 69 6e 74 20 78 20 3d 20 30 3b .for (int x = 0;
0800: 20 78 20 3c 20 4e 3b 20 2b 2b 78 29 0d 0a 09 09 x < N; ++x)....
0810: 09 09 09 61 6e 73 20 2b 3d 20 63 5b 79 5d 5b 78 ...ans += c[y][x
0820: 5d 3b 0d 0a 09 09 09 72 65 74 75 72 6e 20 61 6e ];.....return an
0830: 73 2e 76 61 6c 3b 0d 0a 09 09 7d 0d 0a 09 09 65 s.val;....}....e
0840: 6c 73 65 20 7b 0d 0a 09 09 09 76 65 63 74 6f 72 lse {.....vector
0850: 3c 76 65 63 74 6f 72 3c 69 6e 74 3e 3e 20 63 28 <vector<int>> c(
0860: 32 30 31 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 201, vector<int>
0870: 28 32 30 31 2c 20 31 29 29 3b 0d 0a 09 09 09 76 (201, 1));.....v
0880: 65 63 74 6f 72 3c 76 65 63 74 6f 72 3c 69 6e 74 ector<vector<int
0890: 3e 3e 20 63 32 28 32 30 31 2c 20 76 65 63 74 6f >> c2(201, vecto
08a0: 72 3c 69 6e 74 3e 28 32 30 31 2c 20 31 29 29 3b r<int>(201, 1));
08b0: 0d 0a 09 09 09 66 6f 72 20 28 69 6e 74 20 5f 20 .....for (int _
08c0: 3d 20 30 3b 20 5f 20 3c 20 4a 3b 20 2b 2b 5f 29 = 0; _ < J; ++_)
08d0: 20 7b 0d 0a 09 09 09 09 66 6f 72 20 28 69 6e 74 {......for (int
08e0: 20 79 20 3d 20 30 3b 20 79 20 3c 20 31 30 31 3b y = 0; y < 101;
08f0: 20 2b 2b 79 29 0d 0a 09 09 09 09 09 66 6f 72 20 ++y).......for
0900: 28 69 6e 74 20 78 20 3d 20 30 3b 20 78 20 3c 20 (int x = 0; x <
0910: 31 30 31 3b 20 2b 2b 78 29 20 7b 0d 0a 09 09 09 101; ++x) {.....
0920: 09 09 09 4c 4c 20 73 75 6d 20 3d 20 30 3b 0d 0a ...LL sum = 0;..
0930: 09 09 09 09 09 09 66 6f 72 20 28 69 6e 74 20 44 ......for (int D
0940: 44 20 3a 20 44 29 20 7b 0d 0a 09 09 09 09 09 09 D : D) {........
0950: 09 69 6e 74 20 79 79 20 3d 20 79 20 2d 20 44 44 .int yy = y - DD
0960: 2c 20 78 78 20 3d 20 78 3b 0d 0a 0d 0a 09 09 09 , xx = x;.......
0970: 09 09 09 09 69 66 20 28 79 20 3d 3d 20 31 30 30 ....if (y == 100
0980: 20 26 26 20 78 20 3d 3d 20 31 30 30 29 20 7b 0d && x == 100) {.
0990: 0a 09 09 09 09 09 09 09 09 66 6f 72 20 28 69 6e .........for (in
09a0: 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 44 44 3b t d = 0; d < DD;
09b0: 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 09 09 ++d) {.........
09c0: 09 09 69 66 20 28 30 20 3c 3d 20 79 79 26 26 79 ..if (0 <= yy&&y
09d0: 79 20 3c 20 4e 20 26 26 20 30 20 3c 3d 20 78 78 y < N && 0 <= xx
09e0: 26 26 78 78 20 3c 20 4e 29 20 73 75 6d 20 2b 3d &&xx < N) sum +=
09f0: 20 63 5b 31 30 30 5d 5b 31 30 30 5d 3b 0d 0a 09 c[100][100];...
0a00: 09 09 09 09 09 09 09 09 79 79 2b 2b 2c 20 78 78 ........yy++, xx
0a10: 2b 2b 3b 0d 0a 09 09 09 09 09 09 09 09 7d 0d 0a ++;..........}..
0a20: 09 09 09 09 09 09 09 09 66 6f 72 20 28 69 6e 74 ........for (int
0a30: 20 64 20 3d 20 30 3b 20 64 20 3c 20 44 44 3b 20 d = 0; d < DD;
0a40: 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 09 09 09 ++d) {..........
0a50: 09 69 66 20 28 30 20 3c 3d 20 79 79 26 26 79 79 .if (0 <= yy&&yy
0a60: 20 3c 20 4e 20 26 26 20 30 20 3c 3d 20 78 78 26 < N && 0 <= xx&
0a70: 26 78 78 20 3c 20 4e 29 20 73 75 6d 20 2b 3d 20 &xx < N) sum +=
0a80: 63 5b 31 30 30 5d 5b 31 30 30 5d 3b 0d 0a 09 09 c[100][100];....
0a90: 09 09 09 09 09 09 09 79 79 2b 2b 2c 20 78 78 2d .......yy++, xx-
0aa0: 2d 3b 0d 0a 09 09 09 09 09 09 09 09 7d 0d 0a 09 -;..........}...
0ab0: 09 09 09 09 09 09 09 66 6f 72 20 28 69 6e 74 20 .......for (int
0ac0: 64 20 3d 20 30 3b 20 64 20 3c 20 44 44 3b 20 2b d = 0; d < DD; +
0ad0: 2b 64 29 20 7b 0d 0a 09 09 09 09 09 09 09 09 09 +d) {...........
0ae0: 69 66 20 28 30 20 3c 3d 20 79 79 26 26 79 79 20 if (0 <= yy&&yy
0af0: 3c 20 4e 20 26 26 20 30 20 3c 3d 20 78 78 26 26 < N && 0 <= xx&&
0b00: 78 78 20 3c 20 4e 29 20 73 75 6d 20 2b 3d 20 63 xx < N) sum += c
0b10: 5b 31 30 30 5d 5b 31 30 30 5d 3b 0d 0a 09 09 09 [100][100];.....
0b20: 09 09 09 09 09 09 79 79 2d 2d 2c 20 78 78 2d 2d ......yy--, xx--
0b30: 3b 0d 0a 09 09 09 09 09 09 09 09 7d 0d 0a 09 09 ;..........}....
0b40: 09 09 09 09 09 09 66 6f 72 20 28 69 6e 74 20 64 ......for (int d
0b50: 20 3d 20 30 3b 20 64 20 3c 20 44 44 3b 20 2b 2b = 0; d < DD; ++
0b60: 64 29 20 7b 0d 0a 09 09 09 09 09 09 09 09 09 69 d) {...........i
0b70: 66 20 28 30 20 3c 3d 20 79 79 26 26 79 79 20 3c f (0 <= yy&&yy <
0b80: 20 4e 20 26 26 20 30 20 3c 3d 20 78 78 26 26 78 N && 0 <= xx&&x
0b90: 78 20 3c 20 4e 29 20 73 75 6d 20 2b 3d 20 63 5b x < N) sum += c[
0ba0: 31 30 30 5d 5b 31 30 30 5d 3b 0d 0a 09 09 09 09 100][100];......
0bb0: 09 09 09 09 09 79 79 2d 2d 2c 20 78 78 2b 2b 3b .....yy--, xx++;
0bc0: 0d 0a 09 09 09 09 09 09 09 09 7d 0d 0a 09 09 09 ..........}.....
0bd0: 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 09 65 6c ....}.........el
0be0: 73 65 20 69 66 20 28 79 20 3d 3d 20 31 30 30 29 se if (y == 100)
0bf0: 20 7b 0d 0a 09 09 09 09 09 09 09 09 66 6f 72 20 {..........for
0c00: 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 (int d = 0; d <
0c10: 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 DD; ++d) {......
0c20: 09 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 .....if (0 <= yy
0c30: 26 26 79 79 20 3c 20 4e 20 26 26 20 30 20 3c 3d &&yy < N && 0 <=
0c40: 20 78 78 26 26 78 78 20 3c 20 4e 29 20 73 75 6d xx&&xx < N) sum
0c50: 20 2b 3d 20 63 5b 31 30 30 5d 5b 6d 69 6e 28 31 += c[100][min(1
0c60: 30 30 2c 78 78 29 5d 3b 0d 0a 09 09 09 09 09 09 00,xx)];........
0c70: 09 09 09 79 79 2b 2b 2c 20 78 78 2b 2b 3b 0d 0a ...yy++, xx++;..
0c80: 09 09 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 ........}.......
0c90: 09 09 09 66 6f 72 20 28 69 6e 74 20 64 20 3d 20 ...for (int d =
0ca0: 30 3b 20 64 20 3c 20 44 44 3b 20 2b 2b 64 29 20 0; d < DD; ++d)
0cb0: 7b 0d 0a 09 09 09 09 09 09 09 09 09 69 66 20 28 {...........if (
0cc0: 30 20 3c 3d 20 79 79 26 26 79 79 20 3c 20 4e 20 0 <= yy&&yy < N
0cd0: 26 26 20 30 20 3c 3d 20 78 78 26 26 78 78 20 3c && 0 <= xx&&xx <
0ce0: 20 4e 29 20 73 75 6d 20 2b 3d 20 63 5b 31 30 30 N) sum += c[100
0cf0: 5d 5b 6d 69 6e 28 31 30 30 2c 20 78 78 29 5d 3b ][min(100, xx)];
0d00: 0d 0a 09 09 09 09 09 09 09 09 09 79 79 2b 2b 2c ...........yy++,
0d10: 20 78 78 2d 2d 3b 0d 0a 09 09 09 09 09 09 09 09 xx--;..........
0d20: 7d 0d 0a 09 09 09 09 09 09 09 09 66 6f 72 20 28 }..........for (
0d30: 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 44 int d = 0; d < D
0d40: 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 D; ++d) {.......
0d50: 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 26 ....if (0 <= yy&
0d60: 26 79 79 20 3c 20 4e 20 26 26 20 30 20 3c 3d 20 &yy < N && 0 <=
0d70: 78 78 26 26 78 78 20 3c 20 4e 29 20 73 75 6d 20 xx&&xx < N) sum
0d80: 2b 3d 20 63 5b 31 30 30 5d 5b 6d 69 6e 28 31 30 += c[100][min(10
0d90: 30 2c 20 78 78 29 5d 3b 0d 0a 09 09 09 09 09 09 0, xx)];........
0da0: 09 09 09 79 79 2d 2d 2c 20 78 78 2d 2d 3b 0d 0a ...yy--, xx--;..
0db0: 09 09 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 ........}.......
0dc0: 09 09 09 66 6f 72 20 28 69 6e 74 20 64 20 3d 20 ...for (int d =
0dd0: 30 3b 20 64 20 3c 20 44 44 3b 20 2b 2b 64 29 20 0; d < DD; ++d)
0de0: 7b 0d 0a 09 09 09 09 09 09 09 09 09 69 66 20 28 {...........if (
0df0: 30 20 3c 3d 20 79 79 26 26 79 79 20 3c 20 4e 20 0 <= yy&&yy < N
0e00: 26 26 20 30 20 3c 3d 20 78 78 26 26 78 78 20 3c && 0 <= xx&&xx <
0e10: 20 4e 29 20 73 75 6d 20 2b 3d 20 63 5b 31 30 30 N) sum += c[100
0e20: 5d 5b 6d 69 6e 28 31 30 30 2c 20 78 78 29 5d 3b ][min(100, xx)];
0e30: 0d 0a 09 09 09 09 09 09 09 09 09 79 79 2d 2d 2c ...........yy--,
0e40: 20 78 78 2b 2b 3b 0d 0a 09 09 09 09 09 09 09 09 xx++;..........
0e50: 7d 0d 0a 09 09 09 09 09 09 09 7d 0d 0a 09 09 09 }.........}.....
0e60: 09 09 09 09 65 6c 73 65 20 69 66 20 28 78 20 3d ....else if (x =
0e70: 3d 20 31 30 30 29 20 7b 0d 0a 09 09 09 09 09 09 = 100) {........
0e80: 09 09 66 6f 72 20 28 69 6e 74 20 64 20 3d 20 30 ..for (int d = 0
0e90: 3b 20 64 20 3c 20 44 44 3b 20 2b 2b 64 29 20 7b ; d < DD; ++d) {
0ea0: 0d 0a 09 09 09 09 09 09 09 09 09 69 66 20 28 30 ...........if (0
0eb0: 20 3c 3d 20 79 79 26 26 79 79 20 3c 20 4e 20 26 <= yy&&yy < N &
0ec0: 26 20 30 20 3c 3d 20 78 78 26 26 78 78 20 3c 20 & 0 <= xx&&xx <
0ed0: 4e 29 20 73 75 6d 20 2b 3d 20 63 5b 6d 69 6e 28 N) sum += c[min(
0ee0: 31 30 30 2c 20 79 79 29 5d 5b 31 30 30 5d 3b 0d 100, yy)][100];.
0ef0: 0a 09 09 09 09 09 09 09 09 09 79 79 2b 2b 2c 20 ..........yy++,
0f00: 78 78 2b 2b 3b 0d 0a 09 09 09 09 09 09 09 09 7d xx++;..........}
0f10: 0d 0a 09 09 09 09 09 09 09 09 66 6f 72 20 28 69 ..........for (i
0f20: 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 44 44 nt d = 0; d < DD
0f30: 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 09 ; ++d) {........
0f40: 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 26 26 ...if (0 <= yy&&
0f50: 79 79 20 3c 20 4e 20 26 26 20 30 20 3c 3d 20 78 yy < N && 0 <= x
0f60: 78 26 26 78 78 20 3c 20 4e 29 20 73 75 6d 20 2b x&&xx < N) sum +
0f70: 3d 20 63 5b 6d 69 6e 28 31 30 30 2c 20 79 79 29 = c[min(100, yy)
0f80: 5d 5b 31 30 30 5d 3b 0d 0a 09 09 09 09 09 09 09 ][100];.........
0f90: 09 09 79 79 2b 2b 2c 20 78 78 2d 2d 3b 0d 0a 09 ..yy++, xx--;...
0fa0: 09 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 .......}........
0fb0: 09 09 66 6f 72 20 28 69 6e 74 20 64 20 3d 20 30 ..for (int d = 0
0fc0: 3b 20 64 20 3c 20 44 44 3b 20 2b 2b 64 29 20 7b ; d < DD; ++d) {
0fd0: 0d 0a 09 09 09 09 09 09 09 09 09 69 66 20 28 30 ...........if (0
0fe0: 20 3c 3d 20 79 79 26 26 79 79 20 3c 20 4e 20 26 <= yy&&yy < N &
0ff0: 26 20 30 20 3c 3d 20 78 78 26 26 78 78 20 3c 20 & 0 <= xx&&xx <
1000: 4e 29 20 73 75 6d 20 2b 3d 20 63 5b 6d 69 6e 28 N) sum += c[min(
1010: 31 30 30 2c 20 79 79 29 5d 5b 31 30 30 5d 3b 0d 100, yy)][100];.
1020: 0a 09 09 09 09 09 09 09 09 09 79 79 2d 2d 2c 20 ..........yy--,
1030: 78 78 2d 2d 3b 0d 0a 09 09 09 09 09 09 09 09 7d xx--;..........}
1040: 0d 0a 09 09 09 09 09 09 09 09 66 6f 72 20 28 69 ..........for (i
1050: 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 44 44 nt d = 0; d < DD
1060: 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 09 ; ++d) {........
1070: 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 26 26 ...if (0 <= yy&&
1080: 79 79 20 3c 20 4e 20 26 26 20 30 20 3c 3d 20 78 yy < N && 0 <= x
1090: 78 26 26 78 78 20 3c 20 4e 29 20 73 75 6d 20 2b x&&xx < N) sum +
10a0: 3d 20 63 5b 6d 69 6e 28 31 30 30 2c 20 79 79 29 = c[min(100, yy)
10b0: 5d 5b 31 30 30 5d 3b 0d 0a 09 09 09 09 09 09 09 ][100];.........
10c0: 09 09 79 79 2d 2d 2c 20 78 78 2b 2b 3b 0d 0a 09 ..yy--, xx++;...
10d0: 09 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 .......}........
10e0: 09 7d 0d 0a 09 09 09 09 09 09 09 65 6c 73 65 20 .}.........else
10f0: 7b 0d 0a 09 09 09 09 09 09 09 09 66 6f 72 20 28 {..........for (
1100: 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 44 int d = 0; d < D
1110: 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 D; ++d) {.......
1120: 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 26 ....if (0 <= yy&
1130: 26 79 79 20 3c 20 4e 20 26 26 20 30 20 3c 3d 20 &yy < N && 0 <=
1140: 78 78 26 26 78 78 20 3c 20 4e 29 20 73 75 6d 20 xx&&xx < N) sum
1150: 2b 3d 20 63 5b 6d 69 6e 28 31 30 30 2c 20 79 79 += c[min(100, yy
1160: 29 5d 5b 6d 69 6e 28 31 30 30 2c 20 78 78 29 5d )][min(100, xx)]
1170: 3b 0d 0a 09 09 09 09 09 09 09 09 09 79 79 2b 2b ;...........yy++
1180: 2c 20 78 78 2b 2b 3b 0d 0a 09 09 09 09 09 09 09 , xx++;.........
1190: 09 7d 0d 0a 09 09 09 09 09 09 09 09 66 6f 72 20 .}..........for
11a0: 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c 20 (int d = 0; d <
11b0: 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 DD; ++d) {......
11c0: 09 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 79 .....if (0 <= yy
11d0: 26 26 79 79 20 3c 20 4e 20 26 26 20 30 20 3c 3d &&yy < N && 0 <=
11e0: 20 78 78 26 26 78 78 20 3c 20 4e 29 20 73 75 6d xx&&xx < N) sum
11f0: 20 2b 3d 20 63 5b 6d 69 6e 28 31 30 30 2c 20 79 += c[min(100, y
1200: 79 29 5d 5b 6d 69 6e 28 31 30 30 2c 20 78 78 29 y)][min(100, xx)
1210: 5d 3b 0d 0a 09 09 09 09 09 09 09 09 09 79 79 2b ];...........yy+
1220: 2b 2c 20 78 78 2d 2d 3b 0d 0a 09 09 09 09 09 09 +, xx--;........
1230: 09 09 7d 0d 0a 09 09 09 09 09 09 09 09 66 6f 72 ..}..........for
1240: 20 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 3c (int d = 0; d <
1250: 20 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 DD; ++d) {.....
1260: 09 09 09 09 09 09 69 66 20 28 30 20 3c 3d 20 79 ......if (0 <= y
1270: 79 26 26 79 79 20 3c 20 4e 20 26 26 20 30 20 3c y&&yy < N && 0 <
1280: 3d 20 78 78 26 26 78 78 20 3c 20 4e 29 20 73 75 = xx&&xx < N) su
1290: 6d 20 2b 3d 20 63 5b 6d 69 6e 28 31 30 30 2c 20 m += c[min(100,
12a0: 79 79 29 5d 5b 6d 69 6e 28 31 30 30 2c 20 78 78 yy)][min(100, xx
12b0: 29 5d 3b 0d 0a 09 09 09 09 09 09 09 09 09 79 79 )];...........yy
12c0: 2d 2d 2c 20 78 78 2d 2d 3b 0d 0a 09 09 09 09 09 --, xx--;.......
12d0: 09 09 09 7d 0d 0a 09 09 09 09 09 09 09 09 66 6f ...}..........fo
12e0: 72 20 28 69 6e 74 20 64 20 3d 20 30 3b 20 64 20 r (int d = 0; d
12f0: 3c 20 44 44 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 < DD; ++d) {....
1300: 09 09 09 09 09 09 09 69 66 20 28 30 20 3c 3d 20 .......if (0 <=
1310: 79 79 26 26 79 79 20 3c 20 4e 20 26 26 20 30 20 yy&&yy < N && 0
1320: 3c 3d 20 78 78 26 26 78 78 20 3c 20 4e 29 20 73 <= xx&&xx < N) s
1330: 75 6d 20 2b 3d 20 63 5b 6d 69 6e 28 31 30 30 2c um += c[min(100,
1340: 20 79 79 29 5d 5b 6d 69 6e 28 31 30 30 2c 20 78 yy)][min(100, x
1350: 78 29 5d 3b 0d 0a 09 09 09 09 09 09 09 09 09 79 x)];...........y
1360: 79 2d 2d 2c 20 78 78 2b 2b 3b 0d 0a 09 09 09 09 y--, xx++;......
1370: 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 09 7d 0d ....}.........}.
1380: 0a 0d 0a 09 09 09 09 09 09 09 69 66 20 28 44 44 ..........if (DD
1390: 20 3d 3d 20 30 29 0d 0a 09 09 09 09 09 09 09 09 == 0)..........
13a0: 73 75 6d 20 2b 3d 20 63 5b 79 5d 5b 78 5d 3b 0d sum += c[y][x];.
13b0: 0a 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 09 .......}........
13c0: 63 32 5b 79 5d 5b 78 5d 20 3d 20 73 75 6d 20 25 c2[y][x] = sum %
13d0: 20 4d 4f 44 56 41 4c 3b 0d 0a 09 09 09 09 09 7d MODVAL;.......}
13e0: 0d 0a 09 09 09 09 66 6f 72 20 28 69 6e 74 20 79 ......for (int y
13f0: 20 3d 20 30 3b 20 79 20 3c 20 32 30 31 3b 20 2b = 0; y < 201; +
1400: 2b 79 29 0d 0a 09 09 09 09 09 66 6f 72 20 28 69 +y).......for (i
1410: 6e 74 20 78 20 3d 20 30 3b 20 78 20 3c 20 32 30 nt x = 0; x < 20
1420: 31 3b 20 2b 2b 78 29 0d 0a 09 09 09 09 09 09 63 1; ++x)........c
1430: 32 5b 79 5d 5b 78 5d 20 3d 20 63 32 5b 79 3e 31 2[y][x] = c2[y>1
1440: 30 30 20 3f 20 32 30 30 2d 79 20 3a 20 79 5d 5b 00 ? 200-y : y][
1450: 78 3e 31 30 30 20 3f 20 32 30 30 2d 78 20 3a 20 x>100 ? 200-x :
1460: 78 5d 3b 0d 0a 09 09 09 09 63 2e 73 77 61 70 28 x];......c.swap(
1470: 63 32 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 09 6d c2);.....}.....m
1480: 69 6e 74 20 61 6e 73 20 3d 20 30 3b 0d 0a 09 09 int ans = 0;....
1490: 09 66 6f 72 20 28 69 6e 74 20 79 20 3d 20 30 3b .for (int y = 0;
14a0: 20 79 20 3c 20 32 30 31 3b 20 2b 2b 79 29 0d 0a y < 201; ++y)..
14b0: 09 09 09 09 66 6f 72 20 28 69 6e 74 20 78 20 3d ....for (int x =
14c0: 20 30 3b 20 78 20 3c 20 32 30 31 3b 20 2b 2b 78 0; x < 201; ++x
14d0: 29 0d 0a 09 09 09 09 09 69 66 20 28 79 20 3d 3d ).......if (y ==
14e0: 20 31 30 30 20 26 26 20 78 20 3d 3d 20 31 30 30 100 && x == 100
14f0: 29 0d 0a 09 09 09 09 09 09 61 6e 73 20 2b 3d 20 )........ans +=
1500: 6d 69 6e 74 28 63 5b 79 5d 5b 78 5d 29 20 2a 20 mint(c[y][x]) *
1510: 28 4e 20 2d 20 32 30 30 29 20 2a 20 28 4e 20 2d (N - 200) * (N -
1520: 20 32 30 30 29 3b 0d 0a 09 09 09 09 09 65 6c 73 200);.......els
1530: 65 20 69 66 20 28 79 20 3d 3d 20 31 30 30 20 7c e if (y == 100 |
1540: 7c 20 78 20 3d 3d 20 31 30 30 29 0d 0a 09 09 09 | x == 100).....
1550: 09 09 09 61 6e 73 20 2b 3d 20 6d 69 6e 74 28 63 ...ans += mint(c
1560: 5b 79 5d 5b 78 5d 29 20 2a 20 28 4e 20 2d 20 32 [y][x]) * (N - 2
1570: 30 30 29 3b 0d 0a 09 09 09 09 09 65 6c 73 65 0d 00);.......else.
1580: 0a 09 09 09 09 09 09 61 6e 73 20 2b 3d 20 63 5b .......ans += c[
1590: 79 5d 5b 78 5d 3b 0d 0a 09 09 09 72 65 74 75 72 y][x];.....retur
15a0: 6e 20 61 6e 73 2e 76 61 6c 3b 0d 0a 09 09 7d 0d n ans.val;....}.
15b0: 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 ..}..};....// BE
15c0: 47 49 4e 20 43 55 54 20 48 45 52 45 0d 0a 23 69 GIN CUT HERE..#i
15d0: 6e 63 6c 75 64 65 20 3c 63 74 69 6d 65 3e 0d 0a nclude <ctime>..
15e0: 64 6f 75 62 6c 65 20 73 74 61 72 74 5f 74 69 6d double start_tim
15f0: 65 3b 20 73 74 72 69 6e 67 20 74 69 6d 65 72 28 e; string timer(
1600: 29 0d 0a 20 7b 20 6f 73 74 72 69 6e 67 73 74 72 ).. { ostringstr
1610: 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 22 20 eam os; os << "
1620: 28 22 20 3c 3c 20 69 6e 74 28 28 63 6c 6f 63 6b (" << int((clock
1630: 28 29 2d 73 74 61 72 74 5f 74 69 6d 65 29 2f 43 ()-start_time)/C
1640: 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 43 2a 31 30 LOCKS_PER_SEC*10
1650: 30 30 29 20 3c 3c 20 22 20 6d 73 65 63 29 22 3b 00) << " msec)";
1660: 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 28 29 return os.str()
1670: 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 65 3c 74 79 ; }..template<ty
1680: 70 65 6e 61 6d 65 20 54 3e 20 6f 73 74 72 65 61 pename T> ostrea
1690: 6d 26 20 6f 70 65 72 61 74 6f 72 3c 3c 28 6f 73 m& operator<<(os
16a0: 74 72 65 61 6d 26 20 6f 73 2c 20 63 6f 6e 73 74 tream& os, const
16b0: 20 76 65 63 74 6f 72 3c 54 3e 26 20 76 29 0d 0a vector<T>& v)..
16c0: 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 0d 0a { os << "{ ";..
16d0: 20 20 20 66 6f 72 28 74 79 70 65 6e 61 6d 65 20 for(typename
16e0: 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 74 vector<T>::const
16f0: 5f 69 74 65 72 61 74 6f 72 20 69 74 3d 76 2e 62 _iterator it=v.b
1700: 65 67 69 6e 28 29 3b 20 69 74 21 3d 76 2e 65 6e egin(); it!=v.en
1710: 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 20 20 20 6f d(); ++it).. o
1720: 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a 69 74 s << '\"' << *it
1730: 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 28 69 74 2b << '\"' << (it+
1740: 31 3d 3d 76 2e 65 6e 64 28 29 20 3f 20 22 22 20 1==v.end() ? ""
1750: 3a 20 22 2c 20 22 29 3b 20 6f 73 20 3c 3c 20 22 : ", "); os << "
1760: 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 3b 20 }"; return os;
1770: 7d 0d 0a 76 6f 69 64 20 76 65 72 69 66 79 5f 63 }..void verify_c
1780: 61 73 65 28 63 6f 6e 73 74 20 69 6e 74 26 20 45 ase(const int& E
1790: 78 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 69 xpected, const i
17a0: 6e 74 26 20 52 65 63 65 69 76 65 64 29 20 7b 0d nt& Received) {.
17b0: 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 70 . bool ok = (Exp
17c0: 65 63 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 ected == Receive
17d0: 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 d);.. if(ok) cer
17e0: 72 20 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c r << "PASSED" <<
17f0: 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c timer() << endl
1800: 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 72 20 3c ; else { cerr <
1810: 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 < "FAILED" << ti
1820: 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a mer() << endl;..
1830: 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c cerr << "\to: \
1840: 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 20 3c "" << Expected <
1850: 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c < '\"' << endl <
1860: 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 < "\tx: \"" << R
1870: 65 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 eceived << '\"'
1880: 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 << endl; } }..#d
1890: 65 66 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 efine CASE(N) {c
18a0: 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 err << "Test Cas
18b0: 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e e #" << N << "..
18c0: 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 ." << flush; sta
18d0: 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b rt_time=clock();
18e0: 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 ..#define END. v
18f0: 65 72 69 66 79 5f 63 61 73 65 28 5f 2c 20 53 68 erify_case(_, Sh
1900: 6f 72 74 42 75 67 50 61 74 68 73 28 29 2e 63 6f ortBugPaths().co
1910: 75 6e 74 28 4e 2c 20 44 2c 20 4a 29 29 3b 7d 0d unt(N, D, J));}.
1920: 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a .int main(){....
1930: 43 41 53 45 28 30 29 0d 0a 09 69 6e 74 20 4e 20 CASE(0)...int N
1940: 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 44 5f 5b 5d = 3; ...int D_[]
1950: 20 3d 20 7b 31 7d 3b 0d 0a 09 20 20 76 65 63 74 = {1};... vect
1960: 6f 72 20 3c 69 6e 74 3e 20 44 28 44 5f 2c 20 44 or <int> D(D_, D
1970: 5f 2b 73 69 7a 65 6f 66 28 44 5f 29 2f 73 69 7a _+sizeof(D_)/siz
1980: 65 6f 66 28 2a 44 5f 29 29 3b 20 0d 0a 09 69 6e eof(*D_)); ...in
1990: 74 20 4a 20 3d 20 31 3b 20 0d 0a 09 69 6e 74 20 t J = 1; ...int
19a0: 5f 20 3d 20 32 34 3b 20 0d 0a 45 4e 44 0d 0a 43 _ = 24; ..END..C
19b0: 41 53 45 28 31 29 0d 0a 09 69 6e 74 20 4e 20 3d ASE(1)...int N =
19c0: 20 31 32 33 34 35 36 37 38 39 3b 20 0d 0a 09 69 123456789; ...i
19d0: 6e 74 20 44 5f 5b 5d 20 3d 20 7b 30 7d 3b 0d 0a nt D_[] = {0};..
19e0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
19f0: 44 28 44 5f 2c 20 44 5f 2b 73 69 7a 65 6f 66 28 D(D_, D_+sizeof(
1a00: 44 5f 29 2f 73 69 7a 65 6f 66 28 2a 44 5f 29 29 D_)/sizeof(*D_))
1a10: 3b 20 0d 0a 09 69 6e 74 20 4a 20 3d 20 33 3b 20 ; ...int J = 3;
1a20: 0d 0a 09 69 6e 74 20 5f 20 3d 20 36 34 33 34 39 ...int _ = 64349
1a30: 39 34 37 35 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 9475; ..END..CAS
1a40: 45 28 32 29 0d 0a 09 69 6e 74 20 4e 20 3d 20 35 E(2)...int N = 5
1a50: 3b 20 0d 0a 09 69 6e 74 20 44 5f 5b 5d 20 3d 20 ; ...int D_[] =
1a60: 7b 30 2c 20 31 30 2c 20 32 7d 3b 0d 0a 09 20 20 {0, 10, 2};...
1a70: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 44 28 44 vector <int> D(D
1a80: 5f 2c 20 44 5f 2b 73 69 7a 65 6f 66 28 44 5f 29 _, D_+sizeof(D_)
1a90: 2f 73 69 7a 65 6f 66 28 2a 44 5f 29 29 3b 20 0d /sizeof(*D_)); .
1aa0: 0a 09 69 6e 74 20 4a 20 3d 20 34 3b 20 0d 0a 09 ..int J = 4; ...
1ab0: 69 6e 74 20 5f 20 3d 20 33 38 32 38 31 3b 20 0d int _ = 38281; .
1ac0: 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 0d 0a 09 .END..CASE(3)...
1ad0: 69 6e 74 20 4e 20 3d 20 31 30 30 30 3b 20 0d 0a int N = 1000; ..
1ae0: 09 69 6e 74 20 44 5f 5b 5d 20 3d 20 7b 30 2c 31 .int D_[] = {0,1
1af0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
1b00: 6e 74 3e 20 44 28 44 5f 2c 20 44 5f 2b 73 69 7a nt> D(D_, D_+siz
1b10: 65 6f 66 28 44 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(D_)/sizeof(*
1b20: 44 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 4a 20 3d D_)); ...int J =
1b30: 20 31 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 34 1; ...int _ = 4
1b40: 39 39 36 30 30 30 3b 20 0d 0a 45 4e 44 0d 0a 43 996000; ..END..C
1b50: 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 4e 20 3d ASE(4)...int N =
1b60: 20 34 37 3b 20 0d 0a 09 69 6e 74 20 44 5f 5b 5d 47; ...int D_[]
1b70: 20 3d 20 7b 33 7d 3b 0d 0a 09 20 20 76 65 63 74 = {3};... vect
1b80: 6f 72 20 3c 69 6e 74 3e 20 44 28 44 5f 2c 20 44 or <int> D(D_, D
1b90: 5f 2b 73 69 7a 65 6f 66 28 44 5f 29 2f 73 69 7a _+sizeof(D_)/siz
1ba0: 65 6f 66 28 2a 44 5f 29 29 3b 20 0d 0a 09 69 6e eof(*D_)); ...in
1bb0: 74 20 4a 20 3d 20 36 3b 20 0d 0a 09 69 6e 74 20 t J = 6; ...int
1bc0: 5f 20 3d 20 31 39 35 33 35 34 31 36 35 3b 20 0d _ = 195354165; .
1bd0: 0a 45 4e 44 0d 0a 43 41 53 45 28 35 29 0d 0a 09 .END..CASE(5)...
1be0: 69 6e 74 20 4e 20 3d 20 32 30 30 3b 20 0d 0a 09 int N = 200; ...
1bf0: 69 6e 74 20 44 5f 5b 5d 20 3d 20 7b 20 30 2c 31 int D_[] = { 0,1
1c00: 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 ,2,3,4,5,6,7,8,9
1c10: 2c 31 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f ,10 };... vecto
1c20: 72 20 3c 69 6e 74 3e 20 44 28 44 5f 2c 20 44 5f r <int> D(D_, D_
1c30: 2b 73 69 7a 65 6f 66 28 44 5f 29 2f 73 69 7a 65 +sizeof(D_)/size
1c40: 6f 66 28 2a 44 5f 29 29 3b 20 0d 0a 09 69 6e 74 of(*D_)); ...int
1c50: 20 4a 20 3d 20 31 30 3b 20 0d 0a 09 69 6e 74 20 J = 10; ...int
1c60: 5f 20 3d 20 33 31 36 38 36 30 32 38 39 3b 0d 0a _ = 316860289;..
1c70: 45 4e 44 0d 0a 43 41 53 45 28 36 29 0d 0a 09 69 END..CASE(6)...i
1c80: 6e 74 20 4e 20 3d 20 31 30 30 30 30 30 30 30 30 nt N = 100000000
1c90: 30 3b 20 0d 0a 09 69 6e 74 20 44 5f 5b 5d 20 3d 0; ...int D_[] =
1ca0: 20 7b 20 30 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 { 0,1,2,3,4,5,6
1cb0: 2c 37 2c 38 2c 39 2c 31 30 20 7d 3b 0d 0a 09 76 ,7,8,9,10 };...v
1cc0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 44 28 44 5f ector <int> D(D_
1cd0: 2c 20 44 5f 2b 73 69 7a 65 6f 66 28 44 5f 29 2f , D_+sizeof(D_)/
1ce0: 73 69 7a 65 6f 66 28 2a 44 5f 29 29 3b 0d 0a 09 sizeof(*D_));...
1cf0: 69 6e 74 20 4a 20 3d 20 31 30 3b 0d 0a 09 69 6e int J = 10;...in
1d00: 74 20 5f 20 3d 20 2d 31 30 30 3b 0d 0a 45 4e 44 t _ = -100;..END
1d10: 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 ..}..// END CUT
1d20: 48 45 52 45 0d 0a HERE..