제출 #1234019

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

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 1e3 + 5;
int A[MAXN];
vector<int> adj[MAXN];
int N, M;

void init(int _N, int _M, std::vector<int> P, std::vector<int> _A) {
  N = _N;
  M = _M;
  for (int i = N; i < N + M; ++i) {
    A[i] = _A[i - N];
  }
  for (int i = 1; i < N + M; ++i) {
    adj[P[i]].push_back(i);
  }
}

pair<ll, ll> calc(int node) {
  if (node >= N) {
    return {A[node] ^ 1, A[node] ^ 0};
  }
  int m = adj[node].size();
  vector<pair<ll, ll>> arr(m);
  vector<vector<ll>> dp(m + 1, vector<ll>(m + 1));
  dp[0][0] = 1;
  for (int i = 0; i < m; ++i) {
    arr[i] = calc(adj[node][i]);
  }
  for (int i = 1; i <= m; ++i) {
    dp[i][0] = (dp[i - 1][0] * arr[i - 1].first) % MOD;
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= m; ++j) {
      dp[i][j] = (
        dp[i - 1][j] * arr[i - 1].first % MOD 
        +
        dp[i - 1][j - 1] * arr[i - 1].second % MOD
      ) % MOD;
    }
  }
  ll res = 0;
  for (int i = 1; i <= m; ++i) {
    res = (res + dp[m][i] * i) % MOD;
  }
  ll tot = m;
  for (int i = 0; i < m; ++i) {
    tot = (tot * (arr[i].first + arr[i].second)) % MOD;
  }
  tot = (tot - res + MOD) % MOD;
  return {tot, res};
}

int count_ways(int L, int R) {
  for (int i = L; i <= R; ++i) {
    A[i] ^= 1;
  }
  return calc(0).second;
}

• 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