C++(clang++11) 解法, 执行用时: 311ms, 内存消耗: 23804K, 提交时间: 2021-03-16 22:12:54

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10, mod = 100000007;

int a[N], b[N], fac[N], ifac[N], n, k, op;

int quick_pow(int a, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) {
      ans = 1ll * a * ans % mod;
    }
    a = 1ll * a * a % mod;
    n >>= 1;
  }
  return ans;
}

void init() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = 1ll * i * fac[i - 1] % mod;
  }
  ifac[N - 1] = quick_pow(fac[N - 1], mod - 2);
  for (int i = N - 2; i >= 0; i--) {
    ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
  }
}

void solve1() {
  for (int i = 0; i <= n - k; i++) {
    b[i] = 1ll * a[i + k] * fac[i + k] % mod * ifac[i] % mod;
  }
  int T, x;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &x);
    int ans = 0;
    for (int i = n - k; i >= 0; i--) {
      ans = (1ll * ans * x % mod + b[i]) % mod;
    }
    printf("%d\n", ans);
  }
}

void solve2() {
  for (int i = k; i <= n + k; i++) {
    b[i] = 1ll * a[i - k] * fac[i - k] % mod * ifac[i] % mod;
  }
  int T, x;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &x);
    int ans = 0;
    for (int i = n + k; i >= 0; i--) {
      ans = (1ll * ans * x % mod + b[i]) % mod;
    }
    printf("%d\n", ans);
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  init();
  scanf("%d %d %d", &n, &k, &op);
  for (int i = 0; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  if (op == 1) {
    solve1();
  }
  else {
    solve2();
  }
  return 0;
}