Помогите найти ошибку задача Гиперфиксные суммы

Question

Пробовал решать напролом, получилось что-то такое: Саму обработку массивов вынес в отдельную функцию

#include <stdio.h>
#include <vector>
using namespace std;
vector <long long> rec(vector <long long> z, long long k){  
    vector <long long> temp(z.size());
    temp = z;
    for (int i = 0; i < k; i++){
        long long summ = 0;
        for(long long i = 0; i < z.size(); i++){
            summ += z[i];
            temp[i] = summ;          
        }
        z = temp;
    }
    return temp;
}
int main(){
    long long n, k;
    scanf("%lld %lld", &n, &k);
    vector <long long> h(n);
    for(int i = 0; i < n; i++){
        scanf("%lld", &h[i]);
    }  
    for (auto el : rec(h, k)){
        printf("%lld ", el);
    }
}

Но на 4 тесте выдаёт неправильный ответ, что тут надо поправить?

UPD1:

Добавил остаток от деления, но теперь не проходит по времени на 27 тесте

Код такой:

#include <stdio.h>
#include <vector>
using namespace std;
vector <long long> rec(vector <long long> z, long long k){  
    vector <long long> temp(z.size());
    temp = z;
    for (int i = 0; i < k; i++){
        long long summ = 0;
        for(long long i = 0; i < z.size(); i++){
            summ += z[i];
            temp[i] = summ % 998244353;
        }
        z = temp;
    }
    return temp;
}
int main(){
    long long n, k;
    scanf("%lld %lld", &n, &k);
    vector <long long> h(n);
    for(int i = 0; i < n; i++){
        scanf("%lld", &h[i]);
    }  
    for (auto el : rec(h, k)){
        printf("%lld ", el);
    }
}

Answer 1

Простое решение, но оно не годится на k ~ 10**9

#include <iostream>

const auto MOD = 998244353;

void solve(int* arr, const int n, int k) {
  for (auto r = 0; r < k; ++r) {
    for (auto i = 0; i < n-1; ++i) {
      arr[i+1] = (arr[i] + arr[i+1]) % MOD;
    }
  }
}

int main() {
  const int n = 20;
  int k = 1e6; int arr[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

  solve(arr, n, k);

  for (auto i = 0; i < n; ++i) {
    if (i) std::cout << ' ';
    std::cout << arr[i];
  }
  std::cout << std::endl;
}

Способ пошустрее — вычисляем сразу последнюю строку из первой.

/**
 * Расширенная версия алгоритма Евклида для поиска НОД
 * Помимо самого НОД находит корни уравнения x*a+y*b = gcd(a, b)
 */
int64_t gcd_ex(uint64_t a, uint64_t b, int64_t &x, int64_t &y) {
  if (a == 0) {
    x = 0; y = 1;
    return b;
  }
  int64_t x1, y1, t;
  int64_t d = gcd_ex((b+a) % a, a, x1, y1);
  t = (b / a) * x1;
  x = y1 - t;
  y = x1;

  return d;
}
/**
 * Поиск обратного a элемента b по модулю m,
 * такого, что a * b = 1 (mod m)
 */
uint64_t reciprocal_mod(uint64_t a, uint64_t m) { // a**-1 (mod m)
  int64_t x{}, y{};
  if (gcd_ex(a, m, x, y) == 1) {

    return x < 0 ? x + m : x;
  }
  std::cerr << a << " and " << m << " are not coprimes\n";
  return 1; // no reciprocal
}

void solve_sqr(int* arr, const int n, int k) {
    // A_k_i = A_0_i + \sum_{j=1}^i -1^{j-1}* \frac{k!}{j!(k-j)!}*A_0_{(i-j)}
    
    for (int i = 1; i < n; ++i) {
      // Реализация суммирования ряда по формуле выше
      uint64_t term = k;
      auto sign = 1;
      for (int j = 1; j <= i; ++j) {
        // arr[i] += sign * term * arr[i-j];
        // term = term * (k-j) / (j+1);
        uint64_t t = term;
        t = (t * sign) % MOD;
        t = (t * arr[i-j]) % MOD;
        arr[i] = (arr[i] + t) % MOD;

        term = (term * (k-j)) % MOD;

        // Деление в кольце по модулю MOD требует вычисления обратного элемента
        term = (term * reciprocal_mod(j+1, MOD)) % MOD;

        // (MOD - 1) — это просто -1 по модулю MOD
        sign = (sign == 1) ? MOD - 1 : 1;
      }
    }
}

БЛОГ НА HUSL

Помогите найти ошибку задача Гиперфиксные суммы

Ответы (1 шт):