제출 #1312449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312449		kawhiet	디지털 회로 (IOI22_circuit)	C++20	0 / 100	205 ms	5400 KiB

circuit

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

constexpr int N = 2e5 + 5;
constexpr int mod = 1000002022;

vector<int> a;
vector<long long> dp;
vector<vector<int>> g;

int m;

void op(int i, int x, int y) {
  int d = __lg(m) - __lg(i + 1), all = (1 << d);
  dp[i] = 2 * dp[x] * dp[y] % mod + (all - dp[x]) * dp[y] % mod + (all - dp[y]) * dp[x] % mod;
  dp[i] %= mod;
}

void init(int n, int _m, vector<int> p, vector<int> c) {
  m = _m;
  a.resize(n + m);
  g.resize(n + m);
  dp.resize(n + m);
  for (int i = 1; i < n + m; i++) {
    g[i].push_back(p[i]);
    g[p[i]].push_back(i);
  }
  for (int i = 0; i < m; i++) {
    a[i + n] = c[i];
    dp[i + n] = c[i];
  }
  for (int i = n - 1; i >= 0; i--) {
    int x = i * 2 + 1, y = i * 2 + 2;
    op(i, x, y);
  }
}

int count_ways(int l, int r) {
  assert(l == r);
  int i = l;
  dp[i] ^= 1;
  while (i > 0) {
    int p = (i - 1) / 2;
    int x = 2 * p + 1, y = x + 1;
    op(p, x, y);
    i = p;
  }
  return dp[0];
}

• 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