CF1322C

yijan · 2020-03-13 18:55:30 · 题解

CF1322C

为了更好的阅读体验，建议到 这里 或者 Luogu 博客 阅读，因为我也不知道放在题解的时候公式挂没挂

首先我们知道 \gcd(a,a+b) = \gcd(a,b,a+b) = \gcd(a,b) ，这是显而易见的。

于是我们考虑对于两个右部点 u,v ，假设与它们相邻的左部点集合是 R(u),R(v) 这时它们的贡献。

• R(u) \subseteq R(v)$ 这种时候，当计算 $N(S),S\subseteq R(u)$ 的时候可以计算到 $w_u + w_v$ ，计算 $N(S),S\subseteq R(v),S \nsubseteq R(u)$ 时会计算 $w_v$ 但不会计算 $w_u$ ，所以最后做出贡献的时候可以直接拆开成 $w_u,w_v
• 当 R(u),R(v) 不存在包含关系，但是 R(u)\cap R(v) \neq \varnothing ，这种情况，如果取到交集的子集，贡献是 w_u+w_v ，否则取到某一边的贡献分别是 w_u,w_v 就成为了开头那个 \gcd(a,b,a+b) 的状况，仍然可以直接把 u,v 的贡献看作 w_u,w_v
• R(u) \cap R(v) = \varnothing$ 显然互不相干，分别是 $w_u,w_v

所以对于所有右边的点，我们可以直接按照 R(u) 分组，分组的过程用 hash 就行了。如果 R(u),R(v) 不相同，总是可以把这两个数拆成 w_u,w_v 直接进行贡献。

但是还要注意，如果右边某个点与左边根本不相连需要直接 skip 它。。因为这个场上吃了一发罚时。。

由于是 CF 建议 mt19937 + 双 hash。

可能有不严谨的地方。。但是可以意会一下吧

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
#include "chrono"
#include "random"
#include "map"
using namespace std;
#define ll long long
#define MAXN 500006
mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int n , m;
vector<int> G[MAXN];
const int P = 1000000007 , Q = 501217111;
int bp , bq;
int pp[MAXN] , pq[MAXN];
long long c[MAXN];
long long s[MAXN];
map<pair<int,int>,int> M;
int cn = 0;
long long gcd( long long a , long long b ) {
    return !b ? a : gcd( b , a % b );
}
void solve( ) {
    scanf("%d%d",&n,&m);
    M.clear();
    for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&c[i]) , s[i] = 0 , G[i].clear();
    cn = 0;
    for( int i = 1 , u , v ; i <= m ; ++ i ) {
        scanf("%d%d",&u,&v);
        G[v].push_back( u );
    }
    for( int i = 1 ; i <= n ; ++ i ) {
        int retp = 0 , retq = 0;
        if( !G[i].size() ) continue;
        for( int v : G[i] ) {
            ( retp += pp[v] ) %= P;
            ( retq += pq[v] ) %= Q;
        }
        pair<int,int> fk = make_pair( retp , retq );
        if( !M[fk] ) M[fk] = ++ cn;
        s[M[fk]] += c[i];
    }
    long long res = s[1];
    for( int i = 2 ; i <= cn ; ++ i ) res = gcd( res , s[i] );
    printf("%lld\n",res);
}

int main() {
    bp = Rnd() % 10007 + 1 , bq = Rnd() % 100007 + 1;
    pp[0] = pq[0] = 1;
    for( int i = 1 ; i < MAXN ; ++ i ) pp[i] = 1ll * pp[i - 1] * bp % P , pq[i] = 1ll * pq[i - 1] * bq % Q;
    int T;cin >> T;
    while( T-- ) {
        solve();
    }
}