Artifact 5b09cb848fba39308e5160aa3565b9a0ee09ebcc:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 3e >.#include <map>
0020: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 73 74 72 69 .#include <cstri
0030: 6e 67 3e 0a 75 73 69 6e 67 20 6e 61 6d 65 73 70 ng>.using namesp
0040: 61 63 65 20 73 74 64 3b 0a 0a 0a 6c 6f 6e 67 20 ace std;...long
0050: 6c 6f 6e 67 20 64 70 5b 35 31 5d 5b 35 31 5d 5b long dp[51][51][
0060: 35 31 5d 5b 35 31 5d 3b 20 2f 2f 20 79 2c 78 2c 51][51]; // y,x,
0070: 6e 2c 69 0a 0a 73 74 72 75 63 74 20 43 6f 75 6e n,i..struct Coun
0080: 74 50 61 74 68 73 0a 7b 0a 09 76 65 63 74 6f 72 tPaths.{..vector
0090: 20 3c 69 6e 74 3e 20 64 69 66 50 61 74 68 73 28 <int> difPaths(
00a0: 69 6e 74 20 72 2c 20 69 6e 74 20 63 2c 20 76 65 int r, int c, ve
00b0: 63 74 6f 72 20 3c 69 6e 74 3e 20 66 69 65 6c 64 ctor <int> field
00c0: 72 6f 77 2c 20 76 65 63 74 6f 72 20 3c 69 6e 74 row, vector <int
00d0: 3e 20 66 69 65 6c 64 63 6f 6c 29 0a 09 7b 0a 09 > fieldcol)..{..
00e0: 09 69 6e 74 20 6b 20 3d 20 66 69 65 6c 64 72 6f .int k = fieldro
00f0: 77 2e 73 69 7a 65 28 29 3b 0a 09 09 6d 61 70 3c w.size();...map<
0100: 20 70 61 69 72 3c 69 6e 74 2c 69 6e 74 3e 2c 20 pair<int,int>,
0110: 69 6e 74 20 3e 20 66 3b 0a 09 09 66 6f 72 28 69 int > f;...for(i
0120: 6e 74 20 69 3d 30 3b 20 69 3c 66 69 65 6c 64 72 nt i=0; i<fieldr
0130: 6f 77 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a ow.size(); ++i).
0140: 09 09 09 66 5b 6d 61 6b 65 5f 70 61 69 72 28 66 ...f[make_pair(f
0150: 69 65 6c 64 72 6f 77 5b 69 5d 2c 66 69 65 6c 64 ieldrow[i],field
0160: 63 6f 6c 5b 69 5d 29 5d 20 3d 20 69 3b 0a 0a 09 col[i])] = i;...
0170: 09 6d 65 6d 73 65 74 28 64 70 2c 20 30 2c 20 73 .memset(dp, 0, s
0180: 69 7a 65 6f 66 28 64 70 29 29 3b 0a 09 09 69 66 izeof(dp));...if
0190: 28 20 66 2e 63 6f 75 6e 74 28 20 6d 61 6b 65 5f ( f.count( make_
01a0: 70 61 69 72 28 31 2c 31 29 20 29 20 29 0a 09 09 pair(1,1) ) )...
01b0: 09 64 70 5b 31 5d 5b 31 5d 5b 31 5d 5b 20 66 5b .dp[1][1][1][ f[
01c0: 6d 61 6b 65 5f 70 61 69 72 28 31 2c 31 29 5d 2b make_pair(1,1)]+
01d0: 31 20 5d 20 3d 20 31 3b 0a 09 09 65 6c 73 65 0a 1 ] = 1;...else.
01e0: 09 09 09 64 70 5b 31 5d 5b 31 5d 5b 30 5d 5b 30 ...dp[1][1][0][0
01f0: 5d 20 3d 20 31 3b 0a 0a 09 09 66 6f 72 28 69 6e ] = 1;....for(in
0200: 74 20 79 3d 31 3b 20 79 3c 3d 72 3b 20 2b 2b 79 t y=1; y<=r; ++y
0210: 29 0a 09 09 66 6f 72 28 69 6e 74 20 78 3d 28 79 )...for(int x=(y
0220: 3d 3d 31 3f 32 3a 31 29 3b 20 78 3c 3d 63 3b 20 ==1?2:1); x<=c;
0230: 2b 2b 78 29 0a 09 09 7b 0a 09 09 09 69 66 28 20 ++x)...{....if(
0240: 66 2e 63 6f 75 6e 74 28 6d 61 6b 65 5f 70 61 69 f.count(make_pai
0250: 72 28 79 2c 78 29 29 20 29 20 7b 0a 09 09 09 09 r(y,x)) ) {.....
0260: 69 6e 74 20 49 20 3d 20 66 5b 6d 61 6b 65 5f 70 int I = f[make_p
0270: 61 69 72 28 79 2c 78 29 5d 3b 0a 09 09 09 09 66 air(y,x)];.....f
0280: 6f 72 28 69 6e 74 20 6e 3d 31 3b 20 6e 3c 3d 6b or(int n=1; n<=k
0290: 3b 20 2b 2b 6e 29 20 7b 0a 09 09 09 09 09 69 6e ; ++n) {......in
02a0: 74 20 73 75 6d 20 3d 20 30 3b 0a 09 09 09 09 09 t sum = 0;......
02b0: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 3d for(int i=0; i<=
02c0: 49 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 09 I; ++i) {.......
02d0: 69 66 28 20 79 3e 3d 32 20 29 0a 09 09 09 09 09 if( y>=2 )......
02e0: 09 09 73 75 6d 20 2b 3d 20 64 70 5b 79 2d 31 5d ..sum += dp[y-1]
02f0: 5b 78 5d 5b 6e 2d 31 5d 5b 69 5d 3b 0a 09 09 09 [x][n-1][i];....
0300: 09 09 09 69 66 28 20 78 3e 3d 32 20 29 0a 09 09 ...if( x>=2 )...
0310: 09 09 09 09 09 73 75 6d 20 2b 3d 20 64 70 5b 79 .....sum += dp[y
0320: 5d 5b 78 2d 31 5d 5b 6e 2d 31 5d 5b 69 5d 3b 0a ][x-1][n-1][i];.
0330: 09 09 09 09 09 7d 0a 09 09 09 09 09 64 70 5b 79 .....}......dp[y
0340: 5d 5b 78 5d 5b 6e 5d 5b 49 2b 31 5d 20 3d 20 73 ][x][n][I+1] = s
0350: 75 6d 20 25 20 31 30 30 30 30 30 37 3b 0a 09 09 um % 1000007;...
0360: 09 09 7d 0a 09 09 09 7d 20 65 6c 73 65 20 7b 0a ..}....} else {.
0370: 09 09 09 09 66 6f 72 28 69 6e 74 20 6e 3d 30 3b ....for(int n=0;
0380: 20 6e 3c 3d 6b 3b 20 2b 2b 6e 29 20 7b 0a 09 09 n<=k; ++n) {...
0390: 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
03a0: 69 3c 3d 6b 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 i<=k; ++i) {....
03b0: 09 09 09 69 6e 74 20 73 75 6d 20 3d 20 30 3b 0a ...int sum = 0;.
03c0: 09 09 09 09 09 09 69 66 28 20 79 3e 3d 32 20 29 ......if( y>=2 )
03d0: 0a 09 09 09 09 09 09 09 73 75 6d 20 2b 3d 20 64 ........sum += d
03e0: 70 5b 79 2d 31 5d 5b 78 5d 5b 6e 5d 5b 69 5d 3b p[y-1][x][n][i];
03f0: 0a 09 09 09 09 09 09 69 66 28 20 78 3e 3d 32 20 .......if( x>=2
0400: 29 0a 09 09 09 09 09 09 09 73 75 6d 20 2b 3d 20 )........sum +=
0410: 64 70 5b 79 5d 5b 78 2d 31 5d 5b 6e 5d 5b 69 5d dp[y][x-1][n][i]
0420: 3b 0a 09 09 09 09 09 09 64 70 5b 79 5d 5b 78 5d ;.......dp[y][x]
0430: 5b 6e 5d 5b 69 5d 20 3d 20 73 75 6d 20 25 20 31 [n][i] = sum % 1
0440: 30 30 30 30 30 37 3b 0a 09 09 09 09 09 7d 0a 09 000007;......}..
0450: 09 09 09 7d 0a 09 09 09 7d 0a 09 09 7d 0a 0a 09 ...}....}...}...
0460: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 61 6e 73 .vector<int> ans
0470: 3b 0a 09 09 66 6f 72 28 69 6e 74 20 6e 3d 30 3b ;...for(int n=0;
0480: 20 6e 3c 3d 6b 3b 20 2b 2b 6e 29 20 7b 0a 09 09 n<=k; ++n) {...
0490: 09 69 6e 74 20 73 75 6d 20 3d 20 30 3b 0a 09 09 .int sum = 0;...
04a0: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
04b0: 3d 6b 3b 20 2b 2b 69 29 0a 09 09 09 09 73 75 6d =k; ++i).....sum
04c0: 20 2b 3d 20 64 70 5b 72 5d 5b 63 5d 5b 6e 5d 5b += dp[r][c][n][
04d0: 69 5d 3b 0a 09 09 09 61 6e 73 2e 70 75 73 68 5f i];....ans.push_
04e0: 62 61 63 6b 28 20 73 75 6d 20 25 20 31 30 30 30 back( sum % 1000
04f0: 30 30 37 20 29 3b 0a 09 09 7d 0a 09 09 72 65 74 007 );...}...ret
0500: 75 72 6e 20 61 6e 73 3b 0a 09 7d 0a 7d 3b 0a urn ans;..}.};.