fork download
copy 
  1. #include <iostream>
  2. #include <assert.h>
  3. #include <string.h>
  4.  
  5. class module_int_t
  6. {
  7. private:
  8. 	unsigned int	_value;
  9. 	static unsigned int module;
  10. public:
  11. 	static void init(unsigned int m) { module = m; }
  12. public:
  13. 	module_int_t(unsigned int v = 0):_value(v%module) { ; }
  14. 	module_int_t(const module_int_t& rhs):_value(rhs._value) { ; }
  15. 	module_int_t& operator=(const module_int_t& rhs) { _value = rhs._value;return *this; }
  16. 	~module_int_t() { ; }
  17. public:
  18. 	bool operator==(const module_int_t& rhs)const { return _value == rhs._value; }
  19. 	bool operator!=(const module_int_t& rhs)const { return _value != rhs._value; }
  20. public:
  21. 	module_int_t operator+(const module_int_t& rhs)const { return module_int_t(_value+rhs._value); }
  22. 	module_int_t& operator+=(const module_int_t& rhs) { _value = (_value+rhs._value)%module;return *this; }
  23. 	module_int_t operator-(const module_int_t& rhs)const { return module_int_t(_value+module-rhs._value); }
  24. 	module_int_t operator*(const module_int_t& rhs)const { return module_int_t(((unsigned long long)(_value)*rhs._value)%module); }
  25. 	module_int_t& operator*=(const module_int_t& rhs) { _value = ((unsigned long long)(_value)*rhs._value)%module;return *this; }
  26. public:
  27. 	unsigned int operator()()const { return _value; }
  28. };
  29.  
  30. unsigned int module_int_t::module = 0;
  31.  
  32. template<class data_t>
  33. class matrix_t
  34. {
  35. 	friend std::ostream &operator<<(std::ostream& out,const matrix_t& rhs)
  36. 	{
  37. 		for(size_t i = 0,p = 0;i < rhs._row;++i)
  38. 		{
  39. 			for(size_t j = 0;j < rhs._col;++j,++p)
  40. 			{
  41. 				out << rhs._data[p] << ' ';
  42. 			}
  43. 			out << std::endl;
  44. 		}
  45. 		return out;
  46. 	}
  47. private:
  48. 	data_t*	_data;
  49. 	size_t	_row;
  50. 	size_t	_col;
  51. 	size_t	_size;
  52. public:
  53. 	matrix_t(size_t r = 0,size_t c = 0,data_t coef = data_t()):_row(r),_col(c)
  54. 	{
  55. 		_size =_row*_col;
  56. 		_data = new data_t[_size];
  57. 		assert(NULL != _data);
  58. 		memset(_data,0,_size*sizeof(data_t));
  59. 	}
  60. 	matrix_t(const matrix_t& rhs):_row(rhs._row),_col(rhs._col)
  61. 	{
  62. 		_size = rhs._size;
  63. 		_data = new data_t[_size];
  64. 		assert(NULL != _data);
  65. 		memcpy(_data,rhs._data,_size*sizeof(data_t));
  66. 	}
  67. 	~matrix_t() { delete[] _data; }
  68. public:
  69. 	int getRow()const { return _row; }
  70. 	int getCol()const { return _col; }
  71. public:
  72. 	data_t& operator()(size_t i,size_t j) { assert(0 <= i && i < _row && 0 <= j && j < _col);return _data[i*_col+j]; }
  73. 	const data_t& operator()(size_t i,size_t j)const  { assert(0 <= i && i < _row && 0 <= j && j < _col);return _data[i*_col+j]; }
  74. public:
  75. 	const matrix_t &operator=(const matrix_t& rhs)
  76. 	{
  77. 		if(&rhs == this) return *this;
  78. 		delete[] _data;
  79. 		_row = rhs._row;_col = rhs._col;
  80. 		_size = rhs._size;
  81. 		_data = new data_t[_size];
  82. 		assert(NULL != _data);
  83. 		memcpy(_data,rhs._data,_size*sizeof(data_t));
  84. 		return *this;
  85. 	}
  86. public:
  87. 	bool operator==(const matrix_t& rhs)const
  88. 	{
  89. 		if(_row != rhs._row || _col != rhs._col) return false;
  90. 		for(size_t p = 0;p < _size;++p)
  91. 		{
  92. 			if(_data[p] != rhs._data[p]) return false;
  93. 		}
  94. 		return true;
  95. 	}
  96. 	bool operator!=(const matrix_t& rhs)const { return !((*this) == rhs); }
  97. public:
  98. 	matrix_t operator~()//矩阵转置
  99. 	{
  100. 		matrix_t result(_col,_row);
  101. 		for(size_t i = 0;i < _row;++i)
  102. 			for(size_t j = 0;j < _col;++j)
  103. 				result._data[j*_row+i]=_data[i*_col+j];
  104. 		return result;
  105. 	}
  106. 	matrix_t operator+(const matrix_t& rhs)const
  107. 	{
  108. 		matrix_t result(_row,_col);
  109. 		for(size_t p = 0;p < _size;++p) result._data[p] = _data[p]+rhs._data[p];
  110. 		return result;
  111. 	}
  112. 	matrix_t operator-(const matrix_t& rhs)const
  113. 	{
  114. 		matrix_t result(_row,_col);
  115. 		for(size_t p = 0;p < _size;++p) result._data[p] = _data[p]-rhs._data[p];
  116. 		return result;
  117. 	}
  118. 	matrix_t operator*(const matrix_t& rhs)const
  119. 	{
  120. 		if(_col != rhs._row) throw "";
  121. 		matrix_t result(_row,rhs._col);
  122.  
  123. 		for(size_t i = 0,p = 0;i < _row;++i)
  124. 		{
  125. 			for(size_t j = 0;j < rhs._col;++j,++p)
  126. 			{
  127. 				data_t v = result._data[p];
  128. 				for(size_t k = 0;k < _col;++k)
  129. 				{
  130. 					v += _data[i*_col+k]*rhs._data[k*rhs._col+j];
  131. 				}
  132. 				result._data[p] = v;
  133. 			}
  134. 		}
  135. 		return result;
  136. 	}
  137. 	// 只对方阵有效
  138. public:
  139. 	void unit()
  140. 	{
  141. 		assert(_row == _col);
  142. 		memset(_data,0,sizeof(data_t)*_size);
  143. 		for(size_t i = 0;i < _size;i += _row + 1) _data[i] = 1;
  144. 	}
  145. public:
  146. 	data_t tr()const
  147. 	{
  148. 		assert(_row == _col);
  149. 		data_t ret;
  150. 		for(size_t i = 0;i < _size;i += _row + 1) ret += _data[i];
  151. 		return ret;
  152. 	}
  153. public:
  154. 	// 矩阵快速幂
  155. 	matrix_t operator^(unsigned int x)const
  156. 	{
  157. 		assert(_row == _col);
  158. 		matrix_t result(_row,_col);result.unit();
  159. 		matrix_t product = *this;
  160. 		for(;0 != x;x >>= 1)
  161. 		{
  162. 			if(x&1) result = result*product;
  163. 			product = product*product;
  164. 		}
  165. 		return result;
  166. 	}
  167. };
  168.  
  169. #include <stdio.h>
  170. #include <string>
  171. #include <set>
  172. using std::set;
  173. using std::string;
  174.  
  175. void CodeChef201411CHEFWORD()
  176. {
  177. 	typedef matrix_t<long double> CMatrix;
  178.  
  179. 	static const size_t charset_size = 26;
  180. 	static const size_t buff_size = 100;
  181.  
  182. 	CMatrix convert(charset_size,charset_size);
  183. 	unsigned int nCases = 0;scanf("%d",&nCases);								// 1 <= nCases <= 50
  184. 	for(unsigned int iCases = 1;iCases <= nCases;++iCases)
  185. 	{
  186. 		char buff[buff_size] = { 0 },word[buff_size] = { 0 };
  187. 		unsigned int n = 0,k = 0;												// 1 <= n <= 100000,1 <= k <= 1000000000
  188. 		scanf("%d%d%s",&n,&k,buff);
  189. 		for(unsigned int i = 0;i < charset_size;++i)
  190. 		{
  191. 			for(unsigned int j = 0;j < charset_size;++j)
  192. 			{
  193. 				double v = 0;
  194. 				scanf("%lf",&v);
  195. 				convert(i,j) = v;
  196. 			}
  197. 		}
  198. 		//for(unsigned int i = 0;i < charset_size;++i)
  199. 		//{
  200. 		//	for(unsigned int j = 0;j < charset_size;++j) printf("%.9f ",convert(i,j));
  201. 		//	printf("\n");
  202. 		//}
  203. 		//printf("\n\n");
  204.  
  205. 		CMatrix result = convert^k;
  206.  
  207. 		//for(unsigned int i = 0;i < charset_size;++i)
  208. 		//{
  209. 		//	for(unsigned int j = 0;j < charset_size;++j) printf("%.9f ",result(i,j));
  210. 		//	printf("\n");
  211. 		//}
  212. 		static const long double multi_coef = 1000; 
  213. 		long double ans = 0;
  214. 		size_t len = strlen(buff);
  215. 		set<string> table;
  216. 		for(unsigned int i = 0;i < n;++i)
  217. 		{
  218. 			scanf("%s",word);
  219. 			if(strlen(word) != len) continue;
  220. 			if(table.find(word) != table.end()) continue;
  221. 			table.insert(word);
  222. 			long double v = 1.0;
  223. 			for(size_t j = 0;j < len;++j)
  224. 			{
  225. 				v *= multi_coef*result(buff[j]-'a',word[j]-'a');
  226. 				//printf("%c->%c %.9f\n",buff[j],word[j],result(buff[j]-'a',word[j]-'a'));
  227. 			}
  228. 			ans += v;
  229. 			//printf("%s = %.9f\n",word,v);
  230. 		}
  231. 		for(size_t i = 0;i < len;++i) ans /= multi_coef;
  232. 		printf("%.9f\n",ans);
  233. 	}
  234. }
  235.  
  236. int main()
  237. {
  238. 	CodeChef201411CHEFWORD();
  239. 	return 0;
  240. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
1
4 1
abc
0.25 0.25 0.25 0.25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.50 0.50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.1 0.9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
daa
bbb
ccc
zz
stdout
copy 
-0.000000000
https://ideone.com/9ZFwtm
language:
C++ (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!