CF215C 题解

· · 题解

翻译

有一个 n\times m 的矩阵

我们用一个六元组 (a,b,c,d,x0,y0) 表示一个十字形：

若一个方格 (x,y) 满足下面两个条件之一，则这个方格属于这个六元组表示的十字形

已知一个十字形的面积是 s，问有多少个六元组满足要求

题解

翻译题目中的两个条件：

x$ 到 $x0$ 的距离不超过 $a$ 且 $y$ 到 $y0$ 的距离不超过 $b

或

x$ 到 $x0$ 的距离不超过 $c$ 且 $y$ 到 $y0$ 的距离不超过 $d

而这两个条件其实是分别表示了一个矩形再将这两个矩形取并集而形成的十字型。

这是一个由 (2,1,0,2,5,5) 表示的十字形，其中 2,1 两个数生成了红色的矩形，0,2 生成了蓝色矩形，紫色是重叠部分，黑色是十字的“中心点”。

定义条件中的 |x-x0| 和 |y-y0| 叫做 xy 坐标的“偏移值”，设某一个“偏移值”为 k，则显然发现 x(y) 坐标的取值范围是 x0-k\le x(y)\le x0+k 这个范围显然有 2k+1 个整数，所以，任何单个的条件表示的矩形长宽一定都是奇数。

对了，一个矩形也可以是一个十字形，比如六元组 (1,1,0,0,4,4) 就表示一个以 (4,4) 为中心点，大小为 3\times 3 的矩形，而且十字形不能有任何一个格子在矩阵外边

注意到 n,m 最多只有 500 ，所以我们可以暴力枚举矩形的长宽 i,j，看一下这个矩阵的面积是否恰好等于 s，分类讨论：

那就直接看一下整个大矩阵里有多少个 i\times j 的小矩阵并累加进答案。这可以用一个函数计算：

ll F(ll x,ll y)
{
    return (n-x+1)*(m-y+1);
}

看一下需要在这个矩形左右两侧或上下两侧“补”多少格子

能否补，必须看剩下的面积是否是偶数，因为十字形是轴对称的，如果你左右或上下两侧不对称的话就不是十字形了。

再枚举一个 k，要求 k 必须能整除剩下的面积，并且补的部分不能超出矩形的边界。

综上，由于只要六元组中表示中心点的参数(x0,y0)不相同，算作多种方案，所以第二种情况也需要乘以 F(i,j)

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll F(ll x,ll y)
{
    return (n-x+1)*(m-y+1);
}
int main()
{
    ll s,i,j,k,res=0;
    scanf("%lld %lld %lld",&n,&m,&s);
    for(i=1;i<=n;i+=2)
    {
        for(j=1;j<=m;j+=2)
        {
            ll s0=i*j;
            if(s0==s) res+=(((i-1)/2+1)*((j-1)/2+1)*2-1)*F(i,j);
            else if(s0<s)
            {
                s0=s-s0;
                for(k=1;k<j;k+=2)
                    if(!(s0&1) && s0%k==0 && i+s0/k<=n) res+=2*F(i+s0/k,j);
            }
        }
    }
    printf("%lld",res);
    return 0;
}