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