CF1322 C. Instant Noodles

发表于 | 阅读数

给定共$2n$个点，$m$条边的二分图。右部的每个点都有一个权值，现规定$𝑆$为左部点的任意子集，$𝑁(𝑆)$为与$𝑆$中的点直接相连的右部点集。$𝑓(𝑆)$为𝑆中所有点权值之和。要求所有$𝑓(𝑁(𝑆))$的$gcd$。

假设$1$连了$a_1,a_2$。$2$连了$a_1,a_3$

$gcd=gcd(a_1+a_2+a_3,a_1+a_3,a_1+a_2)=gcd(a_1,a_2,a_3)$

假设$1$连了$a_1,a_2,a_3$。$2$连了$a_1,a_3,a_4$

$gcd=gcd(a_1+a_2+a_3+a_4,a_1+a_3+a_2,a_1+a_3+a_4)=gcd(a_1+a_3,a_2,a_4)$

如果有右边的点$i$和$j$所链接的点集相同。那么$i,j$不可能在算$gcd$拆开来，变成一个整体$a_i+a_j$。
只要把右边连左边点集相同的点看成一个。这样$gcd$就是所有独立的点之后的$gcd$

判断是否点集相同可以用神奇的

1
map<vetor<int>,int>


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
vector<int> g[N];
int n, m;
ll a[N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            g[i].clear();
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            g[v].push_back(u);
        }
        map<vector<int>, ll> mp;
        for (int i = 1; i <= n; i++)
            sort(g[i].begin(), g[i].end());
        for (int i = 1; i <= n; i++)
            if (g[i].size())
                mp[g[i]] += a[i];
        ll ans = 0;
        for (auto x : mp)
        {

            ans = gcd(x.second, ans);
        }
        printf("%lld\n", ans);
    }
}

</details>

代码