#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]),cmp);
/**
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++) for(int j = 1;j<=sz;j++) sum[i][j] = 0;
/*
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++){
for(int j = 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
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
2 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '347768070' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
2 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '347768070' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
1360 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
1360 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '347768070' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
2 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '347768070' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
2 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '347768070' |
| 11 |
Halted |
0 ms |
0 KB |
- |
