제출 #1211623

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

circuit

#include "circuit.h"
#include<bits/stdc++.h>
#define pb push_back
#include <vector>
using namespace std;
const int maxn = 2e3 + 10;
int n, m;
int a[maxn];
vector < int > g[maxn];
const long long mod = 1000002022;
long long dp[maxn][2];
long long val[maxn][maxn][2];
void dfs(int beg)
{
    dp[beg][0] = 0;
    dp[beg][1] = 0;
    if(!g[beg].size())
    {
        dp[beg][a[beg]] = 1;
        dp[beg][1-a[beg]] = 0;
       /// cout << " ** " << beg << " -> " << dp[beg][0] << "  " << dp[beg][1] << endl;
       /// cout << "shtoto " << a[beg] << endl;
        return;
    }
    int oldi = 0, newi = 1;
    int sz = g[beg].size();
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        int nb = g[beg][i];
        dfs(nb);
        if(i == 0)
        {
            val[beg][0][0] = dp[nb][0];
            val[beg][1][0] = dp[nb][1];
            for (int j = 2; j <= sz; ++ j)
                val[beg][j][0] = 0;
            continue;
        }
        for (int j = 0; j <= sz; ++ j)
        {
            val[beg][j][newi] = 0;
        }
        for (int j = 0; j <= sz; ++ j)
        {
            val[beg][j][newi] += val[beg][j][oldi]*dp[nb][0];
            val[beg][j][newi] %= mod;
            val[beg][j][newi] += val[beg][j-1][oldi]*dp[nb][1];
            val[beg][j][newi] %= mod;
        }
       // for (int j = 0; j <= sz; ++ j)
        swap(newi, oldi);
    }

    for (int taken = 0; taken <= g[beg].size(); ++ taken)
    {
        int tobe = taken;
        int tonot = g[beg].size() - taken;
        dp[beg][1] += val[beg][taken][oldi] * tobe;
        dp[beg][0] += val[beg][taken][oldi] * tonot;
        dp[beg][1] %= mod;
        dp[beg][0] %= mod;
    }
   /// cout << beg << " -> "  << dp[beg][0] << "  " << dp[beg][1] << endl;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    n = N;
    m = M;
    int i = 0;
    for (auto x: A)
    {
        a[n+i] = A[i];
        i ++;
    }
    i = 0;
    for (auto par: P)
    {
        if(par != -1)g[par].pb(i);
        i ++;
    }
}

int count_ways(int L, int R)
{
    for (int i = L; i <= R; ++ i)
    {
        a[i] = 1 - a[i];
    }

    dfs(0);
    return dp[0][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