Submission #1247482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247482		erering	Digital Circuit (IOI22_circuit)	C++20	18 / 100	83 ms	96352 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define pb push_back
#define ll long long
const ll MAXN=2000+5,MOD=1000002022;
ll n,m,cnt[MAXN],am[MAXN],suff[MAXN][MAXN],pref[MAXN][MAXN];
vector<int> ch[MAXN];
ll dp[MAXN][2],prod[MAXN],num[MAXN][MAXN];
//dp[i] ammount of ways to make i black. prod[i] how many ways to assign parameters in i subtree
//num[i] how many ways such i of its threshold children are black
void dfs(int node){
    prod[node]=1;
    int seen=0;
    num[node][0]=1;
    for(auto i:ch[node]){
        if(i<n){
            dfs(i);
            prod[node]*=prod[i]*am[i]%MOD;
            prod[node]%=MOD;
            seen++;
            for(int j=seen;j>=0;j--){
                num[node][j]=num[node][j]*dp[i][0]%MOD;
                if(j>0) {
                    num[node][j] += num[node][j - 1] * dp[i][1] % MOD;
                    num[node][j] %= MOD;
                }

            }
        }
    }
   // if(node==0)cout<<num[node][1]<<' '<<num[node][2]<<endl;
    for(int i=seen;i>0;i--)suff[node][i]=(num[node][i]+suff[node][i+1])%MOD;
    pref[node][0]=num[node][0];
    for(int i=1;i<=seen;i++)pref[node][i]=(num[node][i]+pref[node][i-1])%MOD;
    for(int i=1;i<=am[node];i++){
        if(cnt[node]>=i){
            dp[node][1]+=prod[node]; dp[node][1]%=MOD;
            continue;
        }
        int req=i-cnt[node];
        if(req<=seen){
            dp[node][1]+=suff[node][req]; dp[node][1]%=MOD;
            dp[node][0]+=pref[node][req-1]; dp[node][0]%=MOD;
        }
        else{
            dp[node][0]+=prod[node]; dp[node][0]%=MOD;
        }
    }
  //  cout<<node<<' '<<dp[node][0]<<' '<<cnt[node]<<endl;
}
vector<int> a,p;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    for(int i=0;i<MAXN;i++){
        cnt[i]=0; am[i]=0; ch[i].clear(); dp[i][0]=0; dp[i][1]=0;
        for(int j=0;j<MAXN;j++){
            suff[i][j]=0;
            num[i][j]=0;
            pref[i][j]=0;
        }
    }
    p=P;
    a=A;
    n=N; m=M;
    for(int i=1;i<P.size();i++){
        ch[P[i]].pb(i);
        if(i>=n && A[i-N])cnt[P[i]]++;
        am[P[i]]++;
    }
  //  cout<<"bruv"<<cnt[2]<<endl;
}

int count_ways(int L, int R) {
    for(int i=L-n;i<=R-n;i++)a[i]^=1;
    init(n,m,p,a);
    dfs(0);
    return dp[0][1];
}
/*
 * 3 4 1
-1 0 0 1 1 2 2
0 0 0 1
6 6
 */

• 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