제출 #1222808

#제출 시각아이디문제언어결과실행 시간메모리
1222808cpdreamer디지털 회로 (IOI22_circuit)C++20
18 / 100
3043 ms6380 KiB
#include "circuit.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; const long long INF = 1e17; typedef long long ll; const ll MOD = 1000002022; #define S second #define F first #define pb push_back #define V vector #define all(v) v.begin(), v.end() V<int>adj[(int)1e5+1]; ll dp[(int)2e5+1][2]; int a[(int)2e5+1]; ll add(ll a,ll b) { return ((a%MOD)+(b%MOD))%MOD; } ll mul(ll a,ll b) { return ((a%MOD*(b%MOD)))%MOD; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { for (int i =1;i<N+M;i++) { adj[i].pb(P[i]); adj[P[i]].pb(i); } for (int i=0;i<M;i++) { a[i+N]=A[i]; } } void dfs(int n,int p) { for (auto u:adj[n]) { if (u==p)continue; dfs(u,n); } ll ch=(ll)adj[n].size()-1+(n==0); if (ch==0) { dp[n][0]=(a[n]==0); dp[n][1]=(a[n]==1); return; } ll x[ch][2]; int c=0; for (auto u:adj[n]) { if (u==p)continue; x[c][0]=dp[u][0]; x[c][1]=dp[u][1]; c++; } V<ll>d(ch+1,0LL); d[0]=x[0][0]; d[1]=x[0][1]; for (ll i=1;i<ch;i++) { for (ll j=ch;j>=0;j--) { ll y=0LL; y=add(y,mul(d[j],x[i][0])); if (j>=1) { y=add(y,mul(d[j-1],x[i][1])); } d[j]=y; } } ll ans0=0,ans1=0; for (ll i=0;i<ch;i++) { ans0=add(ans0,mul(ch-i,d[i])); } for (ll i=ch;i>=1;i--) { ans1=add(ans1,mul(i,d[i])); } dp[n][0]=ans0%MOD; dp[n][1]=ans1%MOD; } int count_ways(int L, int R) { for (int i=L;i<=R;i++) { a[i]^=1; } dfs(0,-1); return (int)dp[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...