[c7b52e9] | 1 | // polynomial.cpp |
---|
| 2 | |
---|
| 3 | #define _CRT_SECURE_NO_WARNINGS |
---|
| 4 | |
---|
| 5 | #include "polynomial.h" |
---|
| 6 | #include <array> |
---|
| 7 | #include <map> |
---|
| 8 | #include <cstdio> |
---|
[25a5325] | 9 | #include <QDebug> |
---|
[c7b52e9] | 10 | |
---|
| 11 | using namespace pol; |
---|
| 12 | |
---|
| 13 | u61_t::u61_t(u64_t x): |
---|
| 14 | data(x % MOD) { |
---|
| 15 | } |
---|
| 16 | inline u61_t::operator pol::u64_t() const { |
---|
| 17 | return data; |
---|
| 18 | } |
---|
| 19 | inline u61_t u61_t::operator+(const u61_t &x) const { |
---|
| 20 | return (data + x.data) % MOD; |
---|
| 21 | } |
---|
| 22 | inline u61_t u61_t::operator-(const u61_t &x) const { |
---|
| 23 | return (data + MOD - x.data) % MOD; |
---|
| 24 | } |
---|
| 25 | u61_t u61_t::operator*(const u61_t &x) const { |
---|
| 26 | //#pragma warning(push) |
---|
| 27 | //#pragma warning(disable:4127) |
---|
| 28 | if (BUFSIZE > 4) { |
---|
| 29 | //#pragma warning(pop) |
---|
| 30 | u64_t h1 = data >> 32, h2 = x.data >> 32, l1 = data & M32, l2 = x.data & M32; |
---|
| 31 | u64_t bot = l1 * l2; |
---|
| 32 | u64_t mid = h1 * l2 + h2 * l1 + (bot >> 32); |
---|
| 33 | bot = (mid << 32) + (bot & M32); |
---|
| 34 | u64_t top = ((h1 * h2 + (mid >> 32)) << (64 - MODSIZE)) + (bot >> MODSIZE); |
---|
| 35 | return (top + (bot & MOD)) % MOD; |
---|
| 36 | } else { |
---|
| 37 | return data * x.data % MOD; |
---|
| 38 | } |
---|
| 39 | } |
---|
| 40 | u61_t u61_t::operator/(const u61_t &x) const { |
---|
| 41 | return *this * (x.inverse()); |
---|
| 42 | } |
---|
| 43 | u61_t u61_t::inverse() const { |
---|
| 44 | if (!data) { |
---|
| 45 | throw "Invalid inverse\n"; |
---|
| 46 | } |
---|
| 47 | u64_t a = MOD, b = data, r; |
---|
| 48 | std::array<u64_t, 64> q; |
---|
| 49 | q[0] = 1; |
---|
| 50 | u32_t i = 0; |
---|
| 51 | do { |
---|
| 52 | ++i; |
---|
| 53 | r = a % b; |
---|
| 54 | q[i] = a / b; |
---|
| 55 | a = b; b = r; |
---|
| 56 | } while (r); |
---|
| 57 | for (u32_t j = 2; j < i; ++j) { |
---|
| 58 | q[j] = q[j] * q[j - 1] + q[j - 2]; |
---|
| 59 | } |
---|
| 60 | |
---|
| 61 | if (i & 1) { |
---|
| 62 | return u61_t(q[i - 1]); |
---|
| 63 | } else { |
---|
| 64 | return u61_t(MOD - q[i - 1]); |
---|
| 65 | } |
---|
| 66 | } |
---|
| 67 | u61_t& u61_t::operator+=(const u61_t &x) { |
---|
| 68 | return *this = *this + x; |
---|
| 69 | } |
---|
| 70 | u61_t& u61_t::operator-=(const u61_t &x) { |
---|
| 71 | return *this = *this - x; |
---|
| 72 | } |
---|
| 73 | u61_t& u61_t::operator*=(const u61_t &x) { |
---|
| 74 | return *this = *this * x; |
---|
| 75 | } |
---|
| 76 | u61_t& u61_t::operator/=(const u61_t &x) { |
---|
| 77 | return *this = *this / x; |
---|
| 78 | } |
---|
| 79 | inline u64_t* u61_t::get_addr() { |
---|
| 80 | return &data; |
---|
| 81 | } |
---|
| 82 | inline const u64_t* u61_t::get_addr() const { |
---|
| 83 | return &data; |
---|
| 84 | } |
---|
| 85 | inline u64_t& u61_t::get_buf() { |
---|
| 86 | return data; |
---|
| 87 | } |
---|
| 88 | inline const u64_t& u61_t::get_buf() const { |
---|
| 89 | return data; |
---|
| 90 | } |
---|
| 91 | void u61_t::print(FILE *fout, u32_t i) const { |
---|
| 92 | if ((i > 0 && data != 1) || !i) { |
---|
| 93 | fprintf(fout, "%llu", data); |
---|
| 94 | } |
---|
| 95 | if (i > 1) { |
---|
| 96 | fprintf(fout, "t<sup>%u</sup>", i); |
---|
| 97 | } else if (i == 1) { |
---|
| 98 | fprintf(fout, "t"); |
---|
| 99 | } |
---|
| 100 | } |
---|
| 101 | u61_t u61_t::pow(u32_t p) const { |
---|
| 102 | u61_t res, tmp = *this; |
---|
| 103 | res = 1; |
---|
| 104 | while (p > 0) { |
---|
| 105 | if (p & 1) { |
---|
| 106 | res *= tmp; |
---|
| 107 | } |
---|
| 108 | p /= 2; |
---|
| 109 | tmp *= tmp; |
---|
| 110 | } |
---|
| 111 | return res; |
---|
| 112 | } |
---|
| 113 | |
---|
| 114 | pol_t::pol_t(): |
---|
| 115 | data(1), |
---|
| 116 | degree(0) |
---|
| 117 | { |
---|
| 118 | data[0] = 0; |
---|
| 119 | } |
---|
| 120 | void pol_t::change_degree(u32_t ndegree) { |
---|
| 121 | degree = ndegree; |
---|
| 122 | data.resize(degree + 1); |
---|
| 123 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 124 | data[i] = 0; |
---|
| 125 | } |
---|
| 126 | } |
---|
| 127 | pol_t& pol_t::operator=(const pol_t &x) { |
---|
| 128 | if (&x != this) { |
---|
| 129 | change_degree(x.degree); |
---|
| 130 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 131 | data[i] = x[i]; |
---|
| 132 | } |
---|
| 133 | } |
---|
| 134 | return *this; |
---|
| 135 | } |
---|
| 136 | u61_t& pol_t::operator[](u32_t i) { |
---|
| 137 | if (i > degree) { |
---|
| 138 | throw "Out of array bound"; |
---|
| 139 | } |
---|
| 140 | return data[i]; |
---|
| 141 | } |
---|
| 142 | const u61_t& pol_t::operator[](u32_t i) const { |
---|
| 143 | if (i > degree) { |
---|
| 144 | throw "Out of array bound"; |
---|
| 145 | } |
---|
| 146 | return data[i]; |
---|
| 147 | } |
---|
| 148 | u64_t& pol_t::operator()(u32_t i) { |
---|
| 149 | if (i > degree) { |
---|
| 150 | throw "Out of array bound"; |
---|
| 151 | } |
---|
| 152 | return data[i].get_buf(); |
---|
| 153 | } |
---|
| 154 | const u64_t& pol_t::operator()(u32_t i) const { |
---|
| 155 | if (i > degree) { |
---|
| 156 | throw "Out of array bound"; |
---|
| 157 | } |
---|
| 158 | return data[i].get_buf(); |
---|
| 159 | } |
---|
| 160 | inline u32_t pol_t::get_deg() const { |
---|
| 161 | return degree; |
---|
| 162 | } |
---|
| 163 | pol_t pol_t::operator+(const pol_t &x) const{ |
---|
| 164 | pol_t tmp; |
---|
| 165 | u32_t tempdeg; |
---|
| 166 | if (degree < x.degree) { |
---|
| 167 | tempdeg = x.degree; |
---|
| 168 | } else { |
---|
| 169 | tempdeg = degree; |
---|
| 170 | } |
---|
| 171 | tmp.change_degree(tempdeg); |
---|
| 172 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 173 | tmp[i] = data[i]; |
---|
| 174 | } |
---|
| 175 | for (u32_t i = 0; i <= x.degree; ++i) { |
---|
| 176 | tmp[i] += x[i]; |
---|
| 177 | } |
---|
| 178 | while (tmp.degree > 0 && !tmp[tmp.degree]) { |
---|
| 179 | --(tmp.degree); |
---|
| 180 | } |
---|
| 181 | return tmp; |
---|
| 182 | } |
---|
| 183 | pol_t pol_t::operator-(const pol_t &x) const { |
---|
| 184 | pol_t tmp; |
---|
| 185 | u32_t tempdeg; |
---|
| 186 | if (degree < x.degree) { |
---|
| 187 | tempdeg = x.degree; |
---|
| 188 | } else { |
---|
| 189 | tempdeg = degree; |
---|
| 190 | } |
---|
| 191 | tmp.change_degree(tempdeg); |
---|
| 192 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 193 | tmp[i] = data[i]; |
---|
| 194 | } |
---|
| 195 | for (u32_t i = 0; i <= x.degree; ++i) { |
---|
| 196 | tmp[i] -= x[i]; |
---|
| 197 | } |
---|
| 198 | while (tmp.degree > 0 && !tmp[tmp.degree]) { |
---|
| 199 | --(tmp.degree); |
---|
| 200 | } |
---|
| 201 | return tmp; |
---|
| 202 | } |
---|
| 203 | pol_t pol_t::operator*(const pol_t &x) const { |
---|
| 204 | pol_t tmp; |
---|
| 205 | tmp.change_degree(degree + x.degree); |
---|
| 206 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 207 | for (u32_t j = 0; j <= x.degree; ++j) { |
---|
| 208 | tmp[i + j] += data[i] * x[j]; |
---|
| 209 | } |
---|
| 210 | } |
---|
| 211 | while (tmp.degree > 0 && !tmp[tmp.degree]) { |
---|
| 212 | --tmp.degree; |
---|
| 213 | } |
---|
| 214 | return tmp; |
---|
| 215 | } |
---|
| 216 | pol_t pol_t::operator%(const pol_t &x) const { |
---|
| 217 | if (!x) { |
---|
| 218 | throw "Polinomial denominator = 0"; |
---|
| 219 | } |
---|
| 220 | pol_t tmp = *this; |
---|
| 221 | if (!x.degree) { |
---|
| 222 | return pol_t(); |
---|
| 223 | } else { |
---|
| 224 | u61_t inv = x[x.degree].inverse(); |
---|
| 225 | for (u32_t i = tmp.degree; i >= x.degree; --i) { |
---|
| 226 | u61_t q = tmp[i] * inv; |
---|
| 227 | for (u32_t j = 0; j <= x.degree; ++j) { |
---|
| 228 | tmp[i - j] -= x[x.degree - j] * q; |
---|
| 229 | } |
---|
| 230 | } |
---|
| 231 | while (tmp.degree > 0 && !tmp[tmp.degree]) { |
---|
| 232 | --tmp.degree; |
---|
| 233 | } |
---|
| 234 | return tmp; |
---|
| 235 | } |
---|
| 236 | } |
---|
| 237 | pol_t pol_t::operator/(const pol_t &x) const { |
---|
| 238 | if (!x) { |
---|
| 239 | throw "Polinomial devision by 0"; |
---|
| 240 | } else if (x.degree > degree) { |
---|
| 241 | return pol_t(); |
---|
| 242 | } else if (x.degree) { |
---|
| 243 | pol_t tmp = *this, res; |
---|
| 244 | res.change_degree(tmp.degree - x.degree); |
---|
| 245 | u61_t q = x[x.degree].inverse(); |
---|
| 246 | for (u32_t i = tmp.degree; i >= x.degree; --i) { |
---|
| 247 | res[i - x.degree] = tmp[i] * q; |
---|
| 248 | for (u32_t j = 0; j <= x.degree; ++j) { |
---|
| 249 | tmp[i - j] -= x[x.degree - j] * res[i - x.degree]; |
---|
| 250 | } |
---|
| 251 | } |
---|
| 252 | return res; |
---|
| 253 | } else { |
---|
| 254 | pol_t res = *this; |
---|
| 255 | u61_t q = x[0].inverse(); |
---|
| 256 | for (u32_t i = 0; i <= res.degree; ++i) { |
---|
| 257 | res[i] *= q; |
---|
| 258 | } |
---|
| 259 | return res; |
---|
| 260 | } |
---|
| 261 | } |
---|
| 262 | pol_t& pol_t::operator+=(const pol_t&x) { |
---|
| 263 | return *this = *this + x; |
---|
| 264 | } |
---|
| 265 | pol_t& pol_t::operator-=(const pol_t&x) { |
---|
| 266 | return *this = *this - x; |
---|
| 267 | } |
---|
| 268 | pol_t& pol_t::operator*=(const pol_t&x) { |
---|
| 269 | return *this = *this * x; |
---|
| 270 | } |
---|
| 271 | pol_t& pol_t::operator%=(const pol_t&x) { |
---|
| 272 | return *this = *this % x; |
---|
| 273 | } |
---|
| 274 | pol_t& pol_t::operator/=(const pol_t&x) { |
---|
| 275 | return *this = *this / x; |
---|
| 276 | } |
---|
| 277 | pol_t::operator bool() const { |
---|
| 278 | return degree || data[0]; |
---|
| 279 | } |
---|
| 280 | bool pol_t::operator==(const pol_t &x) const { |
---|
| 281 | if (x.degree != degree) { |
---|
| 282 | return false; |
---|
| 283 | } else { |
---|
| 284 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 285 | if (data[i] != x(i)) { |
---|
| 286 | return false; |
---|
| 287 | } |
---|
| 288 | } |
---|
| 289 | } |
---|
| 290 | return true; |
---|
| 291 | } |
---|
| 292 | pol_t pol_t::pow(u32_t p) const { |
---|
| 293 | pol_t res, tmp = *this; |
---|
| 294 | res(0) = 1; |
---|
| 295 | while (p > 0) { |
---|
| 296 | if (p & 1) { |
---|
| 297 | res *= tmp; |
---|
| 298 | } |
---|
| 299 | p /= 2; |
---|
| 300 | tmp *= tmp; |
---|
| 301 | } |
---|
| 302 | return res; |
---|
| 303 | } |
---|
| 304 | pol_t pol_t::mpow(u64_t p, const pol_t &m) const { |
---|
| 305 | pol_t res, tmp = *this % m; |
---|
| 306 | res(0) = 1; |
---|
| 307 | while (p > 0) { |
---|
| 308 | if (p & 1) { |
---|
| 309 | res = res * tmp % m; |
---|
| 310 | } |
---|
| 311 | p /= 2; |
---|
| 312 | tmp = tmp * tmp % m; |
---|
| 313 | } |
---|
| 314 | return res; |
---|
| 315 | } |
---|
| 316 | pol_t pol_t::mpow(u64_t p, u64_t d, const pol_t &m) const { |
---|
| 317 | pol_t tmp = mpow((p - 1) / 2, m), res; |
---|
| 318 | res[0] = 1; |
---|
| 319 | for (u64_t i = 0; i < d; ++i) { |
---|
| 320 | res = res * tmp % m; |
---|
| 321 | tmp = tmp.mpow(p, m); |
---|
| 322 | } |
---|
| 323 | return res; |
---|
| 324 | } |
---|
| 325 | pol_t pol_t::normalize() const { |
---|
| 326 | pol_t res = *this; |
---|
| 327 | u61_t q = data[degree].inverse(); |
---|
| 328 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 329 | res[i] *= q; |
---|
| 330 | } |
---|
| 331 | return res; |
---|
| 332 | } |
---|
| 333 | pol_t pol_t::deriv() const{ |
---|
| 334 | pol_t res; |
---|
| 335 | if (degree) { |
---|
| 336 | res.change_degree(degree - 1); |
---|
| 337 | for (u32_t i = degree; i > 0; --i) { |
---|
| 338 | res[i - 1] = u61_t(i) * data[i]; |
---|
| 339 | } |
---|
| 340 | } |
---|
| 341 | while (res.degree > 0 && !res[res.degree]) { |
---|
| 342 | --res.degree; |
---|
| 343 | } |
---|
| 344 | return res; |
---|
| 345 | } |
---|
| 346 | |
---|
| 347 | void pol_t::read(FILE *fin, pol_format_t format) { |
---|
| 348 | degree = 0; |
---|
| 349 | switch (format) |
---|
| 350 | { |
---|
| 351 | case BINPR: |
---|
| 352 | std::fread(°ree, 1, 1, fin); |
---|
| 353 | if (degree > 256) { |
---|
| 354 | throw "Incorrect polynomial degree"; |
---|
| 355 | } |
---|
| 356 | data.resize(degree + 1); |
---|
| 357 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 358 | u64_t buf; |
---|
| 359 | std::fread(&buf, BUFSIZE, 1, fin); |
---|
| 360 | if (buf >= MOD) { |
---|
| 361 | throw "Incorrect polinomial coefficient"; |
---|
| 362 | } |
---|
| 363 | data[i] = buf; |
---|
| 364 | } |
---|
| 365 | break; |
---|
| 366 | case TEXTPR: |
---|
| 367 | std::fscanf(fin, "%u", °ree); |
---|
| 368 | if (degree > 256) { |
---|
| 369 | throw "Incorrect polynomial degree"; |
---|
| 370 | } |
---|
| 371 | data.resize(degree + 1); |
---|
| 372 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 373 | u64_t buf; |
---|
| 374 | std::fscanf(fin, "%llu", &buf); |
---|
| 375 | if (buf >= MOD) { |
---|
| 376 | throw "Incorrect polinomial coefficient"; |
---|
| 377 | } |
---|
| 378 | data[i] = buf; |
---|
| 379 | } |
---|
| 380 | break; |
---|
| 381 | case HTMLPR: |
---|
| 382 | break; |
---|
| 383 | default: |
---|
| 384 | break; |
---|
| 385 | } |
---|
| 386 | } |
---|
| 387 | void pol_t::write(FILE *fout, pol_format_t format, bool eol) const { |
---|
| 388 | switch (format) |
---|
| 389 | { |
---|
| 390 | case pol::BINPR: |
---|
| 391 | fwrite(°ree, 1, 1, fout); |
---|
| 392 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 393 | fwrite(data[i].get_addr(), BUFSIZE, 1, fout); |
---|
| 394 | } |
---|
| 395 | break; |
---|
| 396 | case pol::TEXTPR: |
---|
| 397 | fprintf(fout, "%u ", degree); |
---|
| 398 | for (u32_t i = 0; i <= degree; ++i) { |
---|
| 399 | fprintf(fout, "%llu ", data[i].get_buf()); |
---|
| 400 | } |
---|
| 401 | if (eol) fprintf(fout, "\n"); |
---|
| 402 | break; |
---|
| 403 | case pol::HTMLPR: |
---|
| 404 | { |
---|
| 405 | u32_t i = degree; |
---|
| 406 | u32_t min = 0; |
---|
| 407 | while (min < degree && !data[min]) ++min; |
---|
| 408 | --min; |
---|
| 409 | data[i].print(fout, i); |
---|
| 410 | --i; |
---|
| 411 | for (; i != min; --i) { |
---|
| 412 | if (data[i]) { |
---|
| 413 | fprintf(fout, " + "); |
---|
| 414 | data[i].print(fout, i); |
---|
| 415 | } |
---|
| 416 | } |
---|
| 417 | if (eol) fprintf(fout, "<br>"); |
---|
| 418 | } |
---|
| 419 | break; |
---|
| 420 | default: |
---|
| 421 | break; |
---|
| 422 | } |
---|
| 423 | } |
---|
| 424 | void pol_t::ddf(u32_t max_deg, vector_t &res) const { |
---|
| 425 | pol_t v = *this, x = get_x(), xp = x, tmp; |
---|
| 426 | res.resize(max_deg + 1); |
---|
| 427 | for (u32_t i = 0; i <= max_deg; ++i) { |
---|
| 428 | res[i](0) = 1; |
---|
| 429 | } |
---|
| 430 | u32_t i = 1; |
---|
| 431 | for (; i <= max_deg; ++i) { |
---|
| 432 | xp = xp.mpow(MOD, v); |
---|
| 433 | tmp = gcd(xp - x, v); |
---|
| 434 | if (tmp.degree > 0) { |
---|
| 435 | res[i] = tmp; |
---|
| 436 | v /= tmp; |
---|
| 437 | } |
---|
| 438 | //fprintf(stderr, "%d of %d\n", i, max_deg); |
---|
| 439 | } |
---|
| 440 | res[0] = v; |
---|
| 441 | } |
---|
| 442 | void pol_t::split(u32_t deg, vector_t &res) const { |
---|
| 443 | u32_t count = degree / deg, found = 0; |
---|
| 444 | pol_t r_pol, r_gcd, unit; |
---|
| 445 | unit[0] = 1; |
---|
| 446 | std::list<pol_t> l1, l2; |
---|
| 447 | l1.push_back(*this); |
---|
| 448 | std::list<pol_t> *cur = &l1, *next = &l2; |
---|
| 449 | while (found < count) { |
---|
| 450 | r_pol = get_rand_pol(deg); |
---|
| 451 | next->clear(); |
---|
| 452 | for (auto i = cur->begin(), end = cur->end(); i != end; ++i) { |
---|
| 453 | if (i->degree == deg) { |
---|
| 454 | res.push_back(*i); |
---|
| 455 | ++found; |
---|
| 456 | } else { |
---|
| 457 | r_gcd = gcd(r_pol.mpow(MOD, deg, *i) - unit, *i); |
---|
| 458 | if (r_gcd.degree && r_gcd.degree < i->degree) { |
---|
| 459 | *i /= r_gcd; |
---|
| 460 | if (i->degree == deg) { |
---|
| 461 | res.push_back(*i); |
---|
| 462 | ++found; |
---|
| 463 | } |
---|
| 464 | else { |
---|
| 465 | next->push_back(*i); |
---|
| 466 | } |
---|
| 467 | if (r_gcd.degree == deg) { |
---|
| 468 | res.push_back(r_gcd); |
---|
| 469 | ++found; |
---|
| 470 | } |
---|
| 471 | else { |
---|
| 472 | next->push_back(r_gcd); |
---|
| 473 | } |
---|
| 474 | } |
---|
| 475 | else { |
---|
| 476 | next->push_back(*i); |
---|
| 477 | } |
---|
| 478 | } |
---|
| 479 | } |
---|
| 480 | std::swap(cur, next); |
---|
| 481 | } |
---|
| 482 | } |
---|
| 483 | void pol_t::fact(u32_t max_deg, vector_t &res) const { |
---|
| 484 | pol_t d = gcd(deriv(), *this), tmp; |
---|
| 485 | if (d.degree) { |
---|
| 486 | tmp = *this / d; |
---|
| 487 | } else { |
---|
| 488 | tmp = *this; |
---|
| 489 | } |
---|
| 490 | std::vector<pol_t> ddf_pol; |
---|
| 491 | tmp.ddf(max_deg, ddf_pol); |
---|
| 492 | for (u32_t i = 1; i <= max_deg; ++i) { |
---|
| 493 | if (ddf_pol[i].degree > 0) { |
---|
| 494 | ddf_pol[i].split(i, res); |
---|
| 495 | } |
---|
| 496 | } |
---|
| 497 | if (d.degree) { |
---|
| 498 | for (size_t i = 0, size = res.size(); i < size && d.degree; ++i) { |
---|
| 499 | while (!(d % res[i])) { |
---|
| 500 | res.push_back(res[i]); |
---|
| 501 | d /= res[i]; |
---|
| 502 | } |
---|
| 503 | } |
---|
| 504 | } |
---|
| 505 | } |
---|
| 506 | |
---|
| 507 | deg_t::deg_t() : key(0) {} |
---|
| 508 | deg_t::deg_t(u32_t a, u32_t b) : |
---|
| 509 | x(a), |
---|
| 510 | y(b) |
---|
| 511 | { |
---|
| 512 | } |
---|
| 513 | bool deg_t::operator<(const deg_t °) const{ |
---|
| 514 | return key < deg.key; |
---|
| 515 | } |
---|
| 516 | bool deg_t::operator==(const deg_t °) const{ |
---|
| 517 | return key == deg.key; |
---|
| 518 | } |
---|
| 519 | deg_t deg_t::operator+(const deg_t °) const { |
---|
| 520 | return deg_t(x + deg.x, y + deg.y); |
---|
| 521 | } |
---|
| 522 | |
---|
| 523 | pol3v_t::pol3v_t() { |
---|
| 524 | data.clear(); |
---|
| 525 | data.push_back(pol3v1_t()); |
---|
| 526 | dx = 0; dy = 0; dt = 0; |
---|
| 527 | } |
---|
| 528 | pol3v_t::pol3v_t(const polmap_t &m) : |
---|
| 529 | data(), |
---|
| 530 | dx(0), |
---|
| 531 | dy(0), |
---|
| 532 | dt(0) |
---|
| 533 | { |
---|
| 534 | data.clear(); |
---|
| 535 | bool empty = true; |
---|
| 536 | for (auto i = m.begin(); i != m.end(); ++i) { |
---|
| 537 | if (i->second) { |
---|
| 538 | if (empty) { |
---|
| 539 | empty = false; |
---|
| 540 | } |
---|
| 541 | data.push_back(*i); |
---|
| 542 | if (dx < i->first.x) dx = i->first.x; |
---|
| 543 | if (dy < i->first.y) dy = i->first.y; |
---|
| 544 | if (dt < i->second.get_deg()) dt = i->second.get_deg(); |
---|
| 545 | } |
---|
| 546 | } |
---|
| 547 | if (empty) { |
---|
| 548 | data.push_back(pol3v1_t()); |
---|
| 549 | } |
---|
| 550 | } |
---|
| 551 | pol3v_t& pol3v_t::operator=(const pol3v_t &x) { |
---|
| 552 | if (&x != this) { |
---|
| 553 | data.clear(); |
---|
| 554 | data = x.data; |
---|
| 555 | dx = x.dx; dy = x.dy; dt = x.dt; |
---|
| 556 | } |
---|
| 557 | return *this; |
---|
| 558 | } |
---|
| 559 | pol3v_t pol3v_t::operator+(const pol3v_t &x) const { |
---|
| 560 | polmap_t tmp; |
---|
| 561 | for (auto i = data.begin(); i != data.end(); ++i) { |
---|
| 562 | if (tmp.find(i->first) == tmp.end()) { |
---|
| 563 | tmp.insert(*i); |
---|
| 564 | } else { |
---|
| 565 | tmp[i->first] += i->second; |
---|
| 566 | } |
---|
| 567 | } |
---|
| 568 | for (auto i = x.data.begin(); i != x.data.end(); ++i) { |
---|
| 569 | if (tmp.find(i->first) == tmp.end()) { |
---|
| 570 | tmp.insert(*i); |
---|
| 571 | } else { |
---|
| 572 | tmp[i->first] += i->second; |
---|
| 573 | } |
---|
| 574 | } |
---|
| 575 | return tmp; |
---|
| 576 | } |
---|
| 577 | pol3v_t pol3v_t::operator-(const pol3v_t &x) const { |
---|
| 578 | polmap_t tmp; |
---|
| 579 | for (auto i = data.begin(); i != data.end(); ++i) { |
---|
| 580 | if (tmp.find(i->first) == tmp.end()) { |
---|
| 581 | tmp.insert(*i); |
---|
| 582 | } else { |
---|
| 583 | tmp[i->first] += i->second; |
---|
| 584 | } |
---|
| 585 | } |
---|
| 586 | for (auto i = x.data.begin(); i != x.data.end(); ++i) { |
---|
| 587 | if (tmp.find(i->first) == tmp.end()) { |
---|
| 588 | tmp.insert(pol3v1_t(i->first, pol_t() - i->second)); |
---|
| 589 | } else { |
---|
| 590 | tmp[i->first] -= i->second; |
---|
| 591 | } |
---|
| 592 | } |
---|
| 593 | return tmp; |
---|
| 594 | } |
---|
| 595 | pol3v_t pol3v_t::operator*(const pol3v_t &x) const { |
---|
| 596 | polmap_t tmp; |
---|
| 597 | for (auto i = data.begin(); i != data.end(); ++i) { |
---|
| 598 | for (auto j = x.data.begin(); j != x.data.end(); ++j) { |
---|
| 599 | if (tmp.find(i->first + j->first) == tmp.end()) { |
---|
| 600 | tmp.insert(pol3v1_t(i->first + j->first, i->second * j->second)); |
---|
| 601 | } else { |
---|
| 602 | tmp[i->first + j->first] += i->second * j->second; |
---|
| 603 | } |
---|
| 604 | } |
---|
| 605 | } |
---|
| 606 | return tmp; |
---|
| 607 | } |
---|
| 608 | pol3v_t& pol3v_t::operator+=(const pol3v_t &x) { |
---|
| 609 | return *this = *this + x; |
---|
| 610 | } |
---|
| 611 | pol3v_t& pol3v_t::operator-=(const pol3v_t &x) { |
---|
| 612 | return *this = *this - x; |
---|
| 613 | } |
---|
| 614 | pol3v_t& pol3v_t::operator*=(const pol3v_t &x) { |
---|
| 615 | return *this = *this * x; |
---|
| 616 | } |
---|
| 617 | pol_t pol3v_t::subst(const pol_t &x, const pol_t &y) const { |
---|
| 618 | pol_t res; |
---|
| 619 | for (auto i = data.begin(), end = data.end(); i != end; ++i) { |
---|
| 620 | res += x.pow(i->first.x) * y.pow(i->first.y) * i->second; |
---|
| 621 | } |
---|
| 622 | return res; |
---|
| 623 | } |
---|
| 624 | pol3v_t pol3v_t::get_same_rand_pol() const { |
---|
| 625 | pol3v_t res = *this; |
---|
| 626 | for (auto i = res.data.begin(), end = res.data.end(); i != end; ++i) { |
---|
| 627 | i->second = get_rand_pol(i->second.get_deg(), false); |
---|
| 628 | } |
---|
| 629 | return res; |
---|
| 630 | } |
---|
| 631 | void pol3v_t::read(FILE *fin, pol_format_t format) { |
---|
| 632 | size_t count = 0; |
---|
| 633 | data.clear(); |
---|
| 634 | switch (format) |
---|
| 635 | { |
---|
| 636 | case BINPR: |
---|
| 637 | { |
---|
| 638 | std::fread(&count, 1, sizeof(count), fin); |
---|
| 639 | if (!count) { |
---|
| 640 | data.push_back(pol3v1_t()); |
---|
| 641 | dx = 0; dy = 0; dt = 0; |
---|
| 642 | } |
---|
| 643 | deg_t deg; |
---|
| 644 | for (size_t i = 0; i < count; ++i) { |
---|
| 645 | std::fread(&(deg.key), sizeof(deg.key), 1, fin); |
---|
| 646 | pol_t tmp; |
---|
| 647 | tmp.read(fin, BINPR); |
---|
| 648 | if (tmp) { |
---|
| 649 | data.push_back(pol3v1_t(deg, tmp)); |
---|
| 650 | if (deg.x > dx) dx = deg.x; |
---|
| 651 | if (deg.y > dy) dy = deg.y; |
---|
| 652 | if (tmp.get_deg() > dt) dt = tmp.get_deg(); |
---|
| 653 | } |
---|
| 654 | } |
---|
| 655 | break; |
---|
| 656 | } |
---|
| 657 | case TEXTPR: |
---|
| 658 | std::fscanf(fin, "%zu", &count); |
---|
| 659 | if (!count) { |
---|
| 660 | data.clear(); |
---|
| 661 | data.push_back(pol3v1_t()); |
---|
| 662 | dx = 0; dy = 0; dt = 0; |
---|
| 663 | } else { |
---|
| 664 | for (size_t i = 0; i < count; ++i) { |
---|
| 665 | u32_t v[2]; |
---|
| 666 | fscanf(fin, "%u%u", v, v + 1); |
---|
| 667 | pol_t tmp; |
---|
| 668 | tmp.read(fin, TEXTPR); |
---|
| 669 | if (tmp) { |
---|
| 670 | data.push_back(pol3v1_t(deg_t(v[0], v[1]), tmp)); |
---|
| 671 | if (v[0] > dx) dx = v[0]; |
---|
| 672 | if (v[1] > dy) dy = v[1]; |
---|
| 673 | if (tmp.get_deg() > dt) dt = tmp.get_deg(); |
---|
| 674 | } |
---|
| 675 | } |
---|
| 676 | } |
---|
| 677 | break; |
---|
| 678 | case HTMLPR: |
---|
| 679 | break; |
---|
| 680 | default: |
---|
| 681 | break; |
---|
| 682 | } |
---|
| 683 | } |
---|
| 684 | void pol3v_t::write(FILE *fout, pol_format_t format, bool eol) const { |
---|
| 685 | size_t count = data.size(); |
---|
| 686 | switch (format) |
---|
| 687 | { |
---|
| 688 | case pol::BINPR: |
---|
| 689 | std::fwrite(&count, 1, sizeof(count), fout); |
---|
| 690 | for (auto i = data.begin(), end = data.end(); i != end; ++i) { |
---|
| 691 | std::fwrite(&(i->first.key), sizeof(i->first.key), 1, fout); |
---|
| 692 | i->second.write(fout, BINPR); |
---|
| 693 | } |
---|
| 694 | break; |
---|
| 695 | case TEXTPR: |
---|
| 696 | std::fprintf(fout, "%zu\n", count); |
---|
| 697 | for (auto i = data.begin(), end = data.end(); i != end; ++i) { |
---|
| 698 | fprintf(fout, "%u %u ", i->first.x, i->first.y); |
---|
| 699 | i->second.write(fout, TEXTPR, true); |
---|
| 700 | } |
---|
| 701 | if (eol) { |
---|
| 702 | fprintf(fout, "\n"); |
---|
| 703 | } |
---|
| 704 | break; |
---|
| 705 | case pol::HTMLPR: |
---|
| 706 | if (!count) { |
---|
| 707 | fprintf(fout, "0"); |
---|
| 708 | } else { |
---|
| 709 | auto i = data.rbegin(); |
---|
| 710 | if (i->first.x > 1) { |
---|
| 711 | fprintf(fout, "x<sup>%u</sup>", i->first.x); |
---|
| 712 | } |
---|
| 713 | else if (i->first.x == 1) { |
---|
| 714 | fprintf(fout, "x"); |
---|
| 715 | } |
---|
| 716 | if (i->first.y > 1) { |
---|
| 717 | fprintf(fout, "y<sup>%u</sup>", i->first.y); |
---|
| 718 | } |
---|
| 719 | else if (i->first.y == 1) { |
---|
| 720 | fprintf(fout, "y"); |
---|
| 721 | } |
---|
| 722 | fprintf(fout, "("); |
---|
| 723 | i->second.write(fout, HTMLPR); |
---|
| 724 | fprintf(fout, ")"); |
---|
| 725 | ++i; |
---|
| 726 | for (auto end = data.rend(); i != end; ++i) { |
---|
| 727 | fprintf(fout, " + "); |
---|
| 728 | if (i->first.x > 1) { |
---|
| 729 | fprintf(fout, "x<sup>%u</sup>", i->first.x); |
---|
| 730 | } |
---|
| 731 | else if (i->first.x == 1) { |
---|
| 732 | fprintf(fout, "x"); |
---|
| 733 | } |
---|
| 734 | if (i->first.y > 1) { |
---|
| 735 | fprintf(fout, "y<sup>%u</sup>", i->first.y); |
---|
| 736 | } |
---|
| 737 | else if (i->first.y == 1) { |
---|
| 738 | fprintf(fout, "y"); |
---|
| 739 | } |
---|
| 740 | fprintf(fout, "("); |
---|
| 741 | i->second.write(fout, HTMLPR); |
---|
| 742 | fprintf(fout, ")"); |
---|
| 743 | } |
---|
| 744 | } |
---|
| 745 | if (eol) { |
---|
| 746 | fprintf(fout, "<br>"); |
---|
| 747 | } |
---|
| 748 | break; |
---|
| 749 | default: |
---|
| 750 | break; |
---|
| 751 | } |
---|
| 752 | } |
---|
| 753 | |
---|
| 754 | File::File() : |
---|
| 755 | file(NULL), |
---|
| 756 | opened(false), |
---|
| 757 | mode(READ), |
---|
| 758 | buf(0), |
---|
| 759 | pos(0), |
---|
| 760 | count(0) |
---|
| 761 | { |
---|
| 762 | } |
---|
| 763 | File::File(FILE *_file, file_mode_t m) : |
---|
| 764 | file(_file), |
---|
| 765 | opened(false), |
---|
| 766 | mode(m), |
---|
| 767 | buf(0), |
---|
| 768 | pos(0), |
---|
| 769 | count(0) |
---|
| 770 | { |
---|
| 771 | } |
---|
| 772 | File::File(const char *file_name, file_mode_t m) : |
---|
| 773 | file(NULL), |
---|
| 774 | opened(false), |
---|
| 775 | mode(m), |
---|
| 776 | buf(0), |
---|
| 777 | pos(0), |
---|
| 778 | count(0) |
---|
| 779 | { |
---|
| 780 | if (!open(file_name, m)) { |
---|
| 781 | throw "Can't open the file"; |
---|
| 782 | } |
---|
| 783 | } |
---|
| 784 | File::~File() { |
---|
| 785 | close(); |
---|
| 786 | } |
---|
| 787 | bool File::open(const char *file_name, file_mode_t m) { |
---|
| 788 | if ((mode = m) == READ) { |
---|
| 789 | file = fopen(file_name, "rb"); |
---|
| 790 | } else { |
---|
| 791 | file = fopen(file_name, "wb"); |
---|
| 792 | } |
---|
| 793 | return opened = !!(file); |
---|
| 794 | } |
---|
| 795 | void File::close() { |
---|
| 796 | if (opened) { |
---|
| 797 | flush(); |
---|
| 798 | fclose(file); |
---|
| 799 | opened = false; |
---|
| 800 | mode = READ; |
---|
| 801 | } |
---|
| 802 | } |
---|
| 803 | void File::flush() { |
---|
| 804 | if (mode == WRITE && count) { |
---|
| 805 | buf = (buf >> pos) & ((1ull << count) - 1); |
---|
| 806 | fwrite(&buf, 1, (count - 1) / 8 + 1, file); |
---|
| 807 | } |
---|
| 808 | count = 0; |
---|
| 809 | pos = 0; |
---|
| 810 | buf = 0; |
---|
| 811 | } |
---|
| 812 | size_t File::read(u61_t &block) { |
---|
| 813 | if (mode != READ || !opened) { |
---|
| 814 | throw "Incorrect read"; |
---|
| 815 | } |
---|
| 816 | u64_t res = 0; |
---|
| 817 | size_t cur = 0; |
---|
| 818 | if (count) { |
---|
| 819 | res = (buf >> pos) & ((1ull << MODSIZE) - 1) & ((1ull << count) - 1); |
---|
| 820 | cur = count < MODSIZE ? count : MODSIZE; |
---|
| 821 | } |
---|
| 822 | if (cur < MODSIZE) { |
---|
| 823 | buf = 0; |
---|
| 824 | count = 8 * fread(&buf, 1, (MODSIZE - cur - 1) / 8 + 1, file); |
---|
| 825 | read_size += count / 8; |
---|
| 826 | res |= (buf << cur) & ((1ull << MODSIZE) - 1); |
---|
| 827 | } |
---|
| 828 | if (res >= MOD || (res < (1ull << (MODSIZE - 1)))) { |
---|
| 829 | res &= (1ull << (MODSIZE - 1)) - 1; |
---|
| 830 | if (count > MODSIZE - 1 - cur) { |
---|
| 831 | count -= MODSIZE - 1 - cur; |
---|
| 832 | pos = MODSIZE - 1 - cur; |
---|
| 833 | cur = MODSIZE - 1; |
---|
| 834 | } else { |
---|
| 835 | cur += count; |
---|
| 836 | count = 0; |
---|
| 837 | } |
---|
| 838 | } else { |
---|
| 839 | count -= MODSIZE - cur; |
---|
| 840 | pos = MODSIZE - cur; |
---|
| 841 | cur = MODSIZE; |
---|
| 842 | } |
---|
| 843 | block = res; |
---|
| 844 | return cur; |
---|
| 845 | } |
---|
| 846 | size_t File::write(const u61_t &block, size_t block_size) { |
---|
| 847 | if (mode != WRITE || !opened) { |
---|
| 848 | throw "Incorrect write"; |
---|
| 849 | } |
---|
| 850 | u64_t tmp = block; |
---|
| 851 | size_t size; |
---|
| 852 | if (tmp >= (1ull << (MODSIZE - 1))) { |
---|
| 853 | size = MODSIZE; |
---|
| 854 | } else { |
---|
| 855 | size = block_size; |
---|
| 856 | } |
---|
| 857 | if (!count) { |
---|
| 858 | buf = 0; |
---|
| 859 | } |
---|
| 860 | buf |= tmp << count; |
---|
| 861 | if (size + count >= 8 * sizeof(buf)) { |
---|
| 862 | fwrite(&buf, 1, sizeof(buf), file); |
---|
| 863 | } |
---|
| 864 | if (size + count > 8 *sizeof(buf)) { |
---|
| 865 | buf = tmp >> (sizeof(buf)* 8 - count); |
---|
| 866 | } |
---|
| 867 | count = (size + count) % (8 * sizeof(buf)); |
---|
| 868 | return size; |
---|
| 869 | } |
---|
| 870 | |
---|
| 871 | random_t::random_t() : |
---|
| 872 | generator(std::time(NULL)) |
---|
| 873 | { |
---|
| 874 | } |
---|
| 875 | u61_t random_t::operator()() { |
---|
| 876 | return u64_t((generator() - 1.) / generator.max() * MOD); |
---|
| 877 | } |
---|
| 878 | |
---|
| 879 | pol_t pol::gcd(const pol_t &x, const pol_t &y) { |
---|
| 880 | pol_t a = x, b = y, q; |
---|
| 881 | while (q = a % b, q) { |
---|
| 882 | a = b; |
---|
| 883 | b = q; |
---|
| 884 | } |
---|
| 885 | return b.normalize(); |
---|
| 886 | } |
---|
| 887 | pol_t pol::get_x() { |
---|
| 888 | pol_t res; |
---|
| 889 | res.change_degree(1); |
---|
| 890 | res[1] = 1; |
---|
| 891 | return res; |
---|
| 892 | } |
---|
| 893 | |
---|
| 894 | pol_t pol::get_rand_pol(u32_t deg, bool flag) { |
---|
| 895 | static random_t get_coef; |
---|
| 896 | pol_t res; |
---|
| 897 | res.change_degree(deg); |
---|
| 898 | //res[deg] = flag ? 1 : get_coef(); |
---|
| 899 | while (!res(deg)) { |
---|
| 900 | res[deg] = get_coef(); |
---|
| 901 | } |
---|
| 902 | for (u32_t i = 0; i < deg; ++i) { |
---|
[25a5325] | 903 | res[i] = get_coef(); |
---|
| 904 | } |
---|
[c7b52e9] | 905 | return res; |
---|
| 906 | } |
---|
| 907 | |
---|
| 908 | |
---|
| 909 | pol3v_t pol::XXX_get_f(const u64_t max_deg, const u32_t key_deg) { |
---|
| 910 | polmap_t tmp; |
---|
| 911 | for (u32_t i = 0; i <= max_deg; ++i) { |
---|
[25a5325] | 912 | tmp.insert(pol3v1_t(deg_t(i, i), get_rand_pol(key_deg - 1))); |
---|
| 913 | } |
---|
[c7b52e9] | 914 | return tmp; |
---|
| 915 | } |
---|
| 916 | |
---|
| 917 | pol3v_t pol::XXX_get_mes(const u64_t max_deg, const u32_t key_deg, const u64_t size, const std::vector<u61_t> &m) { |
---|
| 918 | polmap_t tmp; |
---|
| 919 | pol_t tmp2; |
---|
| 920 | u64_t block_count = m.size(); |
---|
| 921 | tmp2.change_degree(key_deg - 1); |
---|
| 922 | for (u32_t i = 0; i < max_deg; ++i) { |
---|
| 923 | for (u32_t j = 0; j < key_deg; ++j) { |
---|
| 924 | if (i * key_deg + j < block_count) { |
---|
| 925 | tmp2[j] = m[block_count - 1 - (i * key_deg + j)]; |
---|
| 926 | } |
---|
| 927 | else { |
---|
| 928 | tmp2(j) = 0; |
---|
| 929 | } |
---|
| 930 | } |
---|
| 931 | tmp.insert(pol3v1_t(deg_t(i, i), tmp2)); |
---|
| 932 | } |
---|
| 933 | tmp2.change_degree(0); |
---|
| 934 | tmp2[0] = size; |
---|
| 935 | tmp.insert(pol3v1_t(deg_t(u32_t(max_deg), u32_t(max_deg)), tmp2)); |
---|
| 936 | return tmp; |
---|
| 937 | } |
---|
| 938 | void pol::XXX_get_fact(const vector_t &fact, u64_t deg, vector_t &res) { |
---|
| 939 | size_t num = fact.size(); |
---|
| 940 | std::vector<std::list<pol_t>> tmp; |
---|
| 941 | tmp.resize(deg + 1); |
---|
| 942 | for (size_t i = 0; i < num; ++i) { |
---|
| 943 | u32_t pol_deg = fact[i].get_deg(); |
---|
| 944 | for (auto j = tmp.rbegin(); j != tmp.rend(); ++j) { |
---|
| 945 | for (auto it = j->begin(); it != j->end(); ++it) { |
---|
| 946 | if (pol_deg + it->get_deg() <= deg) { |
---|
| 947 | tmp[pol_deg + it->get_deg()].push_back(fact[i] * *it); |
---|
| 948 | } |
---|
| 949 | } |
---|
| 950 | } |
---|
| 951 | if (pol_deg <= deg) { |
---|
| 952 | tmp[pol_deg].push_back(fact[i]); |
---|
| 953 | } |
---|
| 954 | } |
---|
| 955 | res.clear(); |
---|
| 956 | for (auto i = tmp[deg].begin(); i != tmp[deg].end(); ++i) { |
---|
| 957 | res.push_back(*i); |
---|
| 958 | } |
---|
| 959 | } |
---|
| 960 | |
---|