CF2150B Grid Counting 题解

· · 题解

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

题目大意

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

对于每个 i \displaystyle \in [1,m]，假设 (x_i,y_i) 是被涂成黑色的单元格，对于每一个 k 需要满足：

  1. 第 k 行中存在 a_k 个黑格。
  2. 存在一个索引 i 使得 \max(x_i,y_i)=k。
  3. 存在一个索引 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

#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;
}