Advertisement
Guest User

Untitled

a guest
Feb 17th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.58 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <utility>
  10. #include <cstdlib>
  11. #include <memory>
  12. #include <queue>
  13. #include <cassert>
  14. #include <cmath>
  15. #include <ctime>
  16. #include <complex>
  17. #include <bitset>
  18.  
  19. using namespace std;
  20.  
  21. #define pb push_back
  22. #define fst first
  23. #define snd second
  24. #define mp make_pair
  25. #define sz(C) ((int) (C).size())
  26. #define forn(i, n) for (int i = 0; i < (int) n; ++i)
  27. #define ford(i, n) for (int i = ((int) n) - 1; i >= 0; --i)
  28. #define y1 gftxdtrtfhyjfctrxujkvbhyjice
  29. #define y0 ehfoiuvhefroerferjhfjkehfjke
  30. #define left sdhfsjkshdjkfsdfgkqqweqweh
  31. #define right yytrwtretywretwreytwreytwr
  32. #define next jskdfksdhfjkdsjksdjkgf
  33. #define prev koeuigrihjdkjdfj
  34. #define hash kjfdkljkdhgjdkfhgurehg
  35. #define all(C) begin(C), end(C)
  36.  
  37. typedef long long ll;
  38. typedef unsigned long long ull;
  39. typedef unsigned int uint;
  40. typedef pair <int,int> pii;
  41. typedef pair <ll, ll> pll;
  42. typedef vector <ll> vll;
  43. typedef vector <int> vi;
  44. typedef vector <vector <int> > vvi;
  45. typedef vector <pii> vii;
  46. typedef long double ld;
  47. typedef complex<ld> cd;
  48. typedef vector<cd> vcd;
  49.  
  50. const ld EPS = 1e-9;
  51. const int MOD = 998244353;
  52. const int MAXN = 1e6 + 10;
  53. const int A = 26;
  54. const ld PI = acos(-1.0);
  55.  
  56. struct TimeStamp {
  57. string s;
  58. double start;
  59.  
  60. TimeStamp(const string& s) : s(s) {
  61. start = (double) clock() / CLOCKS_PER_SEC;
  62. }
  63.  
  64. ~TimeStamp() {
  65. printf("%s ends in %.5f\n", s.c_str(), (double) clock() / CLOCKS_PER_SEC - start);
  66. }
  67. };
  68.  
  69. void addmod(int& x, int y, int mod) {
  70. (x += y) >= mod && (x -= mod);
  71. }
  72.  
  73. int mulmod(int x, int y, int mod) {
  74. return x * 1ll * y % mod;
  75. }
  76.  
  77. #define ld double
  78.  
  79. namespace FFT {
  80. struct cd {
  81. ld a, b;
  82.  
  83. cd(ld a, ld b) : a(a), b(b) {}
  84.  
  85. cd(ld x = 0) : a(x), b(0) {}
  86.  
  87. ld real() const {
  88. return a;
  89. }
  90.  
  91. void operator += (const cd& other) {
  92. a += other.a;
  93. b += other.b;
  94. }
  95.  
  96. void operator -= (const cd& other) {
  97. a -= other.a;
  98. b -= other.b;
  99. }
  100.  
  101. void operator *= (const cd& other) {
  102. tie(a, b) = mp(a * other.a - b * other.b, a * other.b + b * other.a);
  103. }
  104.  
  105. friend cd operator * (const cd& x, const cd& y) {
  106. cd r = x;
  107. r *= y;
  108. return r;
  109. }
  110.  
  111. friend cd operator + (const cd& x, const cd& y) {
  112. cd r = x;
  113. r += y;
  114. return r;
  115. }
  116.  
  117. friend cd operator - (const cd& x, const cd& y) {
  118. cd r = x;
  119. r -= y;
  120. return r;
  121. }
  122.  
  123. void operator /= (ld c) {
  124. a /= c;
  125. b /= c;
  126. }
  127. };
  128.  
  129. typedef vector<cd> vcd;
  130.  
  131. const int LOG = 15;
  132. const int N = 1 << LOG;
  133.  
  134. int rev[N];
  135. cd root_[N];
  136.  
  137. inline cd root(int k, int n) {
  138. return root_[k * (N / n)];
  139. }
  140.  
  141. void precalc() {
  142. rev[0] = 0;
  143. int hb = -1;
  144. for (int i = 1; i < N; ++i) {
  145. if ((i & (i - 1)) == 0) {
  146. ++hb;
  147. }
  148. rev[i] = rev[i ^ (1 << hb)] | (1 << (LOG - hb - 1));
  149. }
  150.  
  151. forn(i, N) {
  152. ld ang = PI * i * 2.0 / N;
  153. root_[i] = cd(cosl(ang), sinl(ang));
  154. }
  155. }
  156.  
  157. void fft_rec(cd* a, int n) {
  158. if (n == 1) {
  159. return;
  160. }
  161.  
  162. fft_rec(a, n / 2);
  163. fft_rec(a + n / 2, n / 2);
  164.  
  165. forn(k, n / 2) {
  166. cd w = root(k, n);
  167. cd x = a[k];
  168. cd y = w * a[k + n / 2];
  169. a[k] = x + y;
  170. a[k + n / 2] = x - y;
  171. }
  172. }
  173.  
  174. void fft(vcd& a) {
  175. int n = sz(a);
  176. vcd na(n, cd(0, 0));
  177. forn(i, n) na[i] = a[rev[i]];
  178. na.swap(a);
  179.  
  180. fft_rec(&a[0], n);
  181. }
  182.  
  183. void fft_inv(vcd& a) {
  184. fft(a);
  185. int n = sz(a);
  186. reverse(a.begin() + 1, a.end());
  187. forn(i, n) {
  188. a[i] /= n;
  189. }
  190. }
  191.  
  192. vi mult(const vi& a, const vi& b) {
  193. // TimeStamp t("mult");
  194. vcd A(N, cd(0, 0));
  195. vcd B(N, cd(0, 0));
  196. forn(i, sz(a)) A[i] = a[i];
  197. forn(i, sz(b)) B[i] = b[i];
  198.  
  199. fft(A);
  200. fft(B);
  201.  
  202. forn(i, N) A[i] *= B[i];
  203.  
  204. fft_inv(A);
  205.  
  206. vi c(N, 0);
  207. forn(i, N) c[i] = ((ll) (A[i].real() + 0.5)) % MOD;
  208.  
  209. return c;
  210. }
  211.  
  212. vi multmod(const vi& a, const vi& b) {
  213. // a = a0 + sqrt(MOD) * a1
  214. // a = a0 + base * a1
  215. int base = (int) sqrtl(MOD);
  216.  
  217. vi a0(sz(a)), a1(sz(a));
  218. forn(i, sz(a)) {
  219. a0[i] = a[i] % base;
  220. a1[i] = a[i] / base;
  221. assert(a[i] == a0[i] + base * a1[i]);
  222. }
  223.  
  224. vi b0(sz(b)), b1(sz(b));
  225. forn(i, sz(b)) {
  226. b0[i] = b[i] % base;
  227. b1[i] = b[i] / base;
  228. assert(b[i] == b0[i] + base * b1[i]);
  229. }
  230.  
  231. vi a01 = a0;
  232. forn(i, sz(a)) {
  233. addmod(a01[i], a1[i], MOD);
  234. }
  235.  
  236. vi b01 = b0;
  237. forn(i, sz(b)) {
  238. addmod(b01[i], b1[i], MOD);
  239. }
  240.  
  241. vi C = mult(a01, b01); // 1
  242.  
  243. vi a0b0 = mult(a0, b0); // 2
  244. vi a1b1 = mult(a1, b1); // 3
  245.  
  246. vi mid = C;
  247. forn(i, N) {
  248. addmod(mid[i], -a0b0[i] + MOD, MOD);
  249. addmod(mid[i], -a1b1[i] + MOD, MOD);
  250. }
  251.  
  252. vi res = a0b0;
  253. forn(i, N) {
  254. addmod(res[i], mulmod(base, mid[i], MOD), MOD);
  255. }
  256.  
  257. base = mulmod(base, base, MOD);
  258. forn(i, N) {
  259. addmod(res[i], mulmod(base, a1b1[i], MOD), MOD);
  260. }
  261.  
  262. return res;
  263. }
  264. };
  265.  
  266. int P, M;
  267. int p[MAXN];
  268.  
  269. void precalc() {
  270. p[0] = 1;
  271. for (int i = 1; i < MAXN; ++i) {
  272. p[i] = mulmod(p[i - 1], P, M);
  273. }
  274. }
  275.  
  276.  
  277. int main() {
  278.  
  279.  
  280. FFT::precalc();
  281.  
  282. vi a = {MOD-1, MOD-2, MOD-3}, b = {MOD-1, 0, 0};
  283.  
  284. b = FFT::multmod(a, b);
  285. cout << b.size() << endl;
  286. for (auto i : b) {
  287. cout << i << ' ' ;
  288. }
  289. cout << endl;
  290. return 0;
  291. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement