首页 > 其他 > 详细

Codeforces704C. Black Widow

时间:2018-01-13 12:09:35      阅读:61      评论:0      收藏:0      [点我收藏+]

标签:一次   appear   namespace   math.h   nds   flag   !=   fabs   post   

n<=1e5个值v,分别由<=1e5的m个变量中的1<=ki<=2个布尔变量xj(或某个变量取反)或起来组成,而所有的v异或起来为1,一个x不会在输入数据中出现超过2次,包括他和他反面。问满足该条件的布尔序列x有多少种。

如果忽略“超过两次”这个条件是难做的。。(好吧就是我看走眼了)

利用好这个条件,可以先把含相同x的v连边,由于一个x不会出现超过两次,一个v的度也不会超过2,那么就有可能形成环、链或点。

然后分别在环链上做DP,点特判即可。$f(i,0/1,0/1,0/1)$--前i个点,第一个点的第一个变量选了0还是1(判环用),上一次选的变量是0还是1,当前已经确定的v异或起来是0还是1。然后分极多种情况转移即可,要考虑一条边对应的x符号是否一样,详见代码。环的最后要特判,边的最初和最后要分端点的v是含一个变量还是两个。

比较难写。

技术分享图片
  1 #include<string.h>
  2 #include<stdlib.h>
  3 #include<stdio.h>
  4 #include<math.h>
  5 //#include<assert.h>
  6 #include<algorithm>
  7 //#include<iostream>
  8 using namespace std;
  9 
 10 int n,m;
 11 #define maxn 200011
 12 const int mod=1e9+7;
 13 struct Edge{int to,next,v;}edge[maxn<<1]; int first[maxn],le=2;
 14 void in(int x,int y,int v) {Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;}
 15 void insert(int x,int y,int v) {in(x,y,v); in(y,x,v);}
 16 
 17 struct Node
 18 {
 19     int k,id[2];
 20 }a[maxn];
 21 int appear[maxn],h[maxn][2],final[maxn][2],start[maxn],tot=0; bool vis[maxn];
 22 
 23 int sta[maxn],top=0;
 24 void findstart(int x,int fa)
 25 {
 26     vis[x]=1; sta[++top]=x;
 27     bool flag=0;
 28     for (int i=first[x];i;i=edge[i].next)
 29     {
 30         if (i==fa || (i^1)==fa) continue;
 31         flag=1;
 32         const Edge &e=edge[i];
 33         if (vis[e.to]) start[tot]=e.to;
 34         else findstart(e.to,i);
 35     }
 36     if (!flag) start[tot]=x;
 37     if (flag && fa==0 && !start[tot]) start[tot]=x;
 38 }
 39 
 40 int now,f[maxn][2][2][2];
 41 void dfs(int x,int fa)
 42 {
 43     f[x][0][0][0]%=mod;
 44     f[x][0][0][1]%=mod;
 45     f[x][0][1][0]%=mod;
 46     f[x][0][1][1]%=mod;
 47     f[x][1][0][0]%=mod;
 48     f[x][1][0][1]%=mod;
 49     f[x][1][1][0]%=mod;
 50     f[x][1][1][1]%=mod;
 51     vis[x]=1;
 52     if (!fa)
 53     {
 54         if (a[x].k==2) f[x][0][0][0]=f[x][1][1][0]=1;
 55         else f[x][0][0][0]=1;
 56     }
 57                 
 58     bool flag=0;
 59     for (int i=first[x];i;i=edge[i].next)
 60     {
 61         if (i==fa || (i^1)==fa) continue;
 62         const Edge &e=edge[i];
 63         if (vis[e.to] && !fa) continue;
 64         flag=1;
 65         bool diff;
 66         for (int j=0;j<a[x].k;j++)
 67             for (int k=0;k<a[e.to].k;k++)
 68                 if (fabs(a[x].id[j])==fabs(a[e.to].id[k]) && fabs(a[x].id[j])==e.v)
 69                     diff=(a[x].id[j]==-a[e.to].id[k]);
 70         if (vis[e.to])
 71         {
 72             if (!diff)
 73             {
 74                 h[now][0]=(0ll+f[x][0][0][0]+f[x][0][1][1]+f[x][1][0][1]+f[x][1][1][1])%mod;
 75                 h[now][1]=(0ll+f[x][0][1][0]+f[x][0][0][1]+f[x][1][0][0]+f[x][1][1][0])%mod;
 76             }
 77             else
 78             {
 79                 h[now][0]=(0ll+f[x][0][1][1]+f[x][1][0][0]+f[x][0][0][1]+f[x][1][1][1])%mod;
 80                 h[now][1]=(0ll+f[x][0][0][0]+f[x][0][1][0]+f[x][1][1][0]+f[x][1][0][1])%mod;
 81             }
 82         }
 83         else
 84         {
 85             if (!diff)
 86             {
 87                 f[e.to][0][1][1]+=f[x][0][0][0];
 88                 f[e.to][0][0][0]+=f[x][0][0][0];
 89                 f[e.to][0][1][1]+=f[x][0][1][0];
 90                 f[e.to][0][0][1]+=f[x][0][1][0];
 91                 f[e.to][0][1][0]+=f[x][0][0][1];
 92                 f[e.to][0][0][1]+=f[x][0][0][1];
 93                 f[e.to][0][1][0]+=f[x][0][1][1];
 94                 f[e.to][0][0][0]+=f[x][0][1][1];
 95                 
 96                 f[e.to][1][1][1]+=f[x][1][0][0];
 97                 f[e.to][1][0][0]+=f[x][1][0][0];
 98                 f[e.to][1][1][1]+=f[x][1][1][0];
 99                 f[e.to][1][0][1]+=f[x][1][1][0];
100                 f[e.to][1][1][0]+=f[x][1][0][1];
101                 f[e.to][1][0][1]+=f[x][1][0][1];
102                 f[e.to][1][1][0]+=f[x][1][1][1];
103                 f[e.to][1][0][0]+=f[x][1][1][1];
104             }
105             else
106             {
107                 f[e.to][0][0][1]+=f[x][0][0][0];
108                 f[e.to][0][1][0]+=f[x][0][0][0];
109                 f[e.to][0][1][1]+=f[x][0][1][0];
110                 f[e.to][0][0][1]+=f[x][0][1][0];
111                 f[e.to][0][1][1]+=f[x][0][0][1];
112                 f[e.to][0][0][0]+=f[x][0][0][1];
113                 f[e.to][0][1][0]+=f[x][0][1][1];
114                 f[e.to][0][0][0]+=f[x][0][1][1];
115                 
116                 f[e.to][1][0][1]+=f[x][1][0][0];
117                 f[e.to][1][1][0]+=f[x][1][0][0];
118                 f[e.to][1][1][1]+=f[x][1][1][0];
119                 f[e.to][1][0][1]+=f[x][1][1][0];
120                 f[e.to][1][1][1]+=f[x][1][0][1];
121                 f[e.to][1][0][0]+=f[x][1][0][1];
122                 f[e.to][1][1][0]+=f[x][1][1][1];
123                 f[e.to][1][0][0]+=f[x][1][1][1];
124             }
125             dfs(e.to,i);
126         }
127     }
128     if (!flag)
129     {
130         if (a[x].k==1)
131         {
132             h[now][1]=(0ll+f[x][0][0][1]+f[x][0][1][0]+f[x][1][0][1]+f[x][1][1][0])%mod;
133             h[now][0]=(0ll+f[x][0][1][1]+f[x][0][0][0]+f[x][1][0][0]+f[x][1][1][1])%mod;
134         }
135         else
136         {
137             h[now][0]=(0ll+f[x][0][0][1]+f[x][0][1][1]+f[x][1][0][1]+f[x][1][1][1]
138             +f[x][0][0][0]+f[x][0][1][1]+f[x][1][0][0]+f[x][1][1][1])%mod;
139             h[now][1]=(0ll+f[x][0][0][0]+f[x][0][1][0]+f[x][1][0][0]+f[x][1][1][0]
140             +f[x][0][0][1]+f[x][0][1][0]+f[x][1][0][1]+f[x][1][1][0])%mod;
141         }
142     }
143 }
144 
145 int main()
146 {
147     scanf("%d%d",&n,&m);
148     for (int i=1;i<=n;i++)
149     {
150         scanf("%d",&a[i].k);
151         for (int j=0;j<a[i].k;j++)
152         {
153             scanf("%d",&a[i].id[j]);
154             if (appear[(int)fabs(a[i].id[j])])
155             {
156                 if (appear[(int)fabs(a[i].id[j])]!=i)
157                     insert(appear[(int)fabs(a[i].id[j])],i,(int)fabs(a[i].id[j]));
158                 else
159                 {
160                     vis[i]=1; tot++;
161                     if (a[i].id[0]==-a[i].id[1]) h[tot][0]=0,h[tot][1]=2;
162                     else h[tot][0]=h[tot][1]=1;
163                 }
164                 appear[(int)fabs(a[i].id[j])]=-1;
165             }
166             else appear[(int)fabs(a[i].id[j])]=i;
167         }
168     }
169     for (int i=1;i<=m;i++) if (appear[i]>0 && a[appear[i]].k==1)
170     {
171         vis[appear[i]]=1; tot++;
172         h[tot][0]=h[tot][1]=1;
173     }
174     for (int i=1;i<=n;i++) if (!vis[i]) tot++,findstart(i,0);
175     for (;top;top--) vis[sta[top]]=0;
176     for (int i=1;i<=tot;i++) if (start[i]) now=i,dfs(start[i],0);
177     
178     final[1][0]=h[1][0]; final[1][1]=h[1][1];
179     for (int i=2;i<=tot;i++)
180     {
181         final[i][0]=(1ll*final[i-1][1]*h[i][1]+1ll*final[i-1][0]*h[i][0])%mod;
182         final[i][1]=(1ll*final[i-1][1]*h[i][0]+1ll*final[i-1][0]*h[i][1])%mod;
183     }
184     for (int i=1;i<=m;i++) if (appear[i]==0) final[tot][1]=(final[tot][1]<<1)%mod;
185     printf("%d\n",final[tot][1]);
186     return 0;
187 }
View Code

 

Codeforces704C. Black Widow

标签:一次   appear   namespace   math.h   nds   flag   !=   fabs   post   

原文:https://www.cnblogs.com/Blue233333/p/8278682.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号