CF2150B Grid Counting 题解

前置知识：乘法原理、组合数、乘法逆元。

题目大意

给出一个

n\times n

的网格，初始全为白色，我们需要将一些单元格涂黑使得：

对于每个

i \displaystyle \in [1,m]

，假设

(x_i,y_i)

是被涂成黑色的单元格，对于每一个

k

需要满足：

第 $k$ 行中存在 $a_k$ 个黑格。
存在一个索引 $i$ 使得 $\max(x_i,y_i)=k$ 。
存在一个索引 $i$ 使得 $\max(x_i,n+1-y_i)=k$ 。

我们需要计算有多少种方案使得满足题目的条件。

思路

观察样例：

每个

k

对应一个黑色单元格，因此黑色单元格的总数必须恰好为

n

。如果给定的

a

数组之和不为

n

，则方案数直接为

0

，我们只需要输出

0

即可。

我们注意到，第二个与第三个条件存在对称性。则对于更一般的情况，由对称性，我们先对于每个

k

算出可用的位置数

cnt_k=\max(0,n+2-2k)

。然后从

n

到

1

遍历每个

k

，累计已经用掉的位置（以下记为

used

），易知剩余可用位置数（为了对应代码，以下记为

can

）为

\max(0,cnt_k-used)

。此时如果

can<a_k

，则当前行无法放置要求的黑色单元格数，直接输出

0

即可；反之，由乘法原理，我们将方案数乘上

\tbinom{can}{a_k}

，接着更新

used

的值，继续遍历。最后输出总方案数即可。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,MOD=998244353;
int T,n;
int fac[N],inv[N],a[N],cnt[N];

int qpow(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1)(res*=x)%=MOD;
		(x*=x)%=MOD;
		y>>=1;
	}
	return res;
}

void init()
{
	fac[0]=1;
	for(int i=1;i<N;i++)
		fac[i]=fac[i-1]*i%MOD;
	
	inv[N-1]=qpow(fac[N-1],MOD-2);
	for(int i=N-2;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%MOD;
}

inline int C(int n,int m){return n<m?0:fac[n]*inv[n-m]%MOD*inv[m]%MOD;}

signed main()
{
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	init();
	cin>>T;
	while(T--)
	{
		memset(cnt,0,sizeof(cnt));
		cin>>n;
		int sum=0;
		for(int i=1;i<=n;i++)
			cin>>a[i],sum+=a[i];

		if(sum!=n)
		{
			cout<<0<<'\n';
			continue;
		}

		for(int k=1;k<=n;k++)
		{
			int val=n+2-2*k;
			if(val<0)val=0;
			cnt[k]=val;
		}

		int ans=1,used=0;
		bool flag=1;
		for(int k=n;k>=1;k--)
		{
			int can=cnt[k]-used;
			if(can<0)can=0;
			if(can<a[k])
			{
				flag=0;
				break;
			}
			ans=ans*C(can,a[k])%MOD;
			used+=a[k];
		}

		if(!flag)cout<<"0\n";
		else cout<<ans%MOD<<'\n';
	}
	return 0;
}

CF2150B Grid Counting 题解

文章操作

相关推荐

评论

CF2150B Grid Counting 题解