P9583 涂色 题解

· · 题解

P9583 涂色 题解

解法

题中说求最终有多少个方格涂着颜色，那我们可以求有多少个方格没有颜色，用方格的总数减去没有颜色的方格数即为所求。

考虑本题涂色规律，涂上 k 层颜料的方格其颜料会被擦去，这种操作的本质是对 k 取模，所以没有颜色的方格即该方格所在的行、列被涂色的次数和可以被 k 整除。

现在分别统计每个行、每个列的涂色次数，然后对行、列分别开两个桶，维护每行、每列的涂色次数对 k 取模后的值。

然后枚举桶里的元素。设有 rubh_i 个行的涂色次数对 k 取模等于 i，rubl_i 个列的涂色次数对 k 取模等于 i，则想要让一个方格没有颜色，则必须满足 hang_i + lie_i \equiv 0 \pmod{k}，所以对于 rubh_i 个行，只有 rubl_{k-i} 个列与之匹配才能是没有颜色的方格，根据乘法原理，有 rubh_i \times rubl_{k-i} 个方格没有颜色。特殊地，rubh_0 与 rubl_0 匹配。

求解公式即为 rubh_0 \times rubl_0 + \sum \limits _{i=1} ^{i < k} rubh_i \times rubl_{k-i}，时间复杂度 \mathcal{O}(q + k)。

代码

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
    /*
    快读快写
    */
};
using namespace fast_IO;
int n,m,q,k,hang[200010],lie[200010],rubh[500010],rubl[500010];
inline void delh(int x)
{
    if(x==k-1) rubh[x]--,rubh[0]++;
    else rubh[x]--,rubh[x+1]++;
}
inline void dell(int x)
{
    if(x==k-1) rubl[x]--,rubl[0]++;
    else rubl[x]--,rubl[x+1]++;
}
long long ans;
int main()
{
    read(n),read(m),read(q),read(k),rubh[0]=n,rubl[0]=m;
    for(int i=1,op,x;i<=q;i++)
    {
        read(op),read(x);
        if(op==1) hang[x]++,delh((hang[x]-1)%k);
        else lie[x]++,dell((lie[x]-1)%k);
    }
    ans+=1ll*rubh[0]*rubl[0];
    for(int i=1;i<k;i++) ans+=1ll*rubh[i]*rubl[k-i];
    cout<<1ll*n*m-ans;
    return 0;
}