結果

問題 No.2976 高階多点評価
ユーザー ecottea
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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]);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0