fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e6 + 100, mod = 998244353;
  4. int T, n, k;
  5. int a[N], inv[N];
  6.  
  7. inline int lowbit(int x) {return x & -x;}
  8.  
  9. int main() {
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(0); cout.tie(0);
  12.     inv[0] = inv[1] = 1;
  13.     for(int i = 2; i <= N - 1; i++) inv[i] = (mod - mod / i) * inv[mod % i];
  14.     for(cin >> T; T; --T) {
  15.         cin >> n >> k;
  16.         for(int i = 1; i <= n; i++) cin >> a[i];
  17.         for(int i = 1; i <= n; i++){
  18.             int mul = 1;
  19.             for(int u = i + lowbit(i), d = 1; u <= n; u += lowbit(u), ++d) {
  20.                 mul *= (d + k - 1) * inv[d];
  21.                 a[u] -= mul * a[i];
  22.             }
  23.         }
  24.         for(int i = 1; i <= n; i++){
  25.         	cout << a[i] << " \n"[i == n];
  26.         } 
  27.     }
  28.     return 0;
  29. }
Success #stdin #stdout 0.02s 7928KB
comments (?)
stdin 
2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16
stdout 
1 1 1 -998244352 1 1 1 -1090519048
1 2 3 1300234241 5 6
https://ideone.com/6EEvGA
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!