fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define NDEBUG
  4. #include <cassert>
  5. #define clean_errno() (errno == 0 ? "None" : strerror(errno))
  6. #define log_error(M, ...) fprintf(stderr, "[assert] (%s:%d-errno:%s) " M "\n", __FILE__, __LINE__, clean_errno(), ##__VA_ARGS__)
  7. #define assertf(A, M, ...) if(!(A)) {log_error(M, ##__VA_ARGS__); assert(A); }
  8.  
  9. #include <climits>
  10. #include <cfloat>
  11.  
  12. using namespace std;
  13.  
  14. typedef long long LL;
  15. typedef unsigned long long ULL;
  16.  
  17. inline unsigned int rand16(){return ((rand()) << 15) ^ rand();}
  18. inline unsigned int rand32(){return (rand16() << 16) | rand16();}
  19. inline ULL rand64(){return ((LL)rand32() << 32) | rand32();}
  20. inline ULL random(LL l, LL r){return l == r ? l : rand64() %(r-l) +l;}
  21. inline double fRand(double fMin, double fMax) // RAND_MAX: [fMin,fMax)
  22. 	{ double f = (double)rand()/(RAND_MAX+1.0f); return fMin + f*(fMax-fMin); }
  23.  
  24. const int INF = 0x3f3f3f3f;
  25. const LL INFF = 1LL<<60;
  26. const int MOD = 1000000007;
  27. const double EPS = 1e-9;
  28. const double PI = acos(-1.0);//2*acos(0.0);//M_PI;
  29.  
  30. //4 dirs anti-cw: int dx[]={1,0,-1,0}, dy[]={0,1,0,-1};
  31. //4 dirs cw:      int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
  32. //8 dirs: int dx[]={1,1,0,-1,-1,-1,0,1}, dy[]={0,1,1,1,0,-1,-1,-1};
  33. //hex: int dx[6]={2,1,-1,-2,-1,1}, dy[6]={0,1,1,0,-1,-1};
  34. //knight: int dx[]={2,1,-1,-2,-2,-1,1,2}, dy[]={1,2,2,1,-1,-2,-2,-1};
  35.  
  36. #define FOR(i,a,b)   for(int(i)=int(a);(i)<int(b);(i)++)
  37. #define FOREQ(i,a,b) for(int(i)=int(a);(i)<=int(b);(i)++)
  38. #define RFOR(i,a,b)  for(int(i)=(a),_b(b);(i)>=_b;--(i))
  39. #define FOREACH(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  40.  
  41. #define FILL(arr,val) memset((arr),(val),sizeof(arr))
  42. #define CLR(a)        memset((a),0,sizeof(a))
  43. #define CPY(dest,src) memcpy((dest),(src),sizeof(dest))
  44.  
  45. #define ALL(a)       (a).begin(),(a).end()
  46. #define SZ(a)        ((int)(a).size())
  47. #define UNIQ(a)      sort(ALL(a)); (a).erase(unique(ALL(a)),(a).end())
  48. #define IDX(arr,ind) (lower_bound(ALL(arr),ind)-arr.begin())
  49.  
  50. #define fst first
  51. #define snd second
  52. #define pb  push_back
  53. #define mp  make_pair
  54. #define mt(a,b,c) mp(a,mp(b,c))
  55.  
  56. #include <sys/resource.h>
  57. struct rlimit rl;
  58. #define set_stk_sz \
  59. 	getrlimit(RLIMIT_STACK,&rl); \
  60. 	rl.rlim_cur=16*1024*1024; \
  61. 	setrlimit(RLIMIT_STACK, &rl);
  62.  
  63. template< typename T, size_t N >
  64. inline void print_ary(T(&ary)[N], int er)
  65. 	{for(int r = 0; r < er; r++) {cout << ary[r] << " ";}cout<<endl;}
  66. template< typename T, size_t N >
  67. inline void print_ary_eq(T(&ary)[N], int er)
  68. 	{for(int r = 1; r <= er; r++) {cout << ary[r] << " ";}cout<<endl;}
  69. template< typename T, size_t N, size_t M >
  70. inline void print_ary_2d(T(&ary)[N][M], int er, int ec)
  71. 	{for(int r = 0; r < er; r++) {for(int c = 0; c < ec; c++) {cout << ary[r][c] << " ";}cout<<endl;}}
  72. template< typename T, size_t N, size_t M >
  73. inline void print_ary_2d_eq(T(&ary)[N][M], int er, int ec)
  74. 	{for(int r = 1; r <= er; r++) {for(int c = 1; c <= ec; c++) {cout << ary[r][c] << " ";}cout<<endl;}}
  75. inline LL lcm(LL a, LL b) {return a*b/__gcd(a,b);}
  76. inline double dist(double x1, double y1, double x2, double y2)
  77. 	{return hypot(x1-x2,y1-y2);}
  78. //scanf("%[^\n]", &s);
  79. inline int is_pow_of_2(unsigned int x) {return ((x!=0) && ((x&(~x+1))==x));}
  80.  
  81. //#leading 0-bits in x (32bit fixed width representation); x=0: undefined
  82. inline int clz(int N) {return N ? 32 - __builtin_clz(N) : INT_MIN;}
  83. inline int clz(ULL N) {return N ? 64 - __builtin_clzll(N) : 0;}
  84. //#trailing 0-bits
  85. inline int ctz(int n){return (n==0?-1:ctz(n>>1)+1);}
  86. //#1-bits set
  87. #define bitcnt   __builtin_popcount
  88. #define bitcntll __builtin_popcountll
  89.  
  90. #define bin_width 32
  91. inline char* bin(int x,char *so){char s[bin_width+1];int i=bin_width;s[i--]=0x00;do{s[i--]=(x&1)?'1':'0';x>>=1;}while(x>0);i++;sprintf(so,"%s",s+i);return so;}
  92. //USAGE: char buf[bin_width+1];printf("%s",bin(N,buf));
  93.  
  94. /*
  95. const int MAXN = 10005;
  96. int fact[MAXN];
  97. #define FACT fact[0]=1;FOR(i,1,MAXN){fact[i]=(1LL*fact[i-1]*i)%MOD;}
  98. inline LL modinv(int a, int b=MOD-2) {LL x=1,y=a;while(b){if(b&1)x=(x*y)%MOD;y=(y*y)%MOD;b>>=1;}return x;}
  99. // nCr
  100. inline LL c(int n, int r) {return ((((1LL*fact[n]*modinv(fact[n-r]))%MOD)*modinv(fact[r]))%MOD);}
  101. */
  102.  
  103. vector<vector<int> > mappings;
  104. vector<int> m;
  105.  
  106. inline void recurse(int pos, const int N, vector<int> &mapping)
  107. {
  108. 	if (pos > N)
  109. 	{
  110. 		mappings.pb(mapping);
  111. 		return;
  112. 	}
  113.  
  114. 	FOREQ(i,1,N)
  115. 	{
  116. 		if (i != pos)
  117. 		{
  118. 			mapping.pb(i);
  119. 			recurse(pos+1, N, mapping);
  120. 			mapping.pop_back();
  121. 		}
  122. 	}
  123. }
  124.  
  125. inline int bfs(const vector<int> &mapping, const int N)
  126. {
  127. 	bool visited[N+1];
  128. 	FOREQ(i,1,N) { visited[i] = false; }
  129. 	int colorn[N+1], colors[N+1];
  130. 	FOREQ(i,1,N)
  131. 	{
  132. 		colorn[i] = -1;
  133. 		colors[i] = 0;
  134. 	}
  135. 	int color = 1;
  136.  
  137. 	list<int> queue;
  138. 	int len = SZ(mapping);
  139. 	if (len < 1) {return 0;}
  140. 	FOR(i,0,len)
  141. 	{
  142. 		if (!visited[i+1])
  143. 		{
  144. 			queue.pb(i+1);
  145. 		}
  146. 		if (!visited[mapping[i]])
  147. 		{
  148. 			queue.pb(mapping[i]);
  149. 		}
  150.  
  151. 		bool flag = false;
  152. 		while(!queue.empty())
  153. 		{
  154. 			int elem = queue.front();
  155. 			queue.pop_front();
  156. 			if (visited[elem]) {continue;}
  157. 			colorn[elem] = color;
  158. 			flag = true;
  159. 			colors[color]++;
  160. 			visited[elem] = true;
  161. 			FOR(j,i+1,len)
  162. 			{
  163. 				if (elem == (j+1) && !visited[mapping[j]])
  164. 				{
  165. 					queue.pb(mapping[j]);
  166. 				}
  167. 				else if (elem == mapping[j] && !visited[j+1])
  168. 				{
  169. 					queue.pb(j+1);
  170. 				}
  171. 			}
  172. 		}
  173. 		if (flag) { color++; }
  174. 	}
  175.  
  176. 	// printf("{");
  177. 	// FOREQ(i,1,N)
  178. 	// {
  179. 	// 	printf("%d:%d", i,colorn[i]);
  180. 	// 	if (i < N) { printf(","); }
  181. 	// }
  182. 	// printf("}");
  183.  
  184. 	int max_sz = 0;
  185. 	//printf("{");
  186. 	FOR(i,1,color)
  187. 	{
  188. 	//	printf("%d:%d", i,colors[i]);
  189. 	//	if (i < color-1) { printf(","); }
  190. 		max_sz = max(max_sz, colors[i]);
  191. 	}
  192. 	//printf("}");
  193. 	return max_sz;
  194. }
  195.  
  196. int main()
  197. {
  198. 	FOREQ(N,5,5)//2,9)
  199. 	{
  200. 		mappings.clear();
  201.  
  202. 		m.clear();
  203. 		recurse(1, N, m);
  204.  
  205. 		int cnts[N+1];
  206. 		FOREQ(i,0,N) { cnts[i] = 0; }
  207. 		FOREACH(mappings, itr)
  208. 		{
  209. 			int len = SZ(*itr);
  210. 			FOR(i,0,len)
  211. 			{
  212. 			//	printf("(%d,%d)", i+1,(*itr)[i]);
  213. 				if (i < len-1)
  214. 				{
  215. 				//	printf(",");
  216. 				}
  217. 			}
  218. 			int cnt = bfs(*itr, N);
  219. 			cnts[cnt]++;
  220. 		//	printf(": %d\n", cnt);
  221. 		}
  222.  
  223. 		ULL ans_top = 0ULL;
  224. 		stringstream ss;
  225. 		FOREQ(i,1,N)
  226. 		{
  227. 			if (cnts[i] > 0)
  228. 			{
  229. 				ss << i << ":" << cnts[i] << ",";
  230. 				ans_top += i*cnts[i];
  231. 			}
  232. 		}
  233. 		string s = ss.str();
  234. 		s = s.substr(0, SZ(s)-1);
  235.  
  236. 		ULL ans_btm = (ULL)pow((N-1),N);
  237. 		ULL ans_gcd = __gcd(ans_top, ans_btm);
  238.  
  239. 		printf("N=%d: {%s} %llu/%llu\n", N,s.c_str(),ans_top/ans_gcd,ans_btm/ans_gcd);
  240. 		fflush(stdout);
  241. 	}
  242. 	return 0;
  243. }
  244.  
Success #stdin #stdout 0s 3236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N=5: {3:80,5:944} 155/32
https://ideone.com/YH6Omm
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!