New Year Contest 2015 : J - ランダムウォーク

こういうの思いつかないなぁ。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_10

問題

初期状態でプレイヤーは２次元座標上の原点にいる。
１秒毎に、上下左右いずれか等確率で１進む。

N秒後までに１回以上経由した異なる格子点の数の期待値(に4^Nを掛けたもの)を求めよ。

解法

自力で解けず他の解法を参考に解いた。
途中同じ点を複数回通らないなら、N秒で(N+1)個の点に移動できるので期待値は(N+1)*4^Nである。
そこから同じ点を通るケースを減算していく。

ある位置からM秒で初めてその位置に戻るケースの組み合わせ数F(M)を考える。
「初めて」を除き何度目でもいいからM秒後に元の位置に戻ってくるケースの組み合わせ数G(M)は、a回上に移動し、a回下に移動し、(N-a)/2回左に移動し、(N-a)/2回右に移動すると考えると、0≦a≦N/2となる各aについての和である。

G(M)からF(M)を求めるには、G(M)から各iについてF(i)*G(M-i)を引けばよい。すなわちi秒後に一度初めて元の点に戻り、また残り(M-i)秒後に元の点に戻っているケースである。

ここまででF(M)を求めると答えはもうすぐである。
N手の移動中F(M)に該当するケースを含むのは、F(M)に、M秒で元に戻るタイミングの開始時間が(N-M+1)通り、かつ残り(N-M)時間の移動方法が4^(N-M)なのでその積である。
F(M)に該当するケース１個あたり１個通る経由点が減るので、(N+1)*4^NからF(M)*(N-M+1)*4^(N-M)を引いていけば良い。

ll N,M;
const int CN=5005;
ll C[CN][CN];
ll dp[5005],dp2[5005], p4[5005];
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(x,CN) C[x][0]=C[x][x]=1;
	for(i=1;i<CN;i++) for(j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;
	
	p4[0]=1;
	FOR(i,5000) p4[i+1]=p4[i]*4%M;
	
	ret = (N+1)*p4[N]%M;
	
	for(i=2;i<=N;i+=2) {
		FOR(j,i+1) if(j%2==0) dp[i] += C[i][j]*C[(i-j)][(i-j)/2]%M*C[j][j/2]%M;
		dp2[i]=((dp[i]%M)+M)%M;
		for(j=2;j<i;j+=2) dp[i] -= dp[i-j]*dp2[j]%M;
		dp[i]=((dp[i]%M)+M)%M;
		ret -= dp[i]*(N-i+1)%M*p4[N-i]%M;
	}
	cout<<(ret%M+M)%M<<endl;
}

まとめ

前に通った点に初めて戻ってくるなら、その時１個経由地が減るという考え方。
これは自力では思い浮かばないなぁ。