さてDiv2 Hard。
http://community.topcoder.com/stat?c=problem_statement&pm=12467
問題
N個の点の座標が格子点で与えられる。
ここからMターン各点は隣接する格子点に動く。
Mターン後に全部の点が同じ点にくるような組み合わせの数を答える。
解法
なんか似た問題見たことある…と思ったら、Autumn Festの問Eだ。
移動距離の条件などは違うけどね。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_05
ある点がMターン後に別の点に行くパターンは、上下左右の回数を組み合わせ計算で求めることもできる。
ただ、この組み合わせ計算はめんどい。
ここで上記Automn Fest Eの解説を見ると、「原点からDFSすれば、各点に行くパターン数が求められる」とある。
今回の問題もこれを採用。
原点からMターン後に各点に行く場合の数をDPで計算。
N個の点は(0,0)-(50,50)の内部にあり、M<=50なので、(-50,-50)-(100,100)の点に対し、N個の点がMターン後にたどり着く場合の数を掛け合わせればよい。
ll dp[51][105][105]; ll MO=1000000007; class WolfPackDivTwo { public: int calc(vector <int> X, vector <int> Y, int m) { int n,x,y,i; int N=X.size(); ZERO(dp); dp[0][52][52]=1; for(n=1;n<=m;n++) { for(x=2;x<=102;x++) for(y=2;y<=102;y++) { dp[n][x-1][y]=(dp[n][x-1][y]+dp[n-1][x][y])%MO; dp[n][x+1][y]=(dp[n][x+1][y]+dp[n-1][x][y])%MO; dp[n][x][y-1]=(dp[n][x][y-1]+dp[n-1][x][y])%MO; dp[n][x][y+1]=(dp[n][x][y+1]+dp[n-1][x][y])%MO; } } ll pat=0; for(x=-50;x<=100;x++) for(y=-50;y<=100;y++) { ll tpat=1; FOR(i,N) { if(abs(X[i]-x)+abs(Y[i]-y)>m) { tpat=0; break; } tpat = (tpat * dp[m][52+X[i]-x][52+Y[i]-y]) % MO; } pat=(pat+tpat)%MO; } return (int)pat; } };
まとめ
Div2 Hardの割にさっくり解けた問題。
Autumn Festの成果が出たってもんだ。
…残念ながら、問題空間が増えたDiv1 Hardではこれは使えないんだけどね…。