TopCoder SRM 566 Div1 Medium PenguinEmperor

続いてMedium。
今回解けた人が100人以上いたので、500ptとはいえそこまで難しくはない問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12338

円形に配置された都市群で、X日目に時計回りまたは反時計周りにX個先の都市に移動される。
都市の数Cと日数Dが与えられたとき、元の都市に戻る組み合わせ数を求める。

Cは350までと小さいが、Dは上限10^18と大きい。
まず、DがC以上になった場合実質移動する都市はD%Cなので、C日までで移動する組み合わせをDPを求めていく。
注意点は、「同じ移動経路」とみなされる２つの移動経路の条件が「毎日同じ都市に止まること」であること。
よって、普通の日は時計回り・反時計回りで別の都市につくので、合計組み合わせ数は毎日倍々で増えていくけど、C/2日目やC日目は時計回り・反時計回りどちらも同じ都市にたどり着くので、これらの日は増えない。

これでC日移動した場合、各都市に止まる組み合わせ数がわかったので、後はこれをD/C回繰り返し、また最後に残るD%C日分の移動を計算すればよい。
ただ、今回D/Cもかなり大きいので畳み込みを行う。
C日移動パターン数を２回掛け合わせて2C日の移動パターン数を求め、そこから4C、8C…と倍々して求め必要な数を掛け合わせていけばよい。

計算量は、最初のC日までの処理でO(C^2)、畳み込み計算でO(C^2 log(D/C))だね。
多くの回答は行列の畳み込み演算にしていたけど、これだとO(C^3 log(D/C))かかるので割と時間がギリギリ。

もうちょいCが大きいと行列の畳み込み演算でTLEしてくれたんだけどなぁ…。

ll MO=1000000007LL;
class PenguinEmperor {
	ll dp[360][360];
	ll dp2[62][360];
	ll dp3[2][360];
	int C;
	ll D;
	public:
	int countJourneys(int numCities, long long daysPassed) {
		int x,y,z;
		C=numCities;
		D=daysPassed;
		ZERO(dp);
		dp[0][0]=1;
		FOR(x,C) {
			FOR(y,C) {
				dp[x+1][(y+x+1)%C] = (dp[x+1][(y+x+1)%C]+dp[x][y]) % MO;
				if((x+1)*2 != C && x+1!=C) dp[x+1][(y+C-(x+1))%C] = (dp[x+1][(y+C-(x+1))%C]+dp[x][y]) % MO;
			}
		}
		
		ll nl=D / C;
		int cur,tar;
		ZERO(dp2);
		ZERO(dp3);
		FOR(y,C) dp2[0][y]=dp[C][y];
		dp3[0][0]=1;
		cur=0; tar=1;
		FOR(x,61) {
			if(nl & (1LL<<x)) {
				FOR(y,C) dp3[tar][y]=0;
				FOR(y,C) FOR(z,C) dp3[tar][(y+z)%C] = (dp3[tar][(y+z)%C] + dp3[cur][y]*dp2[x][z]) % MO;
				cur^=1;
				tar^=1;
			}
			FOR(y,C) FOR(z,C) dp2[x+1][(y+z)%C] = (dp2[x+1][(y+z)%C] + dp2[x][y]*dp2[x][z]) % MO;
		}
		
		ll res=0;
		FOR(x,C) res = (res + dp3[cur][x]*dp[D%C][x]) % MO;
		return res;
		
	}
};

まとめ

シンプルな条件ながらDP+畳み込み乗算と面白い問題でした。
「同じ移動経路」の条件がちょっとややこしかったね。