做题时间：2022.10.12
\(【题目描述】\)
给定一个长度为 \(n(n\leq 100)\) 的01串，进行 \(k(k\leq 10^9)\) 次操作，每次操作等概率选择两个位置 \(i,j(1\leq i<j\leq n)\)，交换 \(i,j\) 位置上的数。求 \(k\) 次操作后，该01串变成不降序列的概率，答案对 \(10^9+7\) 取模
\(【输入格式】\)
第一行两个整数 \(n,k\)
第二行 \(n\) 个整数表示01串
\(【输出格式】\)
一行一个整数表示概率 \(\mod 10^9+7\)
\(【考点】\)
计数dp、矩阵快速幂
\(【做法】\)
发现0和1的数量保持不变。假设串中有 \(m\) 个0，那么最终的序列会变成连续 \(m\) 个0和连续 \(n-m\) 个1拼成的串。发现前 \(m\) 个数中0的个数会有影响，于是设 \(f_{i,j}\) 表示第 \(i\) 次操作后前 \(m\) 个数中有 \(j\) 个0的方案数，考虑第 \(i\) 次操作将前 \(m\) 个数中0的个数+1/不变/-1：
- +1则是选择前 \(m\) 个数中的1，共 \(m-(j-1)\) 个，以及后 \(n-m\) 个数中的0，共 \(m-(j-1)\) 个，总共 \((m-j+1)^2\) 种选法，设他为 \(A_j\)，因此方案数为 \(f_{i,j-1}\times A_j\)
- 不变则是在前 \(m\) 个数或后 \(n-m\) 个数之间任意对调，或将前面的0/1与后面对应的0/1对调，共 \(\binom{2}{m}+\binom{2}{n-m}+(m-j)(n-2m+j)+j(m-j)\) 种，设他为 \(B_j\) ，则方案数为 \(f_{i,j}\times B_j\)
- -1则是选择前 \(m\) 个数中的0，共 \(j+1\) 种选择，以及后 \(n-m\) 个数中的1，共 \(n-2m+j+1\) 种选择，总共 \((j+1)(n-2m+j+1)\) 种选法，设他为 \(C_j\)，则方案数为 \(f_{i,j+1}\times C_j\)
也就是： \(f_{i,j}=f_{i,j-1}\times A_j+f_{i,j}\times B_j+f_{i,j+1}\times C_j\)
设 \(t\) 表示前 \(m\) 个数种0的个数，初始化即为 \(f_{0,t}=1\)
然后发现第一维很大，第二维很小，所以可以使用矩阵快速幂，即：
\[\begin{bmatrix} f_{i-1,0} & f_{i-1,1} &\cdots & f_{i-1,m}\\ \end{bmatrix} \times \begin{bmatrix} B_0 & A_1 & 0 & 0 & \cdots & 0 \\ C_0 & B_1 & A_2 & 0&\cdots &0\\ 0 & C_1 & B_2 & A_3 & \cdots & 0\\ 0&0&C_2&B_3 & \cdots & 0\\ \vdots &\vdots&\vdots &\vdots &\ddots &0\\ 0&0&0&0&\cdots &B_m \end{bmatrix} = \begin{bmatrix} f_{i,0} & f_{i,1} & \cdots f_{i,m} \end{bmatrix} \]最后的答案就是：
\[ans=\Large \frac{f_{n,m}}{\sum\limits_{i=2m-n}^m f_{n,i}} \]\(【代码】\)
#include<cstdio>
#include<iomanip>
#include<cstring>
#define int long long
using namespace std;
const int N=1e2+50,mod=1e9+7,Inv2=500000004;
int n,m,k,A[N],B[N],C[N],a[N],t;
struct Matrix{
int num[N][N];
Matrix(){memset(num,0,sizeof num);}
Matrix operator *(const Matrix &b) const{
Matrix c;
for(int i=0;i<=m;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=m;k++){
c.num[i][j]=(c.num[i][j]+num[i][k]*b.num[k][j])%mod;
}
}
}
return c;
}
}base,T,One;
void init()
{
for(int i=0;i<=m;i++) One.num[i][i]=1;
base.num[0][t]=1;
for(int j=0;j<=m;j++){//初始化A,B,C
A[j]=(m-j+1)*(m-j+1)%mod;
B[j]=(n-m)*(n-m-1)*Inv2%mod+m*(m-1)*Inv2%mod+(m-j)*(n-2*m+j)%mod+j*(m-j);
C[j]=(j+1)*(n-2*m+j+1)%mod;
B[j]=(B[j]+mod)%mod;
A[j]=(A[j]+mod)%mod;
C[j]=(C[j]+mod)%mod;
}
for(int j=0;j<=m;j++){
if(j) T.num[j-1][j]=A[j];
if(j<m) T.num[j+1][j]=C[j];
T.num[j][j]=B[j];
}
}
Matrix Pow(Matrix a,int b)//矩阵快速幂
{
Matrix ans=One,Base=a;
while(b){
if(b&1){
ans=ans*Base;
}
Base=Base*Base;
b>>=1;
}
return ans;
}
inline int Fast_Pow(int a,int b)
{
int ans=1,base=a;
while(b){
if(b&1) ans=ans*base%mod;
base*=base,base%=mod;
b>>=1;
}
return ans;
}
signed main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(!a[i]) m++;
}
for(int i=1;i<=m;i++) t+=(a[i]==0);
init();
base=base*Pow(T,k);
Matrix t=Pow(T,k);
int st=max(2*m-n,0ll);
int sum=0;
for(int i=st;i<=m;i++) sum+=base.num[0][i],sum%=mod;
printf("%lld\n",base.num[0][m]*Fast_Pow(sum,mod-2)%mod);
return 0;
}