SRM573 Div2 Hard "TeamContestEasy"
訳
N匹のオオカミがいて、各々の居る位置が
2次元座標x(0),x(1)...x(N-1) y(0),y(1)...y(N-1)で与えられている。
オオカミたちはM回動く。
オオカミが(x,y)にいるとすると、1回で(x+1,y)(x-1,y)(x,y+1)(x,y-1)の
いずれかに移動できる。
彼らの目標は、M回移動した時に、全員が同じポイントに到達する事である。
このポイントは任意に選べる。
彼らが目標を達成するような動き方が何パターンあるかを返せ。
制約
2 <= N <= 50
0 <= x(i), y(i) <= 50
1 <= M <= 50
ググル
おお、こんなものが!ありがたやありがたや~
SRM573 WolfPack 解説
うーん・・・nCk mod p の求め方がよく分からないんだよなぁ
ここはDPで行こう。
dp[t][dx][dy] := t回の移動で(x+dx, y+dy)マスに行く移動方法は何パターンあるか?
(50, 50)を原点とするとdp[0][50][50] = 1
配るDPだと更新の仕方はこう
dp[t+1][dx+1][dy] += dp[t][dx][dy];
dp[t+1][dx-1][dy] += dp[t][dx][dy];
dp[t+1][dx][dy+1] += dp[t][dx][dy];
dp[t+1][dx][dy-1] += dp[t][dx][dy];
このdpを使いまわせばいけそう。
ランデブーポイントは制約から
(-50 -50) ~ (100 100)の範囲に収まる。
これを1つ1つ調べていこう。
ソースコード
typedef long long ll; const int MOD = 1000000007; int dp[51][101][101]; class WolfPackDivTwo { public: int calc(vector <int> x, vector <int> y, int m){ int n = x.size(); // dpを初期化 for( int t = 0; t <= 50; t++ ){ for( int dy = 0; dy <= 100; dy++ ){ for( int dx = 0; dx <= 100; dx++ ){ dp[t][dy][dx] = 0; } } } dp[0][50][50] = 1; for( int t = 0; t < m; t++ ){ for( int ty = 0; ty <= 100; ty++ ){ for( int tx = 0; tx <= 100; tx++ ){ static int dx[] = { 0, 0, -1, 1 }; static int dy[] = { -1, 1, 0, 0 }; for( int d = 0; d < 4; d++ ){ int tty = ty + dy[d]; int ttx = tx + dx[d]; if( tty < 0 || 100 < tty || ttx < 0 || 100 < ttx ) continue; dp[t+1][tty][ttx] += dp[t][ty][tx]; dp[t+1][tty][ttx] %= MOD; } } } } // ランデブーポイントを一つ一つ調べる int res = 0; for( int ty = -50; ty <= 100; ty++ ){ for( int tx = -50; tx <= 100; tx++ ){ ll add = 1; for( int i = 0; i < n; i++ ){ int dx = 50 + tx - x[i]; int dy = 50 + ty - y[i]; if( dx < 0 || 100 < dx || dy < 0 || 100 < dy ) { add = 0; }else{ add = add * dp[m][dy][dx]; } add %= MOD; } res += static_cast<int>(add); res %= MOD; } } return res; } };