fork download 
  1. #include <bits/stdc++.h>
  2. #define all(v) v.begin(), v.end()
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef vector<ll> poly;
  7.  
  8. ll pw(ll a, ll b, ll mod){
  9.     ll ret = 1;
  10.     while(b){
  11.         if(b & 1) ret = ret * a % mod;
  12.         b >>= 1; a = a * a % mod;
  13.     }
  14.     return ret;
  15. }
  16.  
  17. template<ll mod, ll w>
  18. class NTT{
  19. public:
  20.     void ntt(poly &f, bool inv = 0){
  21.         int n = f.size(), j = 0;
  22.         vector<ll> root(n >> 1);
  23.         for(int i=1; i<n; i++){
  24.             int bit = (n >> 1);
  25.             while(j >= bit){
  26.                 j -= bit; bit >>= 1;
  27.             }
  28.             j += bit;
  29.             if(i < j) swap(f[i], f[j]);
  30.         }
  31.         ll ang = pw(w, (mod - 1) / n, mod); if(inv) ang = pw(ang, mod - 2, mod);
  32.         root[0] = 1; for(int i=1; i<(n >> 1); i++) root[i] = root[i-1] * ang % mod;
  33.         for(int i=2; i<=n; i<<=1){
  34.             int step = n / i;
  35.             for(int j=0; j<n; j+=i){
  36.                 for(int k=0; k<(i >> 1); k++){
  37.                     ll u = f[j | k], v = f[j | k | i >> 1] * root[step * k] % mod;
  38.                     f[j | k] = (u + v) % mod;
  39.                     f[j | k | i >> 1] = (u - v) % mod;
  40.                     if(f[j | k | i >> 1] < 0) f[j | k | i >> 1] += mod;
  41.                 }
  42.             }
  43.         }
  44.         ll t = pw(n, mod - 2, mod);
  45.         if(inv) for(int i=0; i<n; i++) f[i] = f[i] * t % mod;
  46.     }
  47.     vector<ll> multiply(poly &_a, poly &_b){
  48.         vector<ll> a(all(_a)), b(all(_b));
  49.         int n = 2;
  50.         while(n < a.size() + b.size()) n <<= 1;
  51.         a.resize(n); b.resize(n);
  52.         ntt(a); ntt(b);
  53.         for(int i=0; i<n; i++) a[i] = a[i] * b[i] % mod;
  54.         ntt(a, 1);
  55.         return a;
  56.     }
  57. };
  58.  
  59. ll ext_gcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(a, b)
  60.   ll g = a; x = 1, y = 0;
  61.   if (b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
  62.   return g;
  63. }
  64.  
  65. const ll m1 = 2281701377, m2 = 2483027969, m3 = 998244353;
  66. NTT<m1, 3> ntt1;
  67. NTT<m2, 3> ntt2;
  68. NTT<m3, 3> ntt3;
  69.  
  70. ll f(const vector<ll> &a, ll mod){
  71.     int sz = a.size();
  72.     vector<ll> rmn(sz), lm(sz, 1);
  73.     ll ans = 0, M = 1;
  74.     vector<ll> m({m1, m2, m3}); //prime list
  75.  
  76.     for(int i=0; i<sz; i++){
  77.         ll k = a[i] - rmn[i]; k %= m[i];
  78.         if(k < 0) k += m[i];
  79.         ll x, y;
  80.         ext_gcd(lm[i], m[i], x, y);
  81.         k *= x; k %= m[i];
  82.         if(k < 0) k += m[i];
  83.         ans += k * M % mod;
  84.         ans %= mod;
  85.         for(int t=i+1; t<sz; t++){
  86.             rmn[t] += lm[t] * k;
  87.             rmn[t] %= m[t];
  88.             lm[t] *= m[i];
  89.             lm[t] %= m[t];
  90.         }
  91.         M *= m[i]; M %= mod;
  92.     }
  93.     return ans;
  94. }
  95.  
  96. poly multiply(poly &a, poly &b, ll mod){
  97.     poly a1(a), a2(a), a3(a);
  98.     poly b1(b), b2(b), b3(b);
  99.     poly res1 = ntt1.multiply(a1, b1);
  100.     poly res2 = ntt2.multiply(a2, b2);
  101.     poly res3 = ntt3.multiply(a3, b3);
  102.     poly ret(res1.size());
  103.     for(int i=0; i<res1.size(); i++){
  104.         ret[i] = f({res1[i], res2[i], res3[i]}, mod);
  105.     }
  106.     return ret;
  107. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments ()
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/wIJVrN
language:
C++14 (gcc 8.3)
created:
4 years 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!