제출 #1183798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183798		gyg	디지털 회로 (IOI22_circuit)	C++20	18 / 100	21 ms	12368 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector 
const int N = 1e3 + 5, M = 1e3 + 5, MD = 1000002022;

int n, m;
arr<vec<int>, N + M> ch;
arr<int, N + M> on;

void init(sig _n, sig _m, vec<sig> _pr, vec<sig> _on) {
    n = _n, m = _m;
    for (int u = 2; u <= n + m; u++) {
        int pr = _pr[u - 1] + 1;
        ch[pr].push_back(u);
    }
    for (int u = n + 1; u <= n + m; u++)
        on[u] = _on[u - n - 1];
}

int md(int x) { return (x + MD) % MD; }
arr<arr<int, 2>, N + M> dp;
arr<arr<int, N + M>, N + M> kn;

void dfs(int u = 1) {
    if (u >= n + 1) {
        dp[u][0] = (on[u]) ? 0 : 1;
        dp[u][1] = (on[u]) ? 1 : 0;
        return;
    }
    for (int v : ch[u]) dfs(v);

    int k = ch[u].size();
    kn[0][0] = 1;
    for (int i = 1; i <= k; i++) {
        int v = ch[u][i - 1];
        for (int c = 0; c <= k; c++) {
            int lv = md(dp[v][0] * kn[i - 1][c]);
            int tk = (c == 0) ? 0 : md(dp[v][1] * kn[i - 1][c - 1]);
            kn[i][c] = md(lv + tk);
        }
    }

    dp[u][0] = dp[u][1] = 0;
    for (int c = 0; c <= k; c++) {
        dp[u][0] = md(dp[u][0] + (k - c) * kn[k][c]);
        dp[u][1] = md(dp[u][1] + c * kn[k][c]);
    }

    // cout << u << ": " << dp[u][0] << " " << dp[u][1] << '\n';
}

sig count_ways(sig l, sig r) {
    l++, r++;
    for (int u = l; u <= r; u++) on[u] = !on[u];

    dfs();
    return dp[1][1];
}

• 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