3.1~3.10解题报告

[cf1525E]Assimilation IV

依据题面，可以知道每个点只会被计算一次，所以可以从点出发，求每个点被覆盖的概率，正着计算会有很多重复，所以考虑先算出不可能的情况，在与1作差，很明显，若所有城市到点A的距离都小于n，则一定成立，如果有一个不满足，则若此城市第一个放置，就要分两种情况，若其余距离均小于n-1，则成立，否则以此类推即可求得答案

代码：

#include<cstdio>
#define ll long long
using namespace std;
const int p=998244353;
int n,m;
int t[50005][25];
ll fac[25],ans;
ll qpow(ll x,int y)
{
	ll res=1;
	while(y)
	{
		if(y&1) res=res*x%p;
		x=x*x%p;
		y>>=1;
	}
	return res;
}
int main()
{
	scanf("%d%d",&n,&m);
	fac[0]=1;
	for(int i=1;i<=n;i++)
	{
		fac[i]=fac[i-1]*i%p;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int d;
			scanf("%d",&d);
			t[j][d]++;
		}
	}
	ll inv=qpow(fac[n],p-2);
	for(int i=1;i<=m;i++)
	{
		ll sum=0,tmp=1;
		for(int j=n;j>0;j--)
		{
			sum+=t[i][j+1];
			tmp=tmp*sum%p;
			sum--;
		}
		ans=(ans+1-tmp*inv%p+p)%p;
	}
	printf("%lld",ans);
	return 0;
}