Submission #629357

#	Time	Username	Problem	Language	Result	Execution time	Memory
629357		dacin21	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1299 ms	14340 KiB

circuit

#include "circuit.h"

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

template<typename traits>
class Mod_Int{
public:
    using int_t = typename traits::int_t;
    using long_t = typename traits::long_t;
    static constexpr int_t mod(){ return traits::get_mod(); };

    struct Summer{
    public:
        static constexpr long_t modmod(){ return traits::get_mod()*(long_t)traits::get_mod(); };
        static long_t modmod_step(long_t const& val){
            return val >= modmod() ? val-modmod() : val;
        }

        Summer() : val{} {}
        explicit Summer(Mod_Int const&o) : val(o.get_value()){}
        operator Mod_Int() const {
            return Mod_Int(mod_full(val));
        }

        Summer operator-(Summer const&o){
            return Summer(modmod() - modmod_step(o.val));
        }
        Summer& operator+=(Summer const&o){
            val = modmod_step(val+o.val);
            return *this;
        }
        Summer& operator-=(Summer const&o){
            return operator-=(-o);
        }
        Summer& addmul(Mod_Int const&a, Mod_Int const&b){
            val = modmod_step(val + a.get_value()*(long_t)b.get_value());
            return *this;
        }

    private:
        long_t val;
    };


    Mod_Int() : value(0) {}
    Mod_Int(int_t value_) : value(value_) {}

    friend ostream& operator<<(ostream&o, Mod_Int const&val){
        return o << val.value;
    }
    friend istream& operator>>(istream&i, Mod_Int &val){
         i >> val.value;
         val.value = mod_full(val.value);
         return i;
    }
    int_t const& get_value() const {
        return value;
    }

    Mod_Int operator+(Mod_Int const&o) const {
        Mod_Int ret(mod_step(value + o.value));
        return ret;
    }
    Mod_Int& operator+=(Mod_Int const&o){
        return *this = *this + o;
    }
    Mod_Int& operator++(){
        return operator+=(int_t{1});
    }
    Mod_Int operator-() const{
        Mod_Int ret(mod_step(mod() - value));
        return ret;
    }
    Mod_Int operator-(Mod_Int const&o) const {
        return operator+(-o);
    }
    Mod_Int& operator-=(Mod_Int const&o){
        return operator+=(-o);
    }
    Mod_Int& operator--(){
        return operator-=(int_t{1});
    }
    friend Mod_Int operator*(Mod_Int const&a, Mod_Int const&b) {
        Mod_Int ret(mod_full(a.value * static_cast<long_t>(b.value)));
        return ret;
    }
    Mod_Int& operator*=(Mod_Int const&o){
        return *this = *this * o;
    }
    Mod_Int inv() const {
        return inv_impl(value);
    }
    Mod_Int operator/(Mod_Int const&o) const {
        return *this * o.inv();
    }
    Mod_Int& operator/=(Mod_Int const&o) {
        return *this = *this / o;
    }

    bool operator==(Mod_Int const&o) const {
        return value == o.value;
    }
    bool operator!=(Mod_Int const&o) const {
        return !(*this == o);
    }
    bool operator!() const {
        return !value;
    }

private:
    static int_t mod_step(int_t const& val){
        return val >= mod() ? val-mod() : val;
    }
    static int_t mod_full(long_t const&val){
        return mod() ? val%mod() : val;
    }
    static Mod_Int inv_impl(Mod_Int const& val){
        if(mod() == 0){
            assert(val*val == 1);
            return val;
        }
        int_t value = val.value;
        constexpr size_t cache_size = traits::inv_cache_size()+1;
        static_assert(cache_size > 1);
        static array<Mod_Int, cache_size> cache = [](){
            array<Mod_Int, cache_size> ret;
            ret[1] = 1;
            for(int_t i=2;i<cache_size && i < mod();++i){
                ret[i] = -ret[mod()%i] * (mod()/i);
            }
            return ret;
        } ();
        assert(value != 0);
        Mod_Int factor = 1;
        while(value >= cache_size){
            factor *= - Mod_Int(mod() / value);
            value = mod() % value;
        }
        assert(value != 0);
        assert(factor != 0  && value != 0);
        return factor * cache[value];
    }

    int_t value;
};

template<uint32_t mod>
struct fixed_mod{
    using int_t = uint32_t;
    using long_t = uint64_t;
    static_assert(mod != 0, "Negative numbers won't work.");
    static_assert(numeric_limits<int_t>::max()/2 >= mod, "Addition might overflow.");
    static constexpr size_t inv_cache_size(){ return 30000; }
    static constexpr int_t get_mod(){ return mod; }
};
#ifdef __SIZEOF_INT128__
template<uint64_t mod>
struct fixed_mod_long{
    using int_t = uint64_t;
    using long_t = __int128;
    static_assert(mod != 0, "Negative numbers won't work.");
    static_assert(numeric_limits<int_t>::max()/2 >= mod, "Addition might overflow.");
    static constexpr size_t inv_cache_size(){ return 30000; }
    static constexpr int_t get_mod(){ return mod; }
};
#endif // __SIZEOF_INT128__
struct no_mod{
    using int_t  = int64_t;
    using long_t = int_t;
    static constexpr size_t inv_cache_size(){ return 1; }
    static constexpr int_t get_mod(){ return 0; }
};
struct mutable_mod{
    using int_t = uint32_t;
    using long_t = uint64_t;
    static int_t mod;
    // can't use cache if mod is changing
    static constexpr size_t inv_cache_size(){ return 1; }
    static int_t get_mod(){ return mod; }
};
mutable_mod::int_t mutable_mod::mod = 1000000007;

