Submission #1247446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247446		erering	Digital Circuit (IOI22_circuit)	C++20	2 / 100	13 ms	17480 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define pb push_back
#define ll long long
const ll MAXN=1000+5,MOD=1000002022;
ll n,m,cnt[MAXN],am[MAXN],suff[MAXN][MAXN];
vector<int> ch[MAXN];
ll dp[MAXN],prod[MAXN],num[MAXN][MAXN];
bool pos[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;
    for(auto i:ch[node]){
        if(i<n){
            dfs(i);
            prod[node]*=prod[i]*am[i]%MOD;
            prod[node]%=MOD;
            if(!pos[i])continue;
            seen++;
            for(int j=seen;j>0;j--){
                num[node][j]+=num[node][j-1]+dp[i]; num[node][j]%=MOD;
            }
        }
    }
  //  if(node==1)cout<<num[node][1]<<endl;
    for(int i=seen;i>0;i--)suff[node][i]=(num[node][i]+suff[node][i+1])%MOD;
    //assign parammeter i to node

    for(int i=1;i<=am[node];i++){
        if(cnt[node]>=i){
            pos[node]=1;
            dp[node]+=prod[node]; dp[node]%=MOD;
            continue;
        }
       // cout<<"nah "<<i<<' '<<am[node]<<' '<<node<<' '<<cnt[node]<<endl;
        int req=i-cnt[node];
        if(req>seen)continue;
        pos[node]=1;
     //   cout<<"bro "<<i<<' '<<req<<' '<<suff[node][req]<<' '<<node<<endl;
        dp[node]+=suff[node][req]; dp[node]%=MOD;
    }
   // cout<<node<<' '<<dp[node]<<' '<<prod[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; pos[i]=0;
        for(int j=0;j<MAXN;j++){
            suff[i][j]=0;
            num[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]]++;
    }
   /* for(int i=0;i<n;i++)cout<<cnt[i]<<' ';
    cout<<endl;
    for(auto i:A)cout<<i<<' ';
    cout<<endl;*/
}

int count_ways(int L, int R) {
    for(int i=L-n;i<=R-n;i++)a[i]^=1;
   // cout<<endl;
    init(n,m,p,a);
   // cout<<"goo"<<endl;
    dfs(0);
    return dp[0];
}

• 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