ARC12 D - Don’t worry. Be Together

http://arc012.contest.atcoder.jp/tasks/arc012_4

二次元平面上の格子点(x,y) にいる人間が、原点(0,0)に移動したい。
この時、Tターン後に原点にいる移動方法の組み合わせを求めることが出来ればよい。

移動が可能な条件

Tターン後に原点へ移動が可能な条件は、x+y <= T かつ、x+yとTの偶奇が一致している事。
x+y <= Tは明らかとして、x+yとTの偶奇についての証明無駄に丁寧なのでわかってる人は飛ばしてください

まず1次元で考える。 Txターン後に原点へと移動したい
x軸方向と逆方向の2通りの動き方があり、座標xからそれぞれ(a,b)だけ移動したとすると、移動後の座標は x+a-b となる。
ここで x+a-b = 0,a+b = Tx より a = (Tx-x)/2 , b = (Tx+x)/2
a,bが整数なので、Tx-xは偶数。以上よりTx,xの偶奇は一致する。

同様に2次元で考える。Tx,Tyをそれぞれx軸,y軸の移動に使用したターン数(Tx + Ty = T)と置くと
上記の証明により、Tx,Tyはそれぞれx,yと偶奇が一致する必要がある。
ここでTとx+yの偶奇が一致しているとすると
i)x,yが奇数 ii) x,yのどちらか一方が奇数 iii) x,yが偶数
の3通りがあり、それぞれ x = 2n(+1) y = 2m(+1)などと置くと証明が可能

以上より、原点(0,0)へと移動可能な条件を求められた。

移動可能な組み合わせ

次に(x,y)から(0,0)へと移動する組み合わせが何通りあるか考える
対称性より、(x,y)から移動を始める場合と(|x|,|y|)から移動を始めた場合では組み合わせの個数は変わらないので、 x,y >= 0とする。

まず簡単な場合としてx+y = Tの時を考える。
この時の組み合わせは $_TC_x$ 通りである。
次に x+y < Tの時を考える。x軸方向を右、y軸方向を上とすると
4方向それぞれに(右,左,上,下) = (a,x+a,b,y+b) ターン動けばよいことが分かる。
ここで、合計のターンがTになるようにa,b(>= 0) を調整する必要がある。
x+y+2(a+b) = Tなので、a+b = T-x-y
m = a+b = (T-x-y)/2置くと (右,左,上,下) = (a,x+a,m-a,y+m-a) と書ける。
以上から、(x,y)から(0,0)へ移動する組み合わせは
$\sum^{m}_{a=0}\frac{T!}{a! * (x+a)! * (m-a)! * (y+m-a)!}$
これを全ての人間N人について計算すれば答えが出せるが、一人につき最大O(T/2)なのでTLEする
この式を変形するとO(1)？になる。もう少し大きいかも

先ほどの式の $\sum$ の中身は ${}_nC_k$ の積の形で表すことができる。

$\frac{T!}{a! * (x+a)! * (m-a)! * (y+m-a)!} = {}_TC_a * {}_{T-a}C_{x+a} * {}_{T-2*a-x}C_{m-a}$

ようするにTからa個を選び、残りからx+a個を選び、更に残りからm-a個を選択する組み合わせを表している。
aを減らして $\sum$ の外側に出すことを目標とする。
まずT個からm個を選び、集合をA,Bに分ける。(|A| = m,|B| = T-mとなる)
更に集合Aからa個を選び、集合Bからy+m-a個を選ぶ組み合わせを考えれば、 $\sum$ から一つだけ項を外に出せる
$\sum^{m}_{a=0}\frac{T!}{a! * (x+a)! * (m-a)! * (y+m-a)!} = {}_TC_m * \sum^{m}_{a=0} {}_mC_a * {}_{T-m}C_{y+m-a}$
大分見やすくなったかもしれない？

さらに、 ${}_mC_a * {}_{T-m}C_{y+m-a}$ について考える。
${}_mC_a * {}_{T-m}C_{y+m-a}$ は、集合Aからa個取り出し、集合Bからy+m-a個を取り出す組み合わせを表している。
このaを、a = 0からmまで変化させた時の全ての組み合わせはつまり、
A+Bの全ての集合から、y+m個の要素を取り出した組み合わせと一致する。
つまり、
$\sum^{m}_{a=0} {}_mC_a * {}_{T-m}C_{y+m-a} = {}_TC_{y+m}$

以上から、ターンTで(x,y)から(0,0)への移動方法が ${}_TC_{m} * {}_TC_{y+m}$ 通りであることが分かった。
y+m = T-x-mなので、 ${}_TC_{m} * {}_TC_{y+m} = {}_TC_{m} * {}_TC_{x+m}$ どちらを使用しても答えは変わらない

後は、modが素数の時にはmod_invを使用して、解がO(T log(modulo))程度で求められる。
満点解法はmodinvをせずに、n!が何回出てきたのかを記憶して、最後に2^p * 3^q * 5^s * 7^r * ... % modulo をする方法となる。 O(N)程度？
この部分はsubmitされているコードを読んだほうがわかりやすいと思う

#include <cstring>
#include <cmath>
#include <iostream>

using namespace std;
typedef long long ll;

int fractors[100000+10];

ll mod_pow(ll x,ll n,ll mod){
	ll ret = 1,p = x;
	while(n){
		if(n&1){
			ret = ret * p % mod;
		}
		p = p * p % mod;
		n /= 2;
	}
	return ret;
}

bool move(int x,int y,int t){
	//条件は x+y <= t and x+yとtの偶奇が一致していること
	if(x+y <= t && (x+y+t) % 2 == 0){

		//m = (t-x-y) / 2と置くと
		//組み合わせは T_C_(x+m) * T_C_m
		// T_C_(x+m) * T_C_m = (t!)^2 / ( (x+m)! * (t-x-m)! * m! * (t-m)! ) 
		int m = (t-x-y) / 2;

		fractors[t] += 2;
		fractors[x+m]--;
		fractors[t-x-m]--;
		fractors[m]--;
		fractors[t-m]--;

		return true;
	}
	return false;
}

int main(){
	int n,t,mod; cin>>n>>t>>mod;

	for(int i = 0; i < n; i++){
		int x,y; cin>>x>>y;
		if(!move(abs(x),abs(y),t)){
			cout << 0 << endl;
			return 0;
		}
	}

	//階乗をべき乗の形に直す
	static int powers[100000+10] = {};
	for(int i = 100000; i >= 0; i--) powers[i] = powers[i+1] + fractors[i];
	
	ll ans = 1;
	//素数のべき乗を計算する。
	//素数に分解して計算しない場合、a^x (x < 0)を計算する必要が出てきて計算が出来ない
	//ex) 4_C_2 = 4! / (2! * 2!) = 4^1 * 3^1 * 2^(-1) * 1^(-1)
	//0!,1! は無視してよい
	static bool prime[100000+10] = {};
	memset(prime,1,sizeof(prime));
	for(int i = 2; i <= 100000; i++) if(prime[i]){
		ll p = 0;
		//int xにすると、 x = 5*10^4 程度で桁あふれする
		for(ll x = i; x <= 100000; x *= i){
			for(ll y = x; y <= 100000; y += x){
				prime[y] = false;
				p += powers[y];
			}
		}
		ans = ans * mod_pow(i,p,mod) % mod; // i^p
	}

	cout << ans << endl;

	return 0;
}

間違ってたら教えてください。