fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 998244353;
  8.  
  9. // Function to compute the lowest set bit
  10. int lowbit(int x) {
  11.     return x & -x;
  12. }
  13.  
  14. // Function to build a Fenwick Tree from a given array `a`
  15. vector<int> f(const vector<int>& a, int mod) {
  16.     int n = a.size();
  17.     vector<int> s(n, 0);
  18.     for (int k = 1; k <= n; ++k) {
  19.         int start = k - lowbit(k);
  20.         for (int i = start; i < k; ++i) {
  21.             s[k - 1] = (s[k - 1] + a[i]) % mod;
  22.         }
  23.     }
  24.     return s;
  25. }
  26.  
  27. // Function to inverse the Fenwick Tree to reconstruct array `a`
  28. vector<int> inverse_f(const vector<int>& s, int mod) {
  29.     int n = s.size();
  30.     vector<int> a(n, 0);
  31.     a[0] = s[0];
  32.     for (int k = 1; k < n; ++k) {
  33.         int start = k - lowbit(k);
  34.         a[k] = s[k];
  35.         for (int i = start; i < k; ++i) {
  36.             a[k] = (a[k] - a[i] + mod) % mod;
  37.         }
  38.     }
  39.     return a;
  40. }
  41.  
  42. // Function to find the original array `a` from `fk(a) = b`
  43. vector<int> get_original_array(int n, int k, const vector<int>& b) {
  44.     vector<int> current = b;
  45.     if (k > 1) {
  46.         for (int i = 1; i < k; ++i) {
  47.             current = inverse_f(current, MOD);
  48.         }
  49.     }
  50.     return current;
  51. }
  52.  
  53. int main() {
  54.     int t;
  55.     cin >> t;
  56.  
  57.     while (t--) {
  58.         int n, k;
  59.         cin >> n >> k;
  60.  
  61.         vector<int> b(n);
  62.         for (int i = 0; i < n; i++) {
  63.             cin >> b[i];
  64.         }
  65.  
  66.         vector<int> a = get_original_array(n, k, b);
  67.  
  68.         for (int i = 0; i < n; i++) {
  69.             cout << a[i] << " ";
  70.         }
  71.         cout << "\n";
  72.     }
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16
stdout
copy 
1 2 1 4 1 2 1 8 
1 3 998244352 18 998244337 32
https://ideone.com/SCzJHm
language:
C++14 (gcc 8.3)
created:
19 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!