Submission #696692

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
696692	2023-02-07T04:17:14 Z	tranxuanbach	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	17 ms	412 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

using uint = unsigned int;
template<uint _mod>
struct modular_fixed_base{
    static constexpr uint mod(){
        return _mod;
    }
    template<class T>
    static vector<modular_fixed_base> precalc_power(T base, int SZ){
        vector<modular_fixed_base> res(SZ + 1, 1);
        for(auto i = 1; i <= SZ; ++ i) res[i] = res[i - 1] * base;
        return res;
    }
    static vector<modular_fixed_base> _INV;
    static void precalc_inverse(int SZ){
        if(_INV.empty()) _INV.assign(2, 1);
        for(auto x = _INV.size(); x <= SZ; ++ x) _INV.push_back(_mod / x * -_INV[_mod % x]);
    }
    // _mod must be a prime
    static modular_fixed_base _primitive_root;
    static modular_fixed_base primitive_root(){
        if(_primitive_root) return _primitive_root;
        if(_mod == 2) return _primitive_root = 1;
        if(_mod == 998244353) return _primitive_root = 3;
        uint divs[20] = {};
        divs[0] = 2;
        int cnt = 1;
        uint x = (_mod - 1) / 2;
        while(x % 2 == 0) x /= 2;
        for(auto i = 3; 1LL * i * i <= x; i += 2){
            if(x % i == 0){
                divs[cnt ++] = i;
                while(x % i == 0) x /= i;
            }
        }
        if(x > 1) divs[cnt ++] = x;
        for(auto g = 2; ; ++ g){
            bool ok = true;
            for(auto i = 0; i < cnt; ++ i){
                if((modular_fixed_base(g) ^ (_mod - 1) / divs[i]) == 1){
                    ok = false;
                    break;
                }
            }
            if(ok) return _primitive_root = g;
        }
    }
    constexpr modular_fixed_base(): data(){ }
    modular_fixed_base(const double &x){ data = normalize(llround(x)); }
    modular_fixed_base(const long double &x){ data = normalize(llround(x)); }
    template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base(const T &x){ data = normalize(x); }
    template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> static uint normalize(const T &x){
        int sign = x >= 0 ? 1 : -1;
        uint v =  _mod <= sign * x ? sign * x % _mod : sign * x;
        if(sign == -1 && v) v = _mod - v;
        return v;
    }
    const uint &operator()() const{ return data; }
    template<class T> operator T() const{ return data; }
    modular_fixed_base &operator+=(const modular_fixed_base &otr){ if((data += otr.data) >= _mod) data -= _mod; return *this; }
    modular_fixed_base &operator-=(const modular_fixed_base &otr){ if((data += _mod - otr.data) >= _mod) data -= _mod; return *this; }
    template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base &operator+=(const T &otr){ return *this += modular_fixed_base(otr); }
    template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base &operator-=(const T &otr){ return *this -= modular_fixed_base(otr); }
    modular_fixed_base &operator++(){ return *this += 1; }
    modular_fixed_base &operator--(){ return *this += _mod - 1; }
    modular_fixed_base operator++(int){ modular_fixed_base result(*this); *this += 1; return result; }
    modular_fixed_base operator--(int){ modular_fixed_base result(*this); *this += _mod - 1; return result; }
    modular_fixed_base operator-() const{ return modular_fixed_base(_mod - data); }
    modular_fixed_base &operator*=(const modular_fixed_base &rhs){
        data = (unsigned long long)data * rhs.data % _mod;
        return *this;
    }
    template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr>
    modular_fixed_base &operator^=(T e){
        if(e < 0) *this = 1 / *this, e = -e;
        modular_fixed_base res = 1;
        for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this;
        return *this = res;
    }
    template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr>
    modular_fixed_base operator^(T e) const{
        return modular_fixed_base(*this) ^= e;
    }
    modular_fixed_base &operator/=(const modular_fixed_base &otr){
        int a = otr.data, m = _mod, u = 0, v = 1;
        if(a < _INV.size()) return *this *= _INV[a];
        while(a){
            int t = m / a;
            m -= t * a; swap(a, m);
            u -= t * v; swap(u, v);
        }
        assert(m == 1);
        return *this *= u;
    }
    uint data;
};
template<uint _mod> vector<modular_fixed_base<_mod>> modular_fixed_base<_mod>::_INV;
template<uint _mod> modular_fixed_base<_mod> modular_fixed_base<_mod>::_primitive_root;
template<uint _mod> bool operator==(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data == rhs.data; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(const modular_fixed_base<_mod> &lhs, T rhs){ return lhs == modular_fixed_base<_mod>(rhs); }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) == rhs; }
template<uint _mod> bool operator!=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return !(lhs == rhs); }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(const modular_fixed_base<_mod> &lhs, T rhs){ return !(lhs == rhs); }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(T lhs, const modular_fixed_base<_mod> &rhs){ return !(lhs == rhs); }
template<uint _mod> bool operator<(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data < rhs.data; }
template<uint _mod> bool operator>(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data > rhs.data; }
template<uint _mod> bool operator<=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data <= rhs.data; }
template<uint _mod> bool operator>=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data >= rhs.data; }
template<uint _mod> modular_fixed_base<_mod> operator+(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator+(const modular_fixed_base<_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator+(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
template<uint _mod> modular_fixed_base<_mod> operator-(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator-(const modular_fixed_base<_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator-(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
template<uint _mod> modular_fixed_base<_mod> operator*(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator*(const modular_fixed_base<_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator*(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
template<uint _mod> modular_fixed_base<_mod> operator/(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator/(const modular_fixed_base<_mod> &lhs, T rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator/(T lhs, const modular_fixed_base<_mod> &rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
template<uint _mod> istream &operator>>(istream &in, modular_fixed_base<_mod> &number){
    long long x;
    in >> x;
    number.data = modular_fixed_base<_mod>::normalize(x);
    return in;
}
// #define _PRINT_AS_FRACTION
template<uint _mod> ostream &operator<<(ostream &out, const modular_fixed_base<_mod> &number){
#ifdef LOCAL
#ifdef _PRINT_AS_FRACTION
    out << number();
    cerr << "(";
    for(auto d = 1; ; ++ d){
        if((number * d).data <= 1000000){
            cerr << (number * d).data << "/" << d;
            break;
        }
        else if((-number * d).data <= 1000000){
            cerr << "-" << (-number * d).data << "/" << d;
            break;
        }
    }
    cerr << ")";
    return out;
#else
    return out << number();
#endif
#else
    return out << number();
#endif
}
#undef _PRINT_AS_FRACTION

const uint mod = 1e9 + 7; // 1000000007
// const uint mod = (119 << 23) + 1; // 998244353
// const uint mod = 1e9 + 9; // 1000000009
using modular = modular_fixed_base<mod>;

template<bool Enable_small_to_large = true>
struct disjoint_set{
    int n, _classes;
    vector<int> p;
    disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
    int make_set(){
        p.push_back(-1);
        ++ _classes;
        return n ++;
    }
    int classes() const{
        return _classes;
    }
    int root(int u){
        return p[u] < 0 ? u : p[u] = root(p[u]);
    }
    bool share(int a, int b){
        return root(a) == root(b);
    }
    int size(int u){
        return -p[root(u)];
    }
    bool merge(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
        p[u] += p[v], p[v] = u;
        return true;
    }
    bool merge(int u, int v, auto act){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        bool swapped = false;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
        p[u] += p[v], p[v] = u;
        act(u, v, swapped);
        return true;
    }
    void clear(){
        _classes = n;
        fill(p.begin(), p.end(), -1);
    }
    vector<vector<int>> group_up(){
        vector<vector<int>> g(n);
        for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
        g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
        return g;
    }
};

const int N = 60 + 5, M = 15;

int n, m, k;
pii edge[N]; map <pii, int> mppedge;
vi adj[N];

vi path[M];

bool dfs_path(int u, int p, int endpoint, vi& path){
    path.emplace_back(u);
    if (u == endpoint){
        return true;
    }
    Fora(v, adj[u]){
        if (v == p){
            continue;
        }
        if (dfs_path(v, u, endpoint, path)){
            return true;
        }
    }
    path.pop_back();
    return false;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m >> k;
    For(i, 0, n - 1){
        int u, v; cin >> u >> v;
        mppedge[make_pair(u, v)] = mppedge[make_pair(v, u)] = i;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    For(i, 0, m){
        int u, v; cin >> u >> v;
        vi pathvertex;
        assert(dfs_path(u, u, v, pathvertex));
        For(j, 1, isz(pathvertex)){
            path[i].emplace_back(mppedge[make_pair(pathvertex[j - 1], pathvertex[j])]);
        }
    }

    modular ans = 0;
    For(msk, 0, (1 << m)){
        disjoint_set dsu(n - 1);
        For(i, 0, m){
            if ((msk >> i & 1) == 0){
                continue;
            }
            For(j, 1, isz(path[i])){
                dsu.merge(path[i][j - 1], path[i][j]);
            }
        }
        modular tans = (modular)k ^ dsu.classes();
        if (__builtin_popcount(msk) & 1){
            ans -= tans;
        }
        else{
            ans += tans;
        }
    }
    cout << ans << endl;
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message

Main.cpp:208:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  208 |     bool merge(int u, int v, auto act){
      |                              ^~~~
Main.cpp: In instantiation of 'static uint modular_fixed_base<_mod>::normalize(const T&) [with T = int; typename std::enable_if<std::is_integral<T>::value>::type* <anonymous> = 0; unsigned int _mod = 1000000007; uint = unsigned int]':
Main.cpp:70:131:   required from 'modular_fixed_base<_mod>::modular_fixed_base(const T&) [with T = int; typename std::enable_if<std::is_integral<T>::value>::type* <anonymous> = 0; unsigned int _mod = 1000000007]'
Main.cpp:276:19:   required from here
Main.cpp:73:24: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   73 |         uint v =  _mod <= sign * x ? sign * x % _mod : sign * x;
      |                   ~~~~~^~~~~~~~~~~
Main.cpp: In instantiation of 'modular_fixed_base<_mod>& modular_fixed_base<_mod>::operator/=(const modular_fixed_base<_mod>&) [with unsigned int _mod = 1000000007]':
Main.cpp:139:208:   required from 'modular_fixed_base<_mod> operator/(T, const modular_fixed_base<_mod>&) [with unsigned int _mod = 1000000007; T = int; typename std::enable_if<std::is_integral<_Size>::value>::type* <anonymous> = 0]'
Main.cpp:94:29:   required from 'modular_fixed_base<_mod>& modular_fixed_base<_mod>::operator^=(T) [with T = int; typename std::enable_if<std::is_integral<T>::value>::type* <anonymous> = 0; unsigned int _mod = 1000000007]'
Main.cpp:101:42:   required from 'modular_fixed_base<_mod> modular_fixed_base<_mod>::operator^(T) const [with T = int; typename std::enable_if<std::is_integral<T>::value>::type* <anonymous> = 0; unsigned int _mod = 1000000007]'
Main.cpp:287:49:   required from here
Main.cpp:105:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<modular_fixed_base<1000000007>, std::allocator<modular_fixed_base<1000000007> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         if(a < _INV.size()) return *this *= _INV[a];
      |            ~~^~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	320 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	2 ms	212 KB	Output is correct
6	Correct	2 ms	212 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct

Subtask #5

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	324 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	324 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	320 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	320 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	2 ms	212 KB	Output is correct
25	Correct	2 ms	212 KB	Output is correct
26	Correct	1 ms	328 KB	Output is correct
27	Correct	6 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	7 ms	212 KB	Output is correct
31	Correct	2 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	4 ms	212 KB	Output is correct
36	Correct	17 ms	412 KB	Output is correct
37	Correct	9 ms	212 KB	Output is correct