結果
問題 | No.2976 高階多点評価 |
ユーザー |
|
提出日時 | 2024-11-29 15:06:24 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,530 bytes |
コンパイル時間 | 9,081 ms |
コンパイル使用メモリ | 433,200 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-11-29 15:07:00 |
合計ジャッジ時間 | 29,846 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 TLE * 6 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>using namespace std;#include <boost/multiprecision/cpp_int.hpp>using Bint = boost::multiprecision::cpp_int;int main() {// 係数列を前もって計算しておく.int N = 200;vector<vector<Bint>> f(N + 1);f[0] = vector<Bint>{ 1 };for (int n = 1; n <= N; ++n) {f[n].resize(n + 1);for (int i = 0; i < n; ++i) {f[n][i + 1] -= 2 * n * f[n - 1][i];}for (int i = 1; i < n; ++i) {f[n][i - 1] += i * f[n - 1][i];f[n][i + 1] += i * f[n - 1][i];}for (int i = 0; i <= n; ++i) {f[n][i] /= n;}}vector<Bint> pow100000(N + 1);pow100000[0] = 1;for (int n = 0; n < N; ++n) {pow100000[n + 1] = pow100000[n] * 100000;}for (int n = 1; n <= N; ++n) {for (int i = 0; i <= n; ++i) {f[n][i] *= pow100000[n - i];}}int t;scanf("%d", &t);// クエリ先読みvector<long long> nXjs(t);for (int j = 0; j < t; ++j) {int n; float x;scanf("%d %f", &n, &x);long long X_int = (long long)round(x * 100000.f);nXjs[j] = ((long long)n << 40) | ((X_int + 100000) << 20) | (long long)j;}// クエリの処理順をランダムにする.mt19937_64 mt(0);shuffle(nXjs.begin(), nXjs.end(), mt);vector<float> res(t);// 答えのメモvector<map<int, float>> sol(201);for (auto nXj : nXjs) {int j = (int)(nXj & ((1LL << 20) - 1));nXj >>= 20;int X_int = (int)(nXj & ((1LL << 20) - 1)) - 100000;int n = (int)(nXj >> 20);if (n == 0) {res[j] = 1;continue;}// メモした答えの線形補間auto nit = sol[n].lower_bound(X_int);if (nit != sol[n].begin() && nit != sol[n].end()) {auto pit = prev(nit);auto [pi, pv] = *pit;auto [ni, nv] = *nit;// メモした答えの幅 40 以下の区間に挟まれているなら内挿補間するif (ni - pi <= 40) {float val = pv + (nv - pv) / (ni - pi) * (X_int - pi);res[j] = val;continue;}}Bint X = X_int;Bint X2 = X * X;// ここが遅い・・・はずなのだが思ってるよりずっと速いBint Res = 0;for (int i = n; i >= 0; i -= 2) {Res *= X2;Res += f[n][i];}if (n & 1) Res *= X;float val = static_cast<float>(Res / pow100000[n - 1]);float x = X_int / 100000.f;val *= pow(x * x + 1, -n / 2.f) / 100000.f;res[j] = val;sol[n][X_int] = val;}for (int j = 0; j < t; ++j) {printf("%1.4f\n", res[j]);}}