제출 #1167354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167354		SmuggingSpun	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3082 ms	7412 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
const int mod =  1000002022;
void add(int& a, int b){
    if((a += b) >= mod){
        a -= mod;
    }
}
int n, m, a[lim];
vector<int>g[lim];
void init(int N, int M, vector<int>P, vector<int>A){
    n = N;
    m = M;
    for(int i = n + m - 1; i > -1; i--){
        g[P[i]].emplace_back(i);
    }
    for(int i = 0; i < m; i++){
        a[i + n] = A[i];
    }
}
int count_ways(int L, int R){
    vector<int>dp_0(n + m, 0), dp_1(n + m, 0);
    for(int i = L; i <= R; i++){
        a[i] ^= 1;
    }
    for(int i = n; i < n + m; i++){
        dp_1[i] = (dp_0[i] = int(a[i] == 0)) ^ 1;
    }
    function<void(int)>dfs;
    dfs = [&] (int s){
        vector<int>sum(g[s].size() + 1, 0);
        sum[0] = 1;
        for(int& d : g[s]){
            if(d < n){
                dfs(d);
            } 
            for(int i = g[s].size(); i > 0; i--){
                sum[i] = (1LL * sum[i] * dp_0[d] + 1LL * sum[i - 1] * dp_1[d]) % mod;
            }
            sum[0] = 1LL * sum[0] * dp_0[d] % mod;
        }
        for(int i = 0; i <= g[s].size(); i++){
            add(dp_1[s], 1LL * sum[i] * i % mod);
            add(dp_0[s], 1LL * sum[i] * (int(g[s].size()) - i) % mod);
        }
    };
    dfs(0);
    return dp_1[0];
}

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