Facebook
From long vu, 9 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 226
  1. /**
  2.  *    author:  longvu
  3.  *    created: 06/04/24 09:05:42
  4. **/
  5. #include<bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10. #define sz(x) ((int)x.size())
  11. #define all(x) (x).begin(), (x).end()
  12. const int INF = numeric_limits<int>::max();
  13. const int nax = (int)(401001);
  14. const int mod = 1e9 + 7;
  15.  
  16. template<class X, class Y>
  17. bool maximize(X& x, const Y y) {
  18.     if (y > x) {x = y; return true;}
  19.     return false;
  20. }
  21. template<class X, class Y>
  22. bool minimize(X& x, const Y y) {
  23.     if (y < x) {x = y; return true;}
  24.     return false;
  25. }
  26.  
  27. namespace NTT {
  28. const int MOD = 998244353;
  29. const int root_pw = 1 << 23;
  30.  
  31. int pw(int a, int n) {
  32.     if (n == 0) return 1;
  33.     int q = pw(a, n / 2);
  34.     if (n % 2 == 0) return q * 1ll * q % MOD;
  35.     return q * 1ll * q % MOD * a % MOD;
  36. }
  37.  
  38. const int root = pw(3, MOD / root_pw);
  39. const int root_1 = pw(root, MOD - 2);
  40.  
  41. void ntt(vector<int>& a, bool inv) {
  42.     int n = a.size(), j = 0;
  43.     vector<int> roots(n / 2);
  44.     for (int i = 1; i < n; i++) {
  45.         int bit = (n >> 1);
  46.         while (j >= bit) {
  47.             j -= bit;
  48.             bit >>= 1;
  49.         }
  50.         j += bit;
  51.         if (i < j) {
  52.             swap(a[i], a[j]);
  53.         }
  54.     }
  55.     int ang = inv ? root_1 : root;
  56.     for (int i = n; i < root_pw; i *= 2) {
  57.         ang = ang * 1ll * ang % MOD;
  58.     }
  59.     roots[0] = 1;
  60.     for (int i = 1; i < n / 2; i++) {
  61.         roots[i] = roots[i - 1] * 1ll * ang % MOD;
  62.     }
  63.     for (int i = 2; i <= n; i <<= 1) {
  64.         int step = n / i;
  65.         for (int j = 0; j < n; j += i) {
  66.             for (int k = 0; k < i / 2; k++) {
  67.                 int u = a[j + k], v = a[j + k + i / 2] * 1ll * roots[step * k] % MOD;
  68.                 a[j + k] = (u + v) % MOD;
  69.                 a[j + k + i / 2] = (u - v + MOD) % MOD;
  70.             }
  71.         }
  72.     }
  73.     if (inv) {
  74.         int n_inv = pw(n, MOD - 2);
  75.         for (int i = 0; i < n; i++) {
  76.             a[i] = a[i] * 1ll * n_inv % MOD;
  77.         }
  78.     }
  79. }
  80.  
  81. vector<int> multiply(const vector<int> &a, const vector<int> &b) {
  82.     vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  83.     int n = 1;
  84.     while (n < a.size() + b.size())
  85.         n <<= 1;
  86.     fa.resize(n);
  87.     fb.resize(n);
  88.  
  89.     ntt(fa, false);
  90.     ntt(fb, false);
  91.     for (int i = 0; i < n; i++)
  92.         fa[i] = (long long)fa[i] * fb[i] % MOD;
  93.     ntt(fa, true);
  94.  
  95.     return fa;
  96. }
  97. }
  98.  
  99. int block_sz = 901;
  100.  
  101. tuple<int, int, int> a[nax];
  102. int L[nax], R[nax], ans[nax];
  103. int32_t main() {
  104.     ios_base::sync_with_stdio(false);
  105.     cin.tie(0);
  106.     int n;
  107.     cin >> n;
  108.     for (int i = 0; i < n; ++i) {
  109.         cin >> get<0>(a[i]);
  110.         get<1>(a[i]) = i;
  111.         get<2>(a[i]) = 1;
  112.     }
  113.     for (int i = n; i < 2 * n; ++i) {
  114.         cin >> get<0>(a[i]);
  115.         get<1>(a[i]) = i - n;
  116.         get<2>(a[i]) = 2;
  117.     }
  118.     sort(a, a + 2 * n);
  119.     int n_block = 0;
  120.     for (int i = 0; i < 2 * n; i += block_sz) {
  121.         L[++n_block] = i;
  122.         R[n_block] = min(i + block_sz - 1, 2 * n - 1);
  123.     }
  124.     // for (int i = 0; i < 2 * n; ++i) {
  125.     //     cout << get<0>(a[i]) << " ";
  126.     // }
  127.     // cout << '\n';
  128.     for (int i = 1; i <= n_block; ++i) {
  129.         for (int j = L[i]; j <= R[i]; ++j) {
  130.             if (get<2>(a[j]) == 1) {
  131.                 for (int e = L[i]; e < j; ++e) {
  132.                     if (get<2>(a[e]) == 2) {
  133.                         ans[(get<1>(a[e]) - get<1>(a[j]) + n) % n]++;
  134.                     }
  135.                 }
  136.             }
  137.         }
  138.     }
  139.     vector<int> f, g(n + 1, 0);
  140.     for (int i = 1; i <= n_block; ++i) {
  141.         // cout << L[i] << " " << R[i] << '\n';
  142.         f.clear();
  143.         f.resize(n + 1, 0);
  144.         fill(all(f), 0);
  145.         for (int j = L[i]; j <= R[i]; ++j) {
  146.             if (get<2>(a[j]) == 1) {
  147.                 f[n - get<1>(a[j])]++;
  148.             }
  149.         }
  150.         f = NTT::multiply(f, g);
  151.         for (int j = - n; j <= n; ++j) {
  152.             ans[(j + n) % n] += f[n + j];
  153.         }
  154.         for (int j = L[i]; j <= R[i]; ++j) {
  155.             if (get<2>(a[j]) == 2) {
  156.                 g[get<1>(a[j])]++;
  157.             }
  158.         }
  159.     }
  160.     // for (int i = 0; i < n; ++i) {
  161.     //     cout << ans[i] << " ";
  162.     // }
  163.     // cout << '\n';
  164.     vector<int> anstr;
  165.     for (int i = 0; i < n; ++i) {
  166.         if (ans[i] >= n / 2 + 1) {
  167.             anstr.push_back(i);
  168.         }
  169.     }
  170.     cout << sz(anstr) << '\n';
  171.     for (auto z : anstr) {
  172.         cout << z << " ";
  173.     }
  174.     cout << '\n';
  175.     return 0;
  176. }