【题解】集合选择

题意

给你个数组，每个数组有个元素。让在这个数组中选择两个元素，这两个元素要在不同得数组当中，求有多少种组合能够使得。

题解

这题可以这样考虑，考虑把所有得数存在一个大数组中，然后问题就转为从这个大数组中挑出两个数相乘等于得方案数了，这是总的方案数，我们要的答案就是总的方案数减去两个元素在同一个数组中的情况。我们对所有的数组求一遍从中挑两个数相乘为的方案数，并将该数组中的元素存入最后的大数组中。对大数组这样操作一次，将答案减去之前求的每个小数组的部分。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
map<int,long long>mp;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    long long ans=0;
    for(int i=0; i<n; i++)
    {
        int m;
        scanf("%d",&m);
        map<int,long long>vis;
        for(int j=0; j<m; j++)
        {
            int x;
            scanf("%d",&x);
            mp[x]++;
            vis[x]++;
        }
        for(int j=1; j*j<=k; j++)
        {
            if(k%j==0)
            {
                int x=j;
                int y=k/j;
                if(x!=y)
                {
                    ans-=vis[x]*vis[y];
                }
                else
                {
                    ans-=vis[x]*(vis[x]-1)/2;
                }
            }
        }
    }
    for(int j=1; j*j<=k; j++)
    {
        if(k%j==0)
        {
            int x=j;
            int y=k/j;
            if(x!=y)
            {
                ans+=mp[x]*mp[y];
            }
            else
            {
                ans+=mp[x]*(mp[x]-1)/2;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}