DanceCircle

It’s Halloween, and you’ve organized a bonfire and dance for the neighborhood children. The n children have gathered into a ring to dance around the fire. Each child is wearing one of two fun yet spooky costumes: orange pumpkin, or black bat. Since it’s dark outside, you can only see a few children at a time, as they pass behind the bonfire. The children are not standing evenly so the number of children you can see at each time differs. In particular, numbering the children 0, 1, . . . , n − 1 clockwise around the dance circle, at any given time you can see child $i_{}$ in the center of your view, as well as li children before child $i_{}$ and $r_i$ children after child $i_{}$ around the circle (i.e., child $i-l_i,……,i-1,i,i+1,……,i+r_i$ , where the indices are of course taken modulo n).

To help pass the time while the children dance, you wonder to yourself: suppose you only knew, for each child $i_{}$ , whether an even or odd number of the $l_i+r_i+1$ children centered at child i is wearing the orange pumpkin costume. Would you be able to uniquely reconstruct what costume each child is wearing? Clearly this is possible when $l_i=r_i=0$ . But what if $l_i$ and $r_i$ are not always zero? Maybe there are multiple possible solutions, or none at all? You decide to investigate, later in the evening once you’re back at your computer.

The first line of the input consists of a single integer n, indicating that there are n children in the ring (1 ≤ n ≤200 000). The following n lines describe the children you can see at different times. The $i_{th}$ line (indexed startingfrom zero) contains three space-separated non-negative integers $l_i,r_i,x_i(l_i+r_i+1≤ n,0≤ x_i≤ 1)$ : you can see $l_i+r_i+1$ children when child $i_{}$ is in the center of view (lito the left and $r_i$ to the right of child $i_{}$ ). If xi = 0 then aneven number of them are wearing the orange pumpkin costume. If $x_i$ = 1 then an odd number of them are wearingthe orange pumpkin costume.

Compute the number of ways of assigning a costume to each child, consistent with your observations. Since thisnumber might be large, print the result modulo $10^9+7$ . (If it’s impossible to find any costume assignment thatmatches all parity constraints, print 0).

#include<bits/stdc++.h> using namespace std; const int N=2e5+5; vector<int>to[N+N][2],t2[N+N][2]; int n,vis[N*2],val[N*2]; void add(int x,int y,int z){ to[x][z].push_back(y); to[y][z].push_back(x); } bool dfs(int x){ for(int y:to[x][0]){ if(vis[y]&&val[y]!=val[x]){ return 0; } if(!vis[y]){ vis[y]=1; val[y]=val[x]; if(!dfs(y))return 0; } } for(int y:to[x][1]){ if(vis[y]&&val[y]==val[x]){ return 0; } if(!vis[y]){ vis[y]=1; val[y]=1^val[x]; if(!dfs(y))return 0; } }return 1; } int work(int vn){ for(int i=1;i<=n+n;i++)t2[i][0]=to[i][0],t2[i][1]=to[i][1],vis[i]=val[i]=0; for(int i=1;i<=n;i++) add(i,i+n,vn); vis[n+n]=1;val[n+n]=0; int ans=1; if(!dfs(n+n))ans=0; for(int i=1;i<=n+n;i++)if(!vis[i]){ vis[i]=1;ans=(ans<<1)%1000000007; if(!dfs(i))ans=0; } for(int i=1;i<=n+n;i++)to[i][0]=t2[i][0],to[i][1]=t2[i][1],vis[i]=val[i]=0; return ans; } int main(){ scanf("%d",&n); for(int x,y,z,i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); int l=i-x-1,r=i+y; if(l<1)l+=n,r+=n; add(l,r,z); } int ans=(work(0)+work(1))%1000000007; printf("%d\n",ans); return 0; }

详情