【CF1151F】Sonya and Informatics（动态规划，矩阵快速幂）

时间：2023-03-09 19:42:22
【CF1151F】Sonya and Informatics（动态规划，矩阵快速幂）

【CF1151F】Sonya and Informatics（动态规划，矩阵快速幂）

题面

CF

题解

考虑一个暴力\(dp\)。假设有\(m\)个\(0\)，\(n-m\)个\(1\)。设\(f[i][j]\)表示当前做到了第\(i\)个操作，前\(m\)个元素中有\(j\)个\(1\)的方案数。

转移就枚举交换哪两个东西就可以了。

把转移用矩阵优化就可以做到\(O(n^3logK)\)。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 105

#define MOD 1000000007

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,N,K,z,C[MAX][MAX],a[MAX];

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

struct Matrix

{

	int s[MAX][MAX];

	void clear(){memset(s,0,sizeof(s));}

	void init(){clear();for(int i=0;i<=N;++i)s[i][i]=1;}

	int*operator[](int x){return s[x];}

}A,B;

Matrix operator*(Matrix a,Matrix b)

{

	Matrix c;c.clear();

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

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

			for(int k=0;k<=N;++k)

				c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%MOD;

	return c;

}

Matrix fpow(Matrix a,int b){Matrix s;s.init();while(b){if(b&1)s=s*a;a=a*a;b>>=1;}return s;}

int main()

{

	n=read();K=read();

	for(int i=1;i<=n;++i)a[i]=read(),z+=a[i]^1;

	for(int i=0;i<=n;++i)C[i][0]=1;

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

		for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;

	int s=0;

	for(int i=1;i<=n;++i)if(i<=z&&a[i])++s;

	/*

	f[0][s]=1;

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

		for(int j=0;j<=n-z&&j<=z;++j)

			if(f[i-1][j])

			{

				add(f[i][j],1ll*f[i-1][j]*(C[z][2]+C[n-z][2])%MOD);

				add(f[i][j],1ll*f[i-1][j]*j%MOD*(n-z-j)%MOD);

				add(f[i][j],1ll*f[i-1][j]*(z-j)%MOD*j%MOD);

				add(f[i][j-1],1ll*f[i-1][j]*j%MOD*j%MOD);

				add(f[i][j+1],1ll*f[i-1][j]*(z-j)%MOD*(n-z-j)%MOD);

			}

	*/

	N=min(n-z,z);

	B[0][s]=1;

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

	{

		add(A[i][i],(C[z][2]+C[n-z][2])%MOD);

		add(A[i][i],1ll*i*(n-z-i)%MOD);

		add(A[i][i],1ll*(z-i)*i%MOD);

		if(i)add(A[i][i-1],1ll*i*i%MOD);

		if(i<N)add(A[i][i+1],1ll*(z-i)*(n-z-i)%MOD);

	}

	B=B*fpow(A,K);

	int ans=1ll*B[0][0]*fpow(fpow(n*(n-1)/2,K),MOD-2)%MOD;

	printf("%d\n",ans);

	return 0;

}

相关文章