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: };