题意

已知一个长度为 $n$ 的 $01$ 序列 $A$ 。$(2\le n\le 100)$。

现在对其进行操作，每次均匀随机选择两个数 $i,j$ 满足 $1\le i<j\le n$，然后交换 $A_i$ 和 $A_j$。

一共进行 $k$ 次操作 $(1\le k\le 10^9)$，求进行完操作后整个序列单调不增的概率。

答案对 $10^9+7$ 取模。

题解

计 $s_0$ 表示序列中 $0$ 的个数，$s_1$ 表示序列中 $1$ 的个数。

那么目标的序列就是前面 $s_0$ 个 $0$，后面 $s_1$ 个 $1$ 的序列。

所以如果前 $s_0$ 的位置中有 $1$ 那么这些 $1$ 出现在哪里都一样。

考虑一个暴力 $dp$。

设 $f_{i,j}$ 表示前 $s_0$ 个位置中有 $i$ 个 $1$ ，操作了 $j$ 次的概率。

容易得到状态转移方程：

$$f_{i,j+1}=f_{i,j}\times (\frac{s_0\times (s_0-1)}{2}+\frac{s_1\times (s_1-1)}{2}+i\times (s_1-i)+i\times (s_0-i)) \\ \\ f_{i-1,j+1}=f_{i,j}\times i\times i \\ \\ f_{i+1,j+1}=f{i,j}\times (s_0-i)\times (s_1-i) $$

这样转移的时间复杂度为 $O(nk)$，无法通过此题。

发现 $n$ 非常小，而 $k$ 却很大，直接矩阵快速幂即可。

时间复杂度 $O(n^3\lg k)$。

#include<bits/stdc++.h>
using namespace std;
const int N=105,mod=1e9+7;
struct mat{int cnt[N][N];};
int sum,p[N],s[2],siz;
mat operator*(mat a,mat b){
	mat ans;
	memset(ans.cnt,0,sizeof(ans.cnt));
	for(int i=0;i<=siz;i++)
		for(int j=0;j<=siz;j++)
			for(int k=0;k<=siz;k++)
				ans.cnt[i][j]=(ans.cnt[i][j]+1ll*a.cnt[i][k]*b.cnt[k][j]%mod)%mod;
	return ans;
}
int kuai(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
	return ans;
}
mat kuai(mat a,int b){
	mat ans;
	memset(ans.cnt,0,sizeof(ans.cnt));
	for(int i=0;i<=siz;i++)ans.cnt[i][i]=1;
	for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;
	return ans;
}
int n,m;
mat a,c;
int main(){
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>p[i],s[p[i]]++;
	siz=min(s[0],s[1]);
	for(int i=1;i<=s[0];i++)sum+=p[i];
	a.cnt[0][sum]=1;
	for(int i=0;i<=siz;i++)c.cnt[i][i]=(1ll*s[0]*(s[0]-1)/2%mod+s[1]*(s[1]-1)/2%mod)%mod;
	for(int i=0;i<=siz;i++){
		if(i>0)c.cnt[i][i-1]=1ll*i*i%mod;
		(c.cnt[i][i]+=(1ll*i*(s[1]-i)%mod+1ll*(s[0]-i)*i%mod)%mod)%=mod;
		if(i<siz)c.cnt[i][i+1]=1ll*(s[0]-i)*(s[1]-i)%mod;
	}
	int Inv=kuai(1ll*n*(n-1)/2%mod,mod-2);
	for(int i=0;i<=siz;i++){
		if(i>0)c.cnt[i][i-1]=1ll*c.cnt[i][i-1]*Inv%mod;
		c.cnt[i][i]=1ll*c.cnt[i][i]*Inv%mod;
		if(i<siz)c.cnt[i][i+1]=1ll*c.cnt[i][i+1]*Inv%mod;
	}
	a=a*kuai(c,m);
	cout<<a.cnt[0][0];
}