fork download
copy 
  1. /*
  2.  *  [Ctsc2010]性能优化.cpp
  3.  *
  4.  *  Created on: 2011-4-19
  5.  *      Author: user
  6.  */
  7.  
  8. #include <cstdio>
  9. #include <iostream>
  10. #include <algorithm>
  11. #include <climits>
  12. #include <cstring>
  13. #include <vector>
  14. #define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
  15. using namespace std;
  16.  
  17. typedef long long int64;
  18. int64 doPowMod(int64 x, int64 e, int64 mod) {
  19. 	if (!e)
  20. 		return 1;
  21. 	if (e & 1)
  22. 		return doPowMod(x, e - 1, mod) * x % mod;
  23. 	return doPowMod(x * x % mod, e >> 1, mod);
  24. }
  25.  
  26. int64 invMod(int64 x, int64 mod) {
  27. 	return doPowMod(x, mod - 2, mod);
  28. }
  29.  
  30. int64 powMod(int64 x, int64 e, int64 mod) {
  31. 	if (e >= 0)
  32. 		return doPowMod(x, e, mod);
  33. 	int64 tmp = powMod(x, -e, mod);
  34. 	return invMod(tmp, mod);
  35. }
  36.  
  37. int n, C;
  38. const int MAX_N = 1000000;
  39. int64 a[MAX_N], b[MAX_N];
  40.  
  41. const int PRIMES[] = { 2, 3, 5, 7 };
  42.  
  43. void readInput() {
  44. 	cin >> n >> C;
  45. 	for (int i = 0; i < n; ++i) {
  46. 		int x;
  47. 		scanf("%d", &x);
  48. 		a[i] = x % (n + 1);
  49. 	}
  50. 	for (int i = 0; i < n; ++i) {
  51. 		int x;
  52. 		scanf("%d", &x);
  53. 		b[i] = x % (n + 1);
  54. 	}
  55.  
  56. 	if (C != 0) {
  57. 		C %= n;
  58. 		if (C == 0)
  59. 			C = n;
  60. 	}
  61. }
  62.  
  63. bool ispRoot(int me) {
  64. 	for (int t = 0; t < 4; ++t) {
  65. 		int x = PRIMES[t];
  66. 		if (n % x != 0)
  67. 			continue;
  68. 		if (powMod(me, n / x, n + 1) == 1)
  69. 			return false;
  70. 	}
  71. 	return true;
  72. }
  73.  
  74. int g;
  75.  
  76. void getpRoot() {
  77. 	for (int i = 2; i <= n; ++i) {
  78. 		if (ispRoot(i)) {
  79. 			g = i;
  80. 			break;
  81. 		}
  82. 	}
  83. 	//	cerr << g << endl;
  84. }
  85.  
  86. void DFT(int64 a[], int s, int rev) {
  87. 	if (s == 1)
  88. 		return;
  89. 	int d;
  90. 	for (int i = 0; i < 4; ++i) {
  91. 		if (s % PRIMES[i] == 0) {
  92. 			d = PRIMES[i];
  93. 			break;
  94. 		}
  95. 	}
  96.  
  97. 	static int64 tmp[MAX_N];
  98. 	memcpy(tmp, a, sizeof(int64) * s);
  99.  
  100. 	int64*ch[10];
  101.  
  102. 	int chS = s / d;
  103. 	int64*cur = a;
  104. 	for (int i = 0; i < d; ++i) {
  105. 		ch[i] = cur;
  106. 		cur += chS;
  107. 	}
  108.  
  109. 	for (int i = 0; i < s; ++i) {
  110. 		ch[i % d][i / d] = tmp[i];
  111. 	}
  112.  
  113. 	for (int i = 0; i < d; ++i) {
  114. 		DFT(ch[i], chS, rev);
  115. 	}
  116.  
  117. 	int64 step = powMod(g, rev * n / s, n + 1);
  118. 	int64 w = 1;
  119. 	for (int i = 0; i < s; ++i) {
  120. 		int64 p = 1;
  121. 		tmp[i] = 0;
  122. 		for (int j = 0; j < d; ++j) {
  123. 			(tmp[i] += ch[j][i % (chS)] * p) %= n + 1;
  124. 			(p *= w) %= n + 1;
  125. 		}
  126. 		(w *= step) %= n + 1;
  127. 	}
  128. 	memcpy(a, tmp, sizeof(int64) * s);
  129. }
  130.  
  131. void bfWork() {
  132. 	vector<int64> x(a, a + n);
  133. 	for (int iter = 0; iter < C; ++iter) {
  134. 		vector<int64> y(n, 0);
  135. 		for (int i = 0; i < n; ++i) {
  136. 			for (int j = 0; j < n; ++j) {
  137. 				(y[(i + j) % n] += x[i] * b[j]) %= n + 1;
  138. 			}
  139. 		}
  140. 		x = y;
  141. 	}
  142.  
  143. 	cout << "Ans:" << endl;
  144. 	for (int i = 0; i < n; ++i) {
  145. 		cout << x[i] << endl;
  146. 	}
  147. 	cout << "End" << endl;
  148. }
  149.  
  150. void work() {
  151. 	getpRoot();
  152.  
  153. 	DFT(a, n, 1);
  154.  
  155. 	//	for (int i = 0; i < n; ++i) {
  156. 	//		cout << a[i] << endl;
  157. 	//	}
  158.  
  159. 	DFT(b, n, 1);
  160. 	for (int i = 0; i < n; ++i) {
  161. 		(a[i] *= powMod(b[i], C, n + 1)) %= n + 1;
  162. 	}
  163. 	DFT(a, n, -1);
  164. 	for (int i = 0; i < n; ++i) {
  165. 		(a[i] *= invMod(n, n + 1)) %= n + 1;
  166. 	}
  167. 	for (int i = 0; i < n; ++i) {
  168. 		printf("%d\n", (int) a[i]);
  169. 	}
  170. }
  171.  
  172. void genData() {
  173. 	n = 2 * 3 * 5;
  174. 	C = rand() % 1000;
  175. 	for (int i = 0; i < n; ++i) {
  176. 		a[i] = rand() % (n + 1);
  177. 		b[i] = rand() % (n + 1);
  178. 	}
  179. }
  180.  
  181. void solve() {
  182. 	readInput();
  183. 	//	bfWork();
  184. 	work();
  185. }
  186.  
  187. int main() {
  188. 	solve();
  189. 	//	genData();
  190. 	//	bfWork();
  191. 	//	work();
  192. }
  193.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mjOj1
language:
C++ (gcc 8.3)
created:
13 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!