error
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