Submission #728645

#	Time	Username	Problem	Language	Result	Execution time	Memory
728645		grogu	Digital Circuit (IOI22_circuit)	C++17	0 / 100	9 ms	2148 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define here cerr<<"==============================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define popb pop_back
#define all(x_) x_.begin(), x_.end()

using namespace std;
#define mod 1000002022
ll add(ll x,ll y){
    x+=y;
    x%=mod;
    if(x<0) x+=mod;
    return x;
}
ll mul(ll x,ll y){
    x*=y;
    x%=mod;
    if(x<0) x+=mod;
    return x;
}
#define maxn 1005
int n,m;
int par[maxn];
int a[maxn];
int deg[maxn];
vector<int> g[maxn];
vector<int> v[maxn];
vector<int> topo;
void init(int N, int M, vector<int> P, vector<int> A) {
    n = N;
    m = M;
    for(int i = 1;i<n+m;i++){
        par[i+1] = P[i]+1;
        g[i+1].pb(P[i]+1);
        v[P[i]+1].pb(i+1);
        deg[P[i]+1]++;
    }
    for(int i = n;i<n+m;i++) a[i+1] = A[i-n];
    queue<int> q;
    for(int i = 1;i<=n+m;i++) if(!deg[i]) q.push(i);
    while(q.size()){
        int u = q.front();
        q.pop();
        if(u<=n) topo.pb(u);
        for(int s : g[u]){
            deg[s]--;
            if(!deg[s]) q.push(s);
        }
    }
}
ll dp[maxn];
ll sum[maxn][maxn];
int count_ways(int L, int R){
    L++; R++;
    for(int i = L;i<=R;i++) a[i]^=1;
    for(int i = n+1;i<=n+m;i++) dp[i] = a[i];
    for(int u : topo){
        int sz = v[u].size();
        for(int i = 0;i<=sz;i++) for(int j = 1;j<=sz;j++) sum[i][j] = 0;
        for(int i = 0;i<=sz;i++) sum[i][0] = 1;
        dp[u] = 0;
        for(int k = 1;k<=sz;k++){
            for(int j = 1;j<=sz;j++){
                ll val = dp[v[u][j-1]];
                sum[j][k] = add(sum[j-1][k],mul(sum[j-1][k-1],val));
            }
            dp[u] = add(dp[u],sum[sz][k]);
        }
    }

    return dp[1];
}
/**
3 4 2
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
**/

• 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