CF1151F Sonya and Informatics

我们最终要的序列一定是前面全是0,后面全是1,假设总共\(m\)个0,那么这等价于前\(m\)位0的个数为\(m\).当然一开始可能数量没有\(m\)

那就把前\(m\)位0的数量作为状态,记\(f_{i,j}\)表示前\(i\)次操作,前\(m\)位有\(j\)个0的概率.转移的话只有两种情况会改变状态下表,第一种是前面的0和后面的1交换,这会导致\(j-1\),第二种是前面的1和后面的0交换,这会导致\(j+1\),剩下的情况都不会改变\(j\).所以就可以做到\(O(nk)\)转移,至于前面1数量,以及后面0/1数量都可以通过\(j\)推出来

状态和转移是个矩阵的形式,矩乘优化即可

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db double

using namespace std;

const int N=100+10,mod=1e9+7;

int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}

int ginv(int a){return fpow(a,mod-2);}

int n,m,kk,a[N];

struct matrix

{

	int a[N][N];

	matrix(){memset(a,0,sizeof(a));}

	matrix operator * (const matrix &bb) const

	{

		matrix an;

		for(int i=0;i<=m;++i)

			for(int j=0;j<=m;++j)

			{

				LL nw=0;

				for(int k=0;k<=m;++k) nw+=1ll*a[i][k]*bb.a[k][j]%mod;

				an.a[i][j]=nw%mod;

			}

		return an;

	}

	matrix operator ^ (const LL &bb) const

	{

		matrix an,a=*this;

		for(int i=0;i<=m;++i) an.a[i][i]=1;

		LL b=bb;

		while(b)

		{

			if(b&1) an=an*a;

			a=a*a,b>>=1;

		}

		return an;

	}

}aa,bb;

int main()

{

////////////////////

	n=rd(),kk=rd();

	for(int i=1;i<=n;++i)

		a[i]=rd(),m+=!a[i];

	int nn=n*(n-1)/2,p=ginv(nn);

	for(int i=max(m+m-n,0);i<=m;++i)

	{

		if(i>0) bb.a[i][i-1]=(bb.a[i][i-1]+1ll*i*(n-m-m+i)%mod*p%mod)%mod;

		if(i<m) bb.a[i][i+1]=(bb.a[i][i+1]+1ll*(m-i)*(m-i)%mod*p%mod)%mod;

		bb.a[i][i]=(bb.a[i][i]+1ll*(nn-i*(n-m-m+i)%mod-(m-i)*(m-i)%mod)*p%mod)%mod;

	}

	int mm=0;

	for(int i=1;i<=m;++i) mm+=!a[i];

	aa.a[0][mm]=1;

	printf("%d\n",(aa*(bb^kk)).a[0][m]);

    return 0;

}

巴特西

CF1151F Sonya and Informatics

最新文章

热门文章