Submission #728665

#	Time	Username	Problem	Language	Result	Execution time	Memory
728665		grogu	Digital Circuit (IOI22_circuit)	C++17	2 / 100	12 ms	1356 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()
#define ceri(a,l,r) {cerr<<#a<<": "<<endl; for(ll i = l;i<=r;i++) cerr<<a[i]<< " ";cerr<<endl;}

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;
}
ll po(ll x,ll y){
    if(y==0) return 1;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
#define maxn 1005
int n,m;
int par[maxn];
ll a[maxn];
ll deg[maxn];
ll sub[maxn];
vector<int> g[maxn];
vector<int> v[maxn];
vector<int> topo;
bool cmp(int x,int y){
    if(x<n&&y<n) return 0;
    if(x<n) return 1;
    if(y<n) return 0;
    return 0;
}
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);
    }
    for(ll i = 1;i<=n+m;i++) sub[i] = 1;
    for(ll i = 1;i<=n;i++){
        sub[i] = deg[i];
        //for(ll x : v[i]) if(x>n) sub[i]--;
    }
    for(ll i = 1;i<=n;i++){
        ll cur = 1;
        for(ll x : v[i]) cur=mul(cur,sub[x]);
        sub[i] = mul(sub[i],cur);
    }
    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);
        }
    }
    for(ll i = 1;i<=n+m;i++) sort(all(v[i]));
    /**
    for(ll i = 1;i<=n+m;i++){
        dbg(i);
        for(ll x : v[i]) cerr<<x<< " ";
        cerr<<endl;
    }
    **/
    //ceri(sub,1,n+m);
}
ll dp[maxn];
ll sum[maxn][maxn];
ll way[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] = 1;
    //here;
    for(int u : topo){
        int sz = v[u].size();
        ll cnt = 0;
        while(sz>=1&&v[u][sz-1]>n){
            cnt+=a[v[u][sz-1]];
            sz--;
        }
        //dbg(u);
        //dbg(cnt);
        ll f = 1;
        for(int j = 1;j<=sz;j++) f = mul(f,sub[v[u][j-1]]);
        //dbg(f);
        /*
        for(int i = 0;i<=sz;i++){
            way[i] = 0;
            for(int k = 0;k<=sz;k++){
                sum[i][k] = add(mul(sub[v[u][k-1]],sum[i-1][k-1]),sum[i-1][k]);
                way[i] = add(sum[i][k],way[i]);
            }
        }
        */
        for(ll i = 0;i<=sz;i++){
            for(ll j = 0;j<=sz;j++) sum[i][j] = 0;
        }
        for(ll i = 0;i<=sz;i++) sum[i][0] = 1;
        dp[u] = mul(cnt,f);
        for(int k = 1;k<=sz;k++){
            sum[k][k] = mul(sum[k-1][k-1],dp[v[u][k-1]]);
            for(int j = k+1;j<=sz;j++){
                ll val = dp[v[u][j-1]];
                sum[j][k] = add(mul(sum[j-1][k],sub[v[u][j-1]]),mul(sum[j][k-1],val));
            }
            dp[u] = add(dp[u],sum[sz][k]);
        }
    }
    //cerr<<"dp: "<<endl;
    //for(int i = 1;i<=n;i++) cerr<<dp[i]<< " ";
    //cerr<<endl;
    return dp[1];
}
/**
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
**/

• Subtask 1: 2 / 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