error

 avatar
meda
c_cpp
a month ago
2.6 kB
1
Indexable
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
void printff(vector<T>& v) {
  for (auto k : v) cout << k << " ";
  cout << endl;
}

using matrix = vector<vector<ll>>;
const ll MOD = 998244353;
matrix identity(int n){
    matrix iden(n, vector<ll>(n));
    for (int i = 0; i < n; i++)
        iden[i][i] = 1;
    return iden;
}
matrix matrix_mult(const matrix &a, const matrix &b){
    int n = (int) a.size();
    int m = (int) b[0].size();
    matrix res(n, vector<ll>(m));
    int r = (int) a[0].size();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < r; k++)
                res[i][j] = (res[i][j] % MOD + (a[i][k] % MOD * b[k][j] % MOD) % MOD) % MOD;
    return res;
}
matrix matrix_expo(const matrix &a, ll p){
    matrix iden = identity((int)a[0].size());
    matrix res = a;
    while (p){
        if (p & 1)
            iden = matrix_mult(iden, res);
        res = matrix_mult(res, res);
        p >>= 1;
    }
    return iden;
}
ll mult(ll a, ll b) { return (a * b) % MOD; }
ll add(ll a, ll b) { return (a + b) % MOD; }
ll sub(ll a, ll b) { return (a - b + MOD) % MOD; }

// a0 a1 a2 a3
// a1 + a2 + a3 - a0
// 2 a1 + 2 a2 + 2 a3 + 4 a0
// 6 a1 + 6 a2 + 6 a3 + 2 a0
// 14 a1 + 14 a2 + 14 a3 + 16 a0
//                           (n - 3  n - 1)
// (dp[1, 2, n - 1], dp[0]) *(  1      -1 ) = (dp[1, 2, n - 1], dp[0])

void SOLVE() {
  ll n, k; cin >> n >> k;
  vector<ll> a(n);
  ll sum = 0;
  for(auto & val : a) cin >> val, sum = add(sum, val);
  if(k == 0){
    for(auto & val : a) cout << val << endl;
    return;
  }

  matrix start(1, vector<ll>(2));
  start[0][0] = 1, start[0][1] = MOD - 1;
  matrix transition(2, vector<ll>(2));
  transition[0][0] = (n - 3 + MOD) % MOD;
  transition[0][1] = n - 1;
  transition[1][0] = 1;
  transition[1][1] = MOD - 1;
  
  matrix result = matrix_mult(start, matrix_expo(transition, k - 1));
  
  for(int i = 0; i < n; i++){
    ll all = sub(sum, a[i]);
    cout << add(mult(all, result[0][0]), mult(a[i], result[0][1])) << endl;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);
  int o_o = 1; //cin >> o_o;
  while(o_o --) SOLVE();
  return 0;
}
Editor is loading...
Leave a Comment