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; }
まとめ
まぁこれはさほど難しくないかな。