kmjp's blog

競技プログラミング参加記です

Codeforces #553 Div2 F. Sonya and Informatics

Div2Fにしては正答者が多い問題。
https://codeforces.com/contest/1151/problem/F

問題

01で構成される数列がある。
ある2つの要素が等確率で選択され、それを入れ替える、ということをK回繰り返す。

その結果、数列が昇順になる確率を求めよ。

解法

今正しくない位置がn個あるとする。
1回スワップした場合のnの変化を漸化式で表すと、その遷移を行列で表現すれば行列累乗に持ち込める。

int N,K;
ll mo=1000000007;
int A[101],B[101];
int num[2][2];

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;
}

const int MAT=101;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

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

Mat M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		B[i]=A[i];
	}
	
	sort(B,B+N);
	FOR(i,N) num[A[i]][B[i]]++;
	int n0=num[0][0]+num[1][0];
	int n1=num[0][1]+num[1][1];
	ll re=modpow(comb(N,2));
	for(int ee=0;ee<=n0;ee++) {
		int eo=n0-ee,oe=eo;
		int oo=n1-eo;
		
		if(oo<0||eo<0||oe<0) continue;
		
		M.v[ee][ee]=(comb(ee,2)+comb(oo,2)+comb(eo,2)+comb(oe,2)+ee*(eo+oe)+oo*(eo+oe))*re%mo;
		if(ee>=1) M.v[ee-1][ee]=(ee*oo)*re%mo;
		if(ee+1<=n0) M.v[ee+1][ee]=(eo*oe)*re%mo;
	}
	
	Mat L=powmat(K,M,n0+1);
	
	cout<<L.v[n0][num[0][0]]<<endl;
	
	
	
}

まとめ

まぁこれはさほど難しくないかな。