Submission #1871010


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>

const long long mod = 1e9 + 7;

long long modinv(long long n) {
  if (n < 0) n += mod;
  long long ret = 1;
  long long x = n;
  while (n != 1) {
    ret *= mod - mod / n;
    ret %= mod;
    n = mod % n;
  }
  return ret;
}

long long polynomial_interpolation(std::vector<long long> a, long long x) {
  // f(0)(x-0)(x-1)...(x-n+1)
  // ------------------------
  //     (0-0)(0-1)...(0-n+1)
  const int n = a.size();
  if (x < n) return a[x];
  long long L = 1;
  long long R = 1;
  long long D = 1;
  for (int i = 0; i < n; i++) {
    R = R * -(i + 1) % mod;
    D = D * (x - i) % mod;
  }

  long long ret = 0;
  for (int i = 0; i < n; i++) {
    R = R * -modinv(n - i) % mod;
    long long y = D * modinv(x - i) % mod;
    y = y * modinv(L) % mod;
    y = y * modinv(R) % mod;
    L = L * (i + 1) % mod;
    ret = (ret + y * a[i]) % mod;
  }
  return ret;
}

int main() {
  using namespace std;

  int n;
  cin >> n;

  vector<long long> a(n + 1);

  for (int i = 0; i < n + 1; i++) {
    cin >> a[i];
  }

  long long T;
  cin >> T;

  cout << polynomial_interpolation(a, T) << endl;
}

Submission Info

Submission Time
Task D - 見たことのない多項式
User pekempey
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1212 Byte
Status AC
Exec Time 212 ms
Memory 1792 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 40 / 40 40 / 40 20 / 20
Status
AC × 2
AC × 11
AC × 19
AC × 26
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Subtask3 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask2_01.txt AC 1 ms 256 KB
subtask2_02.txt AC 3 ms 256 KB
subtask2_03.txt AC 5 ms 256 KB
subtask2_04.txt AC 5 ms 256 KB
subtask2_05.txt AC 7 ms 256 KB
subtask2_06.txt AC 7 ms 256 KB
subtask2_07.txt AC 7 ms 256 KB
subtask2_08.txt AC 7 ms 256 KB
subtask3_01.txt AC 7 ms 256 KB
subtask3_02.txt AC 206 ms 1792 KB
subtask3_03.txt AC 54 ms 640 KB
subtask3_04.txt AC 86 ms 896 KB
subtask3_05.txt AC 210 ms 1792 KB
subtask3_06.txt AC 186 ms 1792 KB
subtask3_07.txt AC 212 ms 1792 KB