题解：AT_arc157_d [ARC157D] YY Garden

· · 题解

思路

感觉有点偏思维，不过推出几个重要性质后还是蛮简单的。

首先记 Y 的总数 tot，若为奇数一定无解。

已知两个 Y 分一组，那么一共有 \frac{tot}{2} 组。我们将该矩阵分成若干个矩形，比较显然的是，知道了行被分成了几组，就能知道列被分成了几组。

我们可以枚举它，不过我枚举的是行被分成若干组后，每一组含 Y 的个数 hk，而我们知道两个 Y 一组，所以就能知道列被分成了 \frac{hk}{2} 部分，根据矩形面积公式，我们就能得到行应当被分成 \frac{tot\times 2}{hk} 部分；这里具体枚举那个都是无关紧要的，因为已知其中一个的值就能推导出剩下的值。

注意上面描述的时候用了应当，这是因为以上情况只是我们假设出来的理想情况，若与之不符则应当舍弃；此外，还有一个判断无解的标准，就是我们在按以上情况分出各部分后，需要判断每部分是否正好含两个 Y，具体实现我们可以借助二维前缀和维护。

之后方案若仍合法，则开始计数，此时我们划分部分就较为宽松了，在上面判断的时候，我们划分的标准是该行 / 列有 Y 出现且能将行 / 列分成每部分含对应数量的一组，而计数时只要不影响划分的状态都可以计入，最终利用乘法原理计算出该方案的所有方案数计入答案即可。

由于基础方案数比较少，所以原本 \mathcal{O(S)} 的时间复杂度跑起来还是很快的。

实现

#include<bits/stdc++.h>

const int Ratio=0;
const int N=2005;
const int mod=998244353;
int n,m,tot;
int sum[N][N],hsum[N],lsum[N],hang[N],lie[N];
int hzc[N],lzc[N],cnth[N],cntl[N];
int ans;
namespace Wisadel
{
    void Wsol(int hk)
    {
        int lk=tot*2/hk,ch=0,cl=0,res=1;
        for(int i=1;i<=n;i++) if(hang[i]&&hsum[i]%hk==0) hzc[++ch]=i;
        for(int i=1;i<=m;i++) if(lie[i]&&lsum[i]%lk==0) lzc[++cl]=i;
        if(2*ch!=lk||2*cl!=hk) return;
        for(int i=1;i<=ch;i++) for(int j=1;j<=cl;j++)
        {
            int ck=sum[hzc[i]][lzc[j]]-sum[hzc[i-1]][lzc[j]]-sum[hzc[i]][lzc[j-1]]+sum[hzc[i-1]][lzc[j-1]];
            if(ck!=2) return;
        }
        std::fill(cnth+1,cnth+1+ch,0),std::fill(cntl,cntl+1+cl,0);
        for(int i=1;i<=n;i++) if(hsum[i]%hk==0) cnth[hsum[i]/hk]++;
        for(int i=1;i<=m;i++) if(lsum[i]%lk==0) cntl[lsum[i]/lk]++;
        for(int i=1;i<ch;i++) res=1ll*res*cnth[i]%mod;
        for(int i=1;i<cl;i++) res=1ll*res*cntl[i]%mod;
        ans=(ans+res)%mod;
    }
    short main()
    {
        scanf("%d%d",&n,&m);getchar();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                char ch=getchar();
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
                if(ch=='Y') hang[i]++,lie[j]++,hsum[i]++,lsum[j]++,sum[i][j]++;
            }
            getchar();
            hsum[i]+=hsum[i-1];
        }
        for(int i=1;i<=m;i++) lsum[i]+=lsum[i-1];
        tot=hsum[n];
        if(tot&1){printf("0\n");return Ratio;}
        for(int i=2;i<=n*m;i+=2)
        {
            if(tot%i==0) Wsol(i);
            if(i>tot) break;
        }
        printf("%d\n",ans%mod);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

完结撒花~

\mathcal{Welcome\;to\;my\;blogs}