using num = Mod_Int<fixed_mod<1'000'002'022> >;

//really fast iterative segment-tree implementation
template<class Segtree_Data>
struct Segtree{
	int N, height;
	vector<typename Segtree_Data::node_t> data;
	vector<typename Segtree_Data::update_t> lazy;
	Segtree(vector<typename Segtree_Data::node_t> const&base):N(base.size()), height(__builtin_clz(1)-__builtin_clz(N)), data(2*N, Segtree_Data::node_ne()), lazy(2*N, Segtree_Data::update_ne()){
		copy(base.begin(), base.end(), data.begin()+N);
		for(int i=N-1;i>=0;--i)
			data[i]=Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
	}
	Segtree(int n):N(n), height(__builtin_clz(1)-__builtin_clz(N)), data(2*N, Segtree_Data::node_ne()), lazy(2*N, Segtree_Data::update_ne()){
		for(int i=N-1;i>=0;--i)
			data[i]=Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
	}
	void local_update(int pos, typename Segtree_Data::update_t const&val){
		Segtree_Data::update_node(data[pos], val);
		if(pos<N) lazy[pos] = Segtree_Data::merge_lazy(lazy[pos], val);
	}
	void push(int pos){
		for(int s=height;s>0;--s){
			int i=pos>>s;
			if(lazy[i]!=Segtree_Data::update_ne()){
				local_update(i<<1, lazy[i]);
				local_update(i<<1|1, lazy[i]);
				lazy[i]=Segtree_Data::update_ne();
			}
		}
	}
	void re_path(int pos){
		while(pos>>=1) Segtree_Data::update_node(data[pos] = Segtree_Data::merge_nodes(data[pos<<1], data[pos<<1|1]), lazy[pos]);
	}
	void update(int l, int r, typename Segtree_Data::update_t const&val){
		int l2=l+=N, r2=r+=N;
		push(l2); push(r2-1);
		for(;l<r;l>>=1, r>>=1){
			if(l&1) local_update(l++, val);
			if(r&1) local_update(--r, val);
		}
		re_path(l2);re_path(r2-1);
	}
	typename Segtree_Data::node_t query(int l, int r){
		push(l+N); push(r+N-1);
		typename Segtree_Data::node_t retL=Segtree_Data::node_ne(), retR=Segtree_Data::node_ne();
		for(l+=N, r+=N;l<r;l>>=1, r>>=1){
			if(l&1)retL=Segtree_Data::merge_nodes(retL, data[l++]);
			if(r&1)retR=Segtree_Data::merge_nodes(data[--r], retR);
		}
		return Segtree_Data::merge_nodes(retL, retR);
	}
};
struct Node{
    num on, off;
};
struct Segtreedata{
    typedef Node node_t;
    typedef int update_t;
    static node_t node_ne() {return Node{0, 0};}
    static update_t update_ne(){return 0;}
    static node_t merge_nodes(node_t const&left, node_t const&right){
        return Node{left.on+right.on, left.off+right.off};
    }
    static void update_node(node_t &node, update_t const&update){
        if(update % 2){
            swap(node.on, node.off);
        }
    }
    static update_t merge_lazy(update_t const&old, update_t const&update){
        return old + update;
    }
};

Segtree<Segtreedata> st(0);
int NN, MM;

void init(int N, int M, vector<int> p, vector<int> a) {
    MM = M; NN=N;
    // [0, N) is computed, [N, N+M) is given
    vector<vector<int> > ch(N);
    for(int i=1; i<N+M; ++i) ch[p[i]].push_back(i);
    vector<num> states(N+M, num(1));
    vector<num> down(N+M, num(1));
    vector<num> pre, suff;
    for(int i=N-1; i>=0; --i){
        auto &e = ch[i];
        const int d = ch[i].size();
        pre.assign(d+1, num(1));
        suff.assign(d+1, num(1));
        for(int j=0; j<d; ++j){
            pre[j+1] = pre[j] * states[e[j]];
        }
        for(int j = d-1; j>=0; --j){
            suff[j] = suff[j+1] * states[e[j]];
        }
        for(int j=0; j<d; ++j){
            down[e[j]] = pre[j] * suff[j+1];
        }
        states[i] = pre.back() * num(d);
    }
    for(int i=1; i<N+M; ++i){
        down[i] *= down[p[i]];
    }
    for(int i=N; i<N+M; ++i){
        cerr << down[i] << " ";
    }
    cerr << "\n";

    vector<Node> base(M);
    for(int i=0; i<M; ++i){
        base[i] = a[i] ? Node{down[N+i], 0} : Node{0, down[N+i]};
        // base[i] = Node{down[N+i], 0};
    }
    st = decltype(st)(base);
}

int count_ways(int L, int R) {
  L -= NN;
  R -= NN;
  ++R;
  st.update(L, R, 1);
  const num ans = st.query(0, MM).on;
  return ans.get_value();
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11