제출 #628044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628044		MarkBcc168	디지털 회로 (IOI22_circuit)	C++17	0 / 100	28 ms	19472 KiB

circuit

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

vector<ll> w;

const ll mod = 1e9+2022;

struct Node{
    Node *l_child, *r_child;
    int l,r; bool lazy, flipped;
    Node(){}
    Node(int _l, int _r){
        l = _l; r = _r; lazy = false;
        int m = (l+r)/2;
        if(r-l > 1){
            l_child = new Node(l,m);
            r_child = new Node(m,r);
        }
        //cout << l << " " << r << "\n";
    }
    void push(){
        if(!lazy || r-l == 1) return;
        else{
            lazy = false;
            l_child->lazy = !l_child->lazy;
            r_child->lazy = !r_child->lazy;
        }
    }
    void flip(int L, int R){
        if(R <= l || L >= r) return; //not intersect
        else if(L <= l && r <= R) lazy = !lazy;
        else if(r-l == 1) lazy = !lazy;
        else{
            l_child->flip(L,R);
            r_child->flip(L,R);
        }
    }
    ll query(){
        if(r-l == 1) return lazy * ((w[r] - w[l] + mod) % mod);
        else{
            push();
            return (l_child->query() + r_child->query()) % mod;
        }
    }
};

ll exp(ll a, ll n){
    if(n==0) return 1;
    if(n==1) return a%mod;
    ll x = exp(a, n/2);
    if(n%2==0) return (x*x)%mod;
    else return (((x*x)%mod)*a)%mod;
} 

const ll p = 2;
const ll q = 223;
const ll r = 2242157;
const ll phi = (p-1)*(q-1)*(r-1);

struct mint{
    int vp, vq; ll n;
    mint(ll _n){
        vp = 0; vq = 0;
        n = _n;
        while(n%p==0){vp++; n/=p;}
        while(n%q==0){vq++; n/=q;}
        n = n%mod;
    }
    mint(int _vp, int _vq, ll _n){
        vp = _vp; vq = _vq; n = _n%mod;
    }
    friend mint operator *(mint a, mint b){
        return mint(a.vp+b.vp, a.vq+b.vq, a.n*b.n);
    }
    mint inv(){
        return mint(-vp, -vq, exp(n,phi-1));
    }
    friend mint operator /(mint a, mint b){
        return a * b.inv();
    }
    ll to_int(){
        assert(vp >= 0 && vq >= 0);
        ll m=n;
        m = (m*exp(p,vp)) % mod;
        m = (m*exp(q,vq)) % mod;
        return m;
    }
};

int n,m;
Node tr(0,100005);

void init(int _n, int _m, std::vector<int> p, std::vector<int> a){
    n = _n; m = _m;
    //step 1: compute degree
    vector<int> adj[n];
    vector<int> d(n,0);
    vector<mint> d_mod(n,1);
    mint prod(1);
    for(int i=1; i<n+m; ++i){
        adj[p[i]].push_back(i);
        d[p[i]]++;
    }
    for(int i=0; i<n; ++i){
        d_mod[i] = mint(d[i]);
        prod = prod * d_mod[i];
    }
    //step 2: dfs to find weight of each leaf
    vector<mint> node_w(n+m, mint(1));
    node_w[0] = prod;

    vector<int> st(1,0);
    while(!st.empty()){
        int v = st[st.size()-1];
        st.pop_back();
        //cout << v << "\n";
        for(int u : adj[v]){
            node_w[u] = node_w[v] / d_mod[v];
            cout << u << " " << node_w[u].to_int() << "\n";
            if(u < n) st.push_back(u);
        }
    }
    //step 3: build the tree
    w.push_back(0);
    for(int i=0; i<m; ++i){
        w.push_back(w[i]+node_w[i+n].to_int());
        //cout << w[i+1] << " ";
    }
    for(int i=0; i<m; ++i){
        if(a[i] == 1) tr.flip(i,i+1);
    }
}
int count_ways(int l, int r){
    tr.flip(l-n,r-n+1);
    return tr.query();
}

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