fork(3) download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25. typedef unsigned int Int;
  26.  
  27. const int MAX=40;
  28. const int NUM=10;
  29. const int COLOR=3;
  30. const int P=31;
  31. LL Pow[MAX];
  32.  
  33. int n;
  34. int num[NUM][COLOR];
  35.  
  36. //1-2
  37. //2-3
  38. //3-1
  39. //1-1
  40. //2-2
  41. //3-3
  42. const int lll[]={0,1,0,0,1,2};
  43. const int rrr[]={1,2,2,0,1,2};
  44.  
  45. int g[3][3]=
  46. {
  47. 	{3,0,2},
  48. 	{0,4,1},
  49. 	{2,1,5}
  50. };
  51.  
  52. const int Mod=3000007;
  53. int tot;
  54. int hash[Mod],next[Mod];
  55. LL q[Mod];
  56.  
  57. int find(LL a)
  58. {
  59.     LL u=a% Mod;
  60.     int i;
  61.     for(i=hash[u];i;i=next[i])
  62.         if(q[i]==a)
  63.             return i;
  64. 	++tot;
  65.     next[tot]=hash[u];
  66.     hash[u]=tot;
  67.     q[tot]=a;
  68.     return tot;
  69. }
  70.  
  71. void dfs(int u,int num,LL now)
  72. {
  73. 	if(u==-1)
  74. 	{
  75. 		find(now);
  76. 		return;
  77. 	}
  78. 	int i;
  79. 	REP(i,0,num)
  80. 		dfs(u-1,num-i,now*P+i);
  81. 	return;
  82. }
  83.  
  84. LL get(LL u,int b)
  85. {
  86. 	return u/Pow[b]%P;
  87. }
  88.  
  89. const int MAXS=1947792+10;
  90.  
  91. bool Hash[MAXS][3];
  92. Int cc[MAXS][3];
  93.  
  94. Int solve(int d,int s)
  95. {
  96. 	if(Hash[d][s])
  97. 		return cc[d][s];
  98. 	if(q[d]==0)
  99. 		return 1;
  100. 	Hash[d][s]=1;
  101. 	cc[d][s]=0;
  102. 	LL p=q[d];
  103. 	int j;
  104. 	REP2(j,0,3)
  105. 		if(get(p,g[s][j]))
  106. 			cc[d][s]+=get(p,g[s][j])*solve(find(p-Pow[ g[s][j] ]),j);
  107. 	return cc[d][s];
  108. }
  109.  
  110. int nowF=0,lastF=1;
  111. Int f[2][MAXS];
  112.  
  113. map<LL,Int> F;
  114.  
  115. int used[NUM],color[NUM],top;
  116.  
  117. void dfs2(LL have,int now,vector<int> q)
  118. {
  119. 	int i,j;
  120. 	REP2(i,0,top)
  121. 		if(!used[i])
  122. 			break;
  123. 	if(i==top && !q.size())
  124. 	{
  125. 		F[have]++;
  126. 		return;
  127. 	}
  128. 	REP2(j,0,top)
  129. 		if(used[j]==now)
  130. 			break;
  131. 	if(i>j && q.size() && q[0]<=q[q.size()-1])
  132. 		dfs2(have+Pow[g[q[0]][q[q.size()-1]]],now+1,vector<int>());
  133. 	REP2(j,0,top)
  134. 		if(!used[j] && (q.size()==0 || q[q.size()-1]!=color[j]))
  135. 		{
  136. 			used[j]=now;
  137. 			vector<int> tmp=q;
  138. 			tmp.pb(color[j]);
  139. 			dfs2(have,now,tmp);
  140. 			used[j]=0;
  141. 		}
  142. }
  143.  
  144. void work(int number)//不能有相同颜色的连接在一起。。所以得暴力搜索了
  145. {
  146. 	int i,j;
  147. 	memset(used,0,sizeof used);
  148. 	top=0;
  149. 	REP2(i,0,3)
  150. 		REP2(j,0,num[number][i])
  151. 			color[top++]=i;
  152.  
  153. 	memset(used,0,sizeof used);
  154. 	F.clear();
  155. 	dfs2(0,1,vector<int>());
  156.  
  157. 	swap(nowF,lastF);
  158. 	memset(f[nowF],0,sizeof f[nowF]);
  159.  
  160. 	REP(j,1,tot)
  161. 		if(f[lastF][j])
  162. 			for(map<LL,Int>::iterator it=F.begin();it!=F.end();++it)
  163. 				f[nowF][find(q[j]+it->x)]+=f[lastF][j]*it->y;
  164. }
  165.  
  166. int main()
  167. {
  168. #ifndef ONLINE_JUDGE
  169. 	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  170. #endif
  171. 	int i,j;
  172.  
  173. 	Pow[0]=1;
  174. 	REP2(i,1,MAX)
  175. 		Pow[i]=Pow[i-1]*P;
  176.  
  177. 	scanf("%d",&n);
  178. 	REP(i,1,n)
  179. 	{
  180. 		int a,b;
  181. 		scanf("%d%d",&a,&b);
  182. 		num[b][a]++;
  183. 	}
  184.  
  185. 	memset(q,-1,sizeof q);
  186. 	tot=0;
  187.  
  188. 	dfs(5,n,0);
  189.  
  190. 	f[nowF][find(0)]=1;
  191. 	REP2(i,0,10)
  192. 		work(i);
  193.  
  194. 	Int ans=0;
  195. 	REP(i,1,tot)
  196. 		if(f[nowF][i])
  197. 			REP2(j,0,3)
  198. 				ans+=f[nowF][i]*solve(i,j);
  199. 	cout<<ans<<endl;
  200. 	return 0;
  201. }
  202.  
Success #stdin #stdout 0.05s 94080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/fkee2U
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!