题解：CF1151F Sonya and Informatics

Solution

看到 n\le100,k\le10^9，容易想到矩阵快速幂。关键在于如何设计状态和矩阵转移。\ 设串中有 m 个 1，一个单调不减的 0/1 串显然形如前 n-m 个为 0，后 m 个为 1。发现每次操作都随机选择数对交换，因此一个局面能交换为上述局面的概率不与每个 1 的位置有关，仅与其在最后 m 位的 1 个数有关。\ 于是可以设 f_i 表示当前最后 m 位（以下称为右侧，其他为左侧）有 i 个 1 的概率，考虑转移：

方案数除去 n(n-1)/2，就是此种转移的概率。\ 于是可以设计出矩阵，跑一遍矩阵快速幂即可。

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define R read()
using namespace std;
inline int read(){
    int x=0;char c=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x;
}
const int inf=0x3f3f3f3f,N=105;
const ll INF=0x3f3f3f3f3f3f3f3f,M=1000000007;
int n,m,k,a[N],cnt;
struct matrix{
    ll s[N][N];
    friend matrix operator* (matrix x,matrix y){
        matrix z;
        for(int i=0;i<=m;i++){
            for(int j=0;j<=m;j++){
                z.s[i][j]=0;
                for(int k=0;k<=m;k++)
                    z.s[i][j]+=x.s[i][k]*y.s[k][j],z.s[i][j]%=M;
            }
        }
        return z;
    }
}A,B,E;
ll power(ll x,int y){
    ll res=1;
    while(y){
        if(y&1) res*=x,res%=M;
        x*=x,x%=M,y>>=1;
    }
    return res;
}
matrix power(matrix x,int y){
    matrix res=E;
    while(y){
        if(y&1) res=res*x;
        x=x*x,y>>=1;
    }
    return res;
}
ll qwq;
int main(){
    n=R,k=R;
    for(int i=1;i<=n;i++) a[i]=R,m+=a[i];
    for(int i=n-m+1;i<=n;i++) cnt+=a[i];
    for(int i=0;i<=m;i++) E.s[i][i]=1;
    qwq=power(n*(n-1)>>1,M-2);
    for(int i=0;i<=m;i++){
        ll sum=3*M+1;
        if(i){
            B.s[i][i-1]=i*(n-m-m+i)%M*qwq%M;
            sum-=B.s[i][i-1];
        }
        if(i<m){
            B.s[i][i+1]=(m-i)*(m-i)%M*qwq%M;
            sum-=B.s[i][i+1];
        }
        B.s[i][i]=sum%M;
    }
    A.s[0][cnt]=1;
    A=A*power(B,k);
    printf("%lld\n",A.s[0][m]);
    return 0;
}