CF2044F Easy Demon Problem

题目大意

给定两个长度为 $n,m$ 的数列 $a_i$ ，$b_j$ ，并且依据该数列构造一个矩阵 $M_{n,m}$，使得 $M_{i,j}=a_i \times b_j$ 。

再给出 $q$ 个查询，对于每个 $x_i$，查找是否存在一对 $i,j$ 使得该矩阵删去第 $i$ 行和第 $j$ 列，使得矩阵剩下所有数之和为 。

每一组询问是独立的。

思路

我们发现，矩阵之和可以写为 $\sum_{i=0}^{n}{\sum_{j=0}^{m}{a_i \times b_j} }$ 可以变形为

$\sum_{i=0}^{n}{a_i} \times \sum_{j=0}^{m}{b_i}$

上式等价于 $sum(a) \times sum(b)$

我们神奇的发现，当删去这个矩阵的第 $i$ 行第 $j$ 列的时候，矩阵里面的所有元素之和就是： $[sum(a)-a_i]\times[sum(b)-b_j]$

我们的目的就转换为求是否有一对 $a_i$ 和 $b_j$ 使得 $[sum(a)-a_i]\times[sum(b)-b_j]=x$ 。

重点： 我们分别记录每一个数组 $a,b$ ，并分别求出他们的和。对于每一个询问 $x$ ，分解 $x$ 的因数，查找每一对因数 $l,r$ ，假设 $l=sum(a)-a_i,r=sum(j)-b_{}$ ，则问题又被转换为求是否存在 。这里考虑数据范围，开个大数组记录即可。

注意数存在负数需要处理，时间复杂度为 $O(q)$ (有个 $\sqrt {2⋅10^5}$ 的常数)可过。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool ina[500010],inb[500010];
int la[300010],lb[300010];
ll sum1=0,sum2=0;
bool checkin(bool f,ll num){
    if(num>250000||num<-250000)return false;
    if(!f)return ina[num+250000];
    return inb[num+250000];
}
bool checkit(ll a,ll b,int f){
    int fl1=1,fl2=1;
    if(f)fl1=-1;
    if(checkin(0,sum1-a*fl1)&&checkin(1,sum2-b*fl2))return true;
    if(checkin(1,sum2-a*fl1)&&checkin(0,sum1-b*fl2))return true;

    fl1=-fl1,fl2=-fl2;

    if(checkin(0,sum1-a*fl1)&&checkin(1,sum2-b*fl2))return true;
    if(checkin(1,sum2-a*fl1)&&checkin(0,sum1-b*fl2))return true;
    return false;

}
int main()
{
    //freopen("read.in","r",stdin);
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)scanf("%d",&la[i]),sum1+=la[i],ina[la[i]+250000]=true;
    for(int i=1;i<=m;++i)scanf("%d",&lb[i]),sum2+=lb[i],inb[lb[i]+250000]=true;
    for(int i=1;i<=q;++i){
        int x;
        scanf("%d",&x);
        int f=0;
        if(x<0)f=1,x=-x;

        for(int j=1;j<=sqrt(x);++j){
            if(x%j==0){
                if(checkit(j,x/j,f)){
                    printf("Yes\n");
                    f=2;
                    break;
                }
            }
        }
        if(f==2)continue;
        printf("No\n");
    }
}