自动搬运

查看原文

来自洛谷，原作者为

	wsyhb **

搬运于2025-08-24 22:28:01，当前版本为作者最后更新于2021-01-02 22:46:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

分析 + 题解

容易发现，被操作的区域恰好可以分成 $(m-1)^2$ 个子矩阵，其中每个子矩阵总是同时异或 $1$。

具体地，对于所有满足 $1 \le i < m$，$1 \le j < m$ 的 $(i,j)$，以 $(x_i+1,y_j+1)$，$(x_{i+1},y_{j+1})$ 为顶点的子矩阵满足上述条件。

枚举 $(i,j)$，该子矩阵元素个数为 $(x_{i+1}-x_i)(y_{j+1}-y_j)$，在一次操作中被异或 $1$ 的概率为 $p=\dfrac{ij(m-i)(m-j)}{(C_m^2)^2}$。

说明：一共有 $(C_m^2)^2$ 种选择，其中 $i_1 \le i$，$j_1 \le j$，$i_2 > i$，$j_2 > j$ 的情况有 $ij(m-i)(m-j)$ 种。

设 $k$ 次操作后该子矩阵为全 $1$（异或了奇数次 $1$）的概率为 $f(p)$，则答案为 $\sum_{(i,j)} cnt \times f(p)$，而 $f(p)$ 可以通过一个简单的 DP（严格来说算递推）求得：

设 $dp[i][j]$ 表示第 $i$ 次操作后该子矩阵为全 $j$ 的概率，则有：

$$dp[i][j]=dp[i-1][1-j] \times p +dp[i-1][j] \times (1-p) $$

其中 $f(p)=dp[k][1]$。但这样单次计算是 $O(k)$ 的，不足以通过此题（可以得到 60 分）。

构造如下矩阵，使用矩阵快速幂即可在 $O(log_2k)$ 时间复杂度内进行单次计算。

$$\begin{bmatrix} 1-p&p\\ p&1-p \end{bmatrix}$$

总时间复杂度为 $O(m^2 log_2k)$。

代码

如果还有不清楚的，就看代码吧。

#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
inline void add(int &a,int b)
{
	a=a+b-(a+b>=P?P:0);
}
inline void mul(int &a,int b)
{
	a=1ll*a*b%P;
}
inline int get_sum(int a,int b)
{
	return a+b-(a+b>=P?P:0);
}
inline int get_product(int a,int b)
{
	return 1ll*a*b%P;
}
inline int get_square(int x)
{
	return get_product(x,x);
}
inline int get_power(int a,int n)
{
	int res=1;
	while(n>0)
	{
		res=(n&1)?get_product(res,a):res;
		mul(a,a);
		n>>=1;
	}
	return res;
}
inline int get_inv(int x)
{
	return get_power(x,P-2);
}
//以上是模运算中的加、乘、平方、快速幂、求逆 
const int max_m=1e3+5;
int x[max_m],y[max_m];
struct matrix
{
	int v[2][2];
	inline matrix(int p=0)//matrix 的构造函数，用概率 p 构造上述矩阵 
	{
		v[0][0]=v[1][1]=P+1-p;
		v[0][1]=v[1][0]=p;
	}
};
inline matrix operator * (const matrix &a,const matrix &b)//定义矩阵乘法 
{
	static matrix res;//static 变量会沿用上一次的结果，若需初始化必须在定义后赋值 
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
		{
			res.v[i][j]=0;
			for(int k=0;k<2;++k)
				add(res.v[i][j],get_product(a.v[i][k],b.v[k][j]));
		}
	return res;
}
inline matrix get_power(matrix a,int n)//矩阵快速幂 
{
	static matrix res;
	res.v[0][0]=1;
	res.v[0][1]=res.v[1][0]=res.v[1][1]=0;
	while(n)
	{
		if(n&1)
			res=res*a;
		a=a*a;
		n>>=1;
	}
	return res;
}
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k); 
	for(int i=1;i<=m;++i)
		scanf("%d",x+i);
	for(int i=1;i<=m;++i)
		scanf("%d",y+i);
	int inv_all=get_square(get_inv((1ll*m*(m-1)>>1)%P));//概率的分母 
	int ans=0;
	for(int i=1;i<m;++i)
		for(int j=1;j<m;++j)
		{
			int cnt=get_product(x[i+1]-x[i],y[j+1]-y[j]);//元素个数 
			int p=get_product(get_product(get_product(i,j),get_product(m-i,m-j)),inv_all);//概率 
			add(ans,get_product(cnt,get_power(matrix(p),k).v[0][1]));
		}
	printf("%d\n",ans);
	return 0;
}