4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: long long dp[51][51][51][51]; // y,x,n,i 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: struct CountPaths 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector <int> difPaths(int r, int c, vector <int> fieldrow, vector <int> fieldcol) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int k = fieldrow.size(); 4fd800b3a8 2011-02-23 kinaba: map< pair<int,int>, int > f; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<fieldrow.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: f[make_pair(fieldrow[i],fieldcol[i])] = i; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: memset(dp, 0, sizeof(dp)); 4fd800b3a8 2011-02-23 kinaba: if( f.count( make_pair(1,1) ) ) 4fd800b3a8 2011-02-23 kinaba: dp[1][1][1][ f[make_pair(1,1)]+1 ] = 1; 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: dp[1][1][0][0] = 1; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int y=1; y<=r; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=(y==1?2:1); x<=c; ++x) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( f.count(make_pair(y,x)) ) { 4fd800b3a8 2011-02-23 kinaba: int I = f[make_pair(y,x)]; 4fd800b3a8 2011-02-23 kinaba: for(int n=1; n<=k; ++n) { 4fd800b3a8 2011-02-23 kinaba: int sum = 0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<=I; ++i) { 4fd800b3a8 2011-02-23 kinaba: if( y>=2 ) 4fd800b3a8 2011-02-23 kinaba: sum += dp[y-1][x][n-1][i]; 4fd800b3a8 2011-02-23 kinaba: if( x>=2 ) 4fd800b3a8 2011-02-23 kinaba: sum += dp[y][x-1][n-1][i]; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: dp[y][x][n][I+1] = sum % 1000007; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } else { 4fd800b3a8 2011-02-23 kinaba: for(int n=0; n<=k; ++n) { 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<=k; ++i) { 4fd800b3a8 2011-02-23 kinaba: int sum = 0; 4fd800b3a8 2011-02-23 kinaba: if( y>=2 ) 4fd800b3a8 2011-02-23 kinaba: sum += dp[y-1][x][n][i]; 4fd800b3a8 2011-02-23 kinaba: if( x>=2 ) 4fd800b3a8 2011-02-23 kinaba: sum += dp[y][x-1][n][i]; 4fd800b3a8 2011-02-23 kinaba: dp[y][x][n][i] = sum % 1000007; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<int> ans; 4fd800b3a8 2011-02-23 kinaba: for(int n=0; n<=k; ++n) { 4fd800b3a8 2011-02-23 kinaba: int sum = 0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<=k; ++i) 4fd800b3a8 2011-02-23 kinaba: sum += dp[r][c][n][i]; 4fd800b3a8 2011-02-23 kinaba: ans.push_back( sum % 1000007 ); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return ans; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: };