# [题解] 2023 杭电多校 Expectation of Rank [计数 dp]

# 题目大意

矩阵 $A\in \Bbb{F}_p^{n\times n}$ ，其中的每个元素取值为 $\Bbb{F}_p$ 的均匀随机变量。
$\Bbb{F}_p$ 为 $p$ 阶有限域，其中 $p$ 为质数。
求矩阵 $A$ 的秩的期望 $\Bbb{E}(rank\ A)$ 。

# 题解

题目有点唬人的，但实际上只用到了一个关键点：
$p$ 阶有限域下，秩为 $k$ 的向量组可以确定一个 $k$ 维超立方体，每个维度的取值有 $p$ 个，则总向量个数为 $p^k$ 。
在欧几里得空间中很好理解，比如秩为 $2$ 的向量组确定了一个平面，秩为 k 的向量组确定了一个 $k$ 维空间；放在离散意义下，这里 p 为素数，所以每个维度的取值可以在整数 $[0,p)$ 中任意一个。
这个期望问题当然要转化成计数问题，只需要求出秩为 $k$ 的矩阵有多少个即可。
考虑不断往向量组中添加新向量， $dp$ 做这个过程。
设 $f_{i,j}$ 表示当前向量组中有 $i$ 个向量，向量组的秩为 $j$ 。
每个向量长度为 $N$ ，并且元素取值在 $\Bbb{F}_p$ ，那么新加的向量一共有 $p^N$ 种可能。
现在向量组的秩为 $j$ ，也就是说这些向量可以确定 $p^j$ 个向量。所以有 $p^j$ 种情况，添加新向量后向量组的秩不发生变化，其余 $p^n-p^j$ 种情况会使向量组的秩增加 $1$ 。
$dp$ 递推式子长这样：

$f_{i+1,j}+=f{i,j}*p^j$

$f_{i+1,j+1}+=f{i,j}*(p^n-p^j)$

预处理 $p$ 的幂，时间复杂度 $\mathcal{O}(n^2)$

# 代码

	#include<cstdio>
	#include<cstring>

	typedef long long ll;

	const int MAXN=5010;
	const int P=1e9+7;

	int T,N,M;
	int f[MAXN][MAXN];
	int qp[MAXN];

	int qpow(int a,int b){
	a%=P;
	if(!a) return 0;
	int res=1;
	for(;b;a=(ll)a*a%P,b>>=1)
	if(b&1) res=(ll)res*a%P;
	return res;
	}

	void Add(int &a,const int &b){
	a=(a+b)%P;
	}

	int main(){
	// freopen("1.in","r",stdin);
	scanf("%d",&T);
	while(T--){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;++i)
	for(int j=0;j<=i;++j)
	f[i][j]=0;
	for(int i=0;i<=N;++i)
	qp[i]=qpow(M,i);
	f[0][0]=1;
	for(int i=0;i<=N;++i){
	for(int j=0;j<=i;++j){
	Add(f[i+1][j],(ll)f[i][j]*qp[j]%P);
	Add(f[i+1][j+1],(ll)f[i][j]*(qp[N]-qp[j]+P)%P);
	}
	}
	int ans=0;
	for(int i=1;i<=N;++i)
	// printf("%d ",f[N][i]),
	Add(ans,(ll)f[N][i]*i%P);
	ans=(ll)ansqpow(qpow(M,NN),P-2)%P;
	printf("%d\n",ans);
	}
	}

计数 dp

# [题解] 2023 杭电多校 Expectation of Rank [计数 dp]

# 题目大意

# 题解

# 代码

[题解] CF890 E PermuTree [树][背包dp][二进制拆分]

[题解] 2023杭电多校 Rikka with Square Numbers [数论]