自动搬运

查看原文

来自洛谷，原作者为

	Neil_Qian 题目按字典序排列

搬运于2025-08-24 22:56:58，当前版本为作者最后更新于2024-04-10 14:05:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10328 [UESTCPC 2024] 卡牌游戏 题解

赛场上想出来了但是不敢写，怕调不出来被队友打。

解决方案

首先容易想到 $k$ 对取牌的过程并没有影响，所以考虑矩阵快速幂，这样就解释了为什么 $k\le 10^9$。

然后考虑矩阵的内容。$n\le 4$ 有很大启发，每种牌都可能有或者没有，使用状压，虽然有 $2^{16}$ 种方案，但容易想到实际合法的方案应该不多。打表发现只有 $209$ 种。可以支持 $O(n^3)$ 的矩阵乘法。

每个状态的得分是可以计算的。其次，要计算任意两个状态之间转移的概率。分几种情况：拿起一张没有的、拿起一张导致放回一张、拿起一张导致放回两张。注意第三种容易被忽视。

这些是算好了以后，就可以上矩阵了，如图：

其中 $f_i$ 表示状态编号为 $i$ 的状态发生的概率。注意因为 $ans$ 只能计算上一次的贡献，因此 $k$ 要变成 $k+1$。

代码

注意细节。

#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N=220,MOD=998244353;
struct mat{
	ll n,m,a[N][N];
	mat(){n=m=0,memset(a,0,sizeof(a));}
	mat operator *(const mat b){
		mat res;res.n=n,res.m=b.m;
		for(int i=1;i<=res.n;i++)for(int j=1;j<=res.m;j++)
			for(int k=1;k<=m;k++)(res.a[i][j]+=a[i][k]*b.a[k][j]%MOD)%=MOD;
		return res;
	}
}x,res;ll n,sn,k,a[10][10],b[10][10],cnt,num[N],mv[N][N],point[N],f1,f2,tot,sum;
inline ll getid(ll x,ll y){return (x-1)*n+y-1;}
inline ll qpow(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1)(res*=x)%=MOD;
		(x*=x)%=MOD,y>>=1;
	}
	return res;
}
inline bool check(int i,int x,int y){
	for(int j=1;j<=n;j++){
		if(x==-1&&((i>>getid(j,y))&1))return 0;
		else if(y==-1&&((i>>getid(x,j))&1))return 0;
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cin>>n>>k,k++,sn=n*n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j],(tot+=a[i][j])%=MOD;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>b[i][j];
	for(int i=0;i<(1<<sn);i++){
		f1=1;
		for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
			if(!a[j][k]&&((i>>getid(j,k))&1)){f1=0;break;}
		if(!f1)continue;
		f1=1;
		for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)for(int l=k+1;l<=n;l++)
			if((((i>>getid(j,k))&1)&&((i>>getid(j,l))&1))||
			(((i>>getid(k,j))&1)&&((i>>getid(l,j))&1))){f1=0;break;}
		if(f1){
			num[++cnt]=i;
			for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
				point[cnt]+=(((i>>getid(j,k))&1)*b[j][k]);
		}
	}
	for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++){
		f1=f2=-1;
		for(int k=1;k<=n;k++){
			for(int l=1;l<=n;l++)
				if(((num[i]>>getid(k,l))&1)+((num[j]>>getid(k,l))&1)==1){
					if(f2>=0){f1=-2;break;}
					else if(f1>=0)f2=getid(k,l);
					else f1=getid(k,l);
				}
			if(f1==-2)break;
		}
		if(f1<0)continue;
		for(int k=1;k<=n;k++)for(int l=1;l<=n;l++)tot-=((num[i]>>getid(k,l))&1);
		if(f2>=0){
			int x=f1/n+1,y=f1%n+1,k=f2/n+1,l=f2%n+1;
			if(((num[i]>>f1)&1)&&((num[i]>>f2)&1))
				mv[i][j]=(a[x][l]+a[k][y])%MOD*qpow(tot,MOD-2)%MOD;
		}
		else{
			if((num[i]>>f1)&1){
				sum=0;
				for(int k=1;k<=n;k++){
					if(check(num[i],k,-1)||k==f1/n+1)(sum+=a[k][f1%n+1])%=MOD;
					if(k!=f1%n+1&&check(num[i],-1,k))(sum+=a[f1/n+1][k])%=MOD;
				}
				mv[i][j]=(sum-1+MOD)%MOD*qpow(tot,MOD-2)%MOD;
			}
			else mv[i][j]=a[f1/n+1][f1%n+1]*qpow(tot,MOD-2)%MOD;
		}
		for(int k=1;k<=n;k++)for(int l=1;l<=n;l++)tot+=((num[i]>>getid(k,l))&1);
	}
	x.n=x.m=res.m=cnt+1,res.n=1,res.a[1][1]=1,x.a[cnt+1][cnt+1]=1;
	for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++)x.a[i][j]=mv[i][j];
	for(int i=1;i<=cnt;i++)x.a[i][cnt+1]=point[i];
	while(k){
		if(k&1)res=res*x;
		x=x*x,k>>=1;
	}
	return cout<<res.a[1][cnt+1]<<"\n",0;
}