AtCoder ABC #216 : H - Random Robots

久々に見た。
https://atcoder.jp/contests/abc216/tasks/abc216_h

問題

1次元の数直線上に、K体のロボットがおりその座標が与えられる。
このあとN秒間、1秒毎に各ロボットは1/2の確率でその場にとどまるか1進むかを選ぶものとする。
途中どのロボットも同じ座標に同時に存在しない確率を求めよ。

解法

LGV lemmaを変形させて解くことを考える。
LGV lemmaを使おうとすると、各ロボットの移動パターン毎に行列式を求めなければいけない。
これは組み合わせが爆発してしんどいので工夫する。

まず工夫の1つ目として、行列式を求める手続きを分解してみる。
(1...K)の置換を考え、最終的にロボットがその順に並ぶケースを考える。
置換が定まれば、x体目が座標pに並ぶような確率はO(K(N+max(X)))で求められる。
その時、そのような並びになる確率を求めたら、置換が奇置換か偶置換かによって、その確率を解に減算または加算すればよい。

とはいえ実際にK!通り置換を考えると計算量がO(K!(N+max(X)))と多くなってしまうが、そこはよくある並び順の総当たりをBitDPでK!通りから2^K*K通りにするテクを使えばO(2^K*K^2*(N+max(X)))に抑えられる。

int N,K;
int X[1010];

ll dp[1<<10][2049];
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	FOR(i,K) {
		cin>>X[i];
		X[i]++;
	}

	ll ret=0;
	dp[0][0]=1;
	int mask;
	FOR(mask,1<<K) {
		int flip=0;
		for(i=K-1;i>=0;i--) {
			if(mask&(1<<i)) {
				flip^=1;
			}
			else {
				ll S=0;
				FOR(j,2048) {
					if(j>=X[i]) {
						if(flip==0) {
							(dp[mask|(1<<i)][j]+=S*comb(N,j-X[i]))%=mo;
						}
						else {
							(dp[mask|(1<<i)][j]-=S*comb(N,j-X[i]))%=mo;
						}
					}
					
					(S+=dp[mask][j])%=mo;
				}
			}
		}
	}
	
	FOR(j,2018) ret+=dp[(1<<K)-1][j];
	ret=(ret%mo+mo)%mo*modpow(modpow(2,K*N))%mo;
	
	cout<<ret%mo<<endl;
	
}

まとめ

LGV公式を久々に使った。
それ以上に、行列式をこう求めるテクは何気に初めて使ったので勉強になった。