fork download
copy 
  1. #ifdef LOCAL
  2. #include "algo/dbg.hpp"
  3. #else
  4. #include "bits/stdc++.h"
  5. #define dbg(...)
  6. #endif
  7. using namespace std;
  8.  
  9. #define endl '\n'
  10. // #define int long long
  11. #define sz(x) (int) x.size()
  12. #define pb push_back
  13. // #define all(v) v.begin(), v.end()
  14. #define rep(i,a,b) for (int i = (a); i < (b); ++i)
  15. #define rrep(i,a,b) for (int i = (a); i >= (b); --i)
  16.  
  17. typedef long long ll;
  18. typedef pair<int, int> pii;
  19. typedef vector<int> vi;
  20. template<class T> bool ckmin(T& a, T b){ return b < a ? a = b, 1 : 0; }
  21. template<class T> bool ckmax(T& a, T b){ return b > a ? a = b, 1 : 0; }
  22. template<class T> istream& operator>>(istream&i,vector<T>&v){for(T&x:v)i>>x;return i;}\
  23.  
  24. #include<bits/stdc++.h>
  25. using namespace std;
  26.  
  27. //typedef complex<double> CD;
  28. struct CD {
  29.     double x, y;
  30.     CD(double x=0, double y=0) :x(x), y(y) {}
  31.     CD operator+(const CD& o) { return {x+o.x, y+o.y};}
  32.     CD operator-(const CD& o) { return {x-o.x, y-o.y};}
  33.     CD operator*(const CD& o) { return {x*o.x-y*o.y, x*o.y+o.x*y};}
  34.     void operator /= (double d) { x/=d; y/=d;}
  35.     double real() {return x;}
  36.     double imag() {return y;}
  37. };
  38. CD conj(const CD &c) {return CD(c.x, -c.y);}
  39.  
  40. typedef long long LL;
  41. const double PI = acos(-1.0L);
  42.  
  43. namespace FFT {
  44.     int N;
  45.     vector<int> perm;
  46.     vector<CD> wp[2];
  47.  
  48.     void precalculate(int n) {
  49.         assert((n & (n-1)) == 0);
  50.         N = n;
  51.         perm = vector<int> (N, 0);
  52.         for (int k=1; k<N; k<<=1) {
  53.             for (int i=0; i<k; i++) {
  54.                 perm[i] <<= 1;
  55.                 perm[i+k] = 1 + perm[i];
  56.             }
  57.         }
  58.  
  59.         wp[0] = wp[1] = vector<CD>(N);
  60.         for (int i=0; i<N; i++) {
  61.             wp[0][i] = CD( cos(2*PI*i/N),  sin(2*PI*i/N) );
  62.             wp[1][i] = CD( cos(2*PI*i/N), -sin(2*PI*i/N) );
  63.         }
  64.     }
  65.  
  66.     void fft(vector<CD> &v, bool invert = false) {
  67.         if (v.size() != perm.size())    precalculate(v.size());
  68.  
  69.         for (int i=0; i<N; i++)
  70.             if (i < perm[i])
  71.                 swap(v[i], v[perm[i]]);
  72.  
  73.         for (int len = 2; len <= N; len *= 2) {
  74.             for (int i=0, d = N/len; i<N; i+=len) {
  75.                 for (int j=0, idx=0; j<len/2; j++, idx += d) {
  76.                     CD x = v[i+j];
  77.                     CD y = wp[invert][idx]*v[i+j+len/2];
  78.                     v[i+j] = x+y;
  79.                     v[i+j+len/2] = x-y;
  80.                 }
  81.             }
  82.         }
  83.  
  84.         if (invert) {
  85.             for (int i=0; i<N; i++) v[i]/=N;
  86.         }
  87.     }
  88.  
  89.      void pairfft(vector<CD> &a, vector<CD> &b, bool invert = false) {
  90.         int N = a.size();
  91.         vector<CD> p(N);
  92.         for (int i=0; i<N; i++) p[i] = a[i] + b[i] * CD(0, 1);
  93.         fft(p, invert);
  94.         p.push_back(p[0]);
  95.  
  96.         for (int i=0; i<N; i++) {
  97.             if (invert) {
  98.                 a[i] = CD(p[i].real(), 0);
  99.                 b[i] = CD(p[i].imag(), 0);
  100.             }
  101.             else {
  102.                 a[i] = (p[i]+conj(p[N-i]))*CD(0.5, 0);
  103.                 b[i] = (p[i]-conj(p[N-i]))*CD(0, -0.5);
  104.             }
  105.         }
  106.     }
  107.  
  108.     vector<LL> multiply(const vector<LL> &a, const vector<LL> &b) {
  109.         int n = 1;
  110.         while (n < a.size()+ b.size())  n<<=1;
  111.  
  112.         vector<CD> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  113.         fa.resize(n); fb.resize(n);
  114.  
  115. //        fft(fa); fft(fb);
  116.         pairfft(fa, fb);
  117.         for (int i=0; i<n; i++) fa[i] = fa[i] * fb[i];
  118.         fft(fa, true);
  119.  
  120.         vector<LL> ans(n);
  121.         for (int i=0; i<n; i++)     ans[i] = round(fa[i].real());
  122.         return ans;
  123.     }
  124.  
  125.     const int M = 7340033, B = sqrt(M)+1;
  126.     vector<LL> anyMod(const vector<LL> &a, const vector<LL> &b) {
  127.         int n = 1;
  128.         while (n < a.size()+ b.size())  n<<=1;
  129.         vector<CD> al(n), ar(n), bl(n), br(n);
  130.  
  131.         for (int i=0; i<a.size(); i++)  al[i] = a[i]%M/B, ar[i] = a[i]%M%B;
  132.         for (int i=0; i<b.size(); i++)  bl[i] = b[i]%M/B, br[i] = b[i]%M%B;
  133.  
  134.         pairfft(al, ar); pairfft(bl, br);
  135. //        fft(al); fft(ar); fft(bl); fft(br);
  136.  
  137.         for (int i=0; i<n; i++) {
  138.             CD ll = (al[i] * bl[i]), lr = (al[i] * br[i]);
  139.             CD rl = (ar[i] * bl[i]), rr = (ar[i] * br[i]);
  140.             al[i] = ll; ar[i] = lr;
  141.             bl[i] = rl; br[i] = rr;
  142.         }
  143.  
  144.         pairfft(al, ar, true); pairfft(bl, br, true);
  145. //        fft(al, true); fft(ar, true); fft(bl, true); fft(br, true);
  146.  
  147.         vector<LL> ans(n);
  148.         for (int i=0; i<n; i++) {
  149.             LL right = round(br[i].real()), left = round(al[i].real());;
  150.             LL mid = round(round(bl[i].real()) + round(ar[i].real()));
  151.             ans[i] = ((left%M)*B*B + (mid%M)*B + right)%M;
  152.         }
  153.         return ans;
  154.     }
  155. }
  156. template<int MOD, int RT> struct Mint {
  157.     static const int mod = MOD;
  158.     static constexpr Mint rt() { return RT; } // primitive root for FFT
  159.     int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
  160.     Mint():v(0) {}
  161.     Mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
  162.  
  163.     bool operator==(const Mint& o) const { return v == o.v; }
  164.     friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
  165.     friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
  166.  
  167.     Mint& operator+=(const Mint& o) { if ((v += o.v) >= MOD) v -= MOD; return *this; }
  168.     Mint& operator-=(const Mint& o) { if ((v -= o.v) < 0) v += MOD; return *this; }
  169.     Mint& operator*=(const Mint& o) { v = int((ll)v*o.v%MOD); return *this; }
  170.     Mint& operator/=(const Mint& o) { return (*this) *= inv(o); }
  171.     friend Mint pow(Mint a, ll p) {
  172.         Mint ans = 1; assert(p >= 0);
  173.         for (; p; p /= 2, a *= a) if (p&1) ans *= a; return ans; }
  174.     friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a,MOD-2); }
  175.  
  176.     Mint operator-() const { return Mint(-v); }
  177.     Mint& operator++() { return *this += 1; }
  178.     Mint& operator--() { return *this -= 1; }
  179.     friend Mint operator+(Mint a, const Mint& b) { return a += b; }
  180.     friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
  181.     friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
  182.     friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
  183.     friend ostream& operator<<(ostream &out, const Mint &m) {return out << m.v;}
  184.     friend istream& operator>>(istream &in, Mint &m) {long long x; in >> x; m = Mint(x); return in;}
  185. };
  186. const int MOD = 7340033; // change accordingly
  187. using mint = Mint<MOD,5>;
  188. vector<mint> fact(1, 1);
  189. vector<mint> inv_fact(1, 1);
  190.  
  191. mint choose(int n, int k) {
  192.   if (k < 0 || k > n) {
  193.     return 0;
  194.   }
  195.   while ((int) fact.size() < n + 1) {
  196.     fact.push_back(fact.back() * (int) fact.size());
  197.     inv_fact.push_back(1 / fact.back());
  198.   }
  199.   return fact[n] * inv_fact[k] * inv_fact[n - k];
  200. }
  201.  
  202. void solve(int tc = 0) {
  203.     int n; cin >> n;
  204.     vi cnt(4, 0);
  205.     rep(i, 0, n){
  206.         int x, y; cin >> x >> y;
  207.         if(x > 0 and y > 0) cnt[0]++;
  208.         if(x > 0 and y < 0) cnt[3]++;
  209.         if(x < 0 and y > 0) cnt[1]++;
  210.         if(x < 0 and y < 0) cnt[2]++;
  211.     }
  212.     int a = min(cnt[0], cnt[2]);
  213.     int b = min(cnt[1], cnt[3]);
  214.  
  215.     vector<ll> polya(a+1);
  216.     vector<ll> polyb(b+1);
  217.     for(int i = 0; i <= a; i++){
  218.         polya[i] = 1LL*int(choose(cnt[0], i))*1LL*int(choose(cnt[2], i));
  219.     }
  220.     for(int i = 0; i <= b; i++){
  221.         polyb[i] = 1LL*int(choose(cnt[1], i))*1LL*int(choose(cnt[3], i));
  222.     }
  223.     // auto it = convMod<7340033>(polya, polyb);
  224.     vector<ll> it = FFT::anyMod(polya, polyb);
  225.  
  226.     cout << "Case " << tc+1 << ":\n";
  227.     while(it.size() <= n) it.pb(0LL);
  228.  
  229.     for(int i = 1; i <= n; i++){
  230.         if(i&1){
  231.             cout << 0;
  232.         }else{
  233.             cout << it[i/2];
  234.         }
  235.         cout << " \n"[i == n];
  236.     } 
  237.  
  238.  
  239. }
  240.  
  241. signed main() {
  242. ios_base::sync_with_stdio(false);
  243. cin.tie(NULL); cout.tie(NULL);
  244.  
  245. int tc = 1;
  246. cin >> tc;
  247. for(int t = 0; t < tc; t++) solve(t);
  248. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1:
https://ideone.com/4j9x8t
language:
C++14 (gcc 8.3)
created:
8 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!