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. typedef complex<double> C;
  25. typedef vector<double> vd;
  26. void fft(vector<C>& a) {
  27. 	int n = sz(a), L = 31 - __builtin_clz(n);
  28. 	static vector<complex<long double>> R(2, 1);
  29. 	static vector<C> rt(2, 1);  // (^ 10% faster if double)
  30. 	for (static int k = 2; k < n; k *= 2) {
  31. 		R.resize(n); rt.resize(n);
  32. 		auto x = polar(1.0L, acos(-1.0L) / k);
  33. 		rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
  34. 	}
  35. 	vi rev(n);
  36. 	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
  37. 	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
  38. 	for (int k = 1; k < n; k *= 2)
  39. 		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
  40. 			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
  41. 			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
  42. 			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
  43. 			a[i + j + k] = a[i + j] - z;
  44. 			a[i + j] += z;
  45. 		}
  46. }
  47.  
  48. vd conv(const vd& a, const vd& b) {
  49. 	if (a.empty() || b.empty()) return {};
  50. 	vd res(sz(a) + sz(b) - 1);
  51. 	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
  52. 	vector<C> in(n), out(n);
  53. 	copy(all(a), begin(in));
  54. 	rep(i,0,sz(b)) in[i].imag(b[i]);
  55. 	fft(in);
  56. 	for (C& x : in) x *= x;
  57. 	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
  58. 	fft(out);
  59. 	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
  60. 	return res;
  61. }
  62. typedef vector<ll> vl;
  63. template<int M> vl convMod(const vl &a, const vl &b) {
  64. 	if (a.empty() || b.empty()) return {};
  65. 	vl res(sz(a) + sz(b) - 1);
  66. 	int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(M));
  67. 	vector<C> L(n), R(n), outs(n), outl(n);
  68. 	rep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut);
  69. 	rep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut);
  70. 	fft(L), fft(R);
  71. 	rep(i,0,n) {
  72. 		int j = -i & (n - 1);
  73. 		outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
  74. 		outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / C(0, 1); // / 1i
  75. 	}
  76. 	fft(outl), fft(outs);
  77. 	rep(i,0,sz(res)) {
  78. 		ll av = ll(real(outl[i])+.5), cv = ll(imag(outs[i])+.5);
  79. 		ll bv = ll(imag(outl[i])+.5) + ll(real(outs[i])+.5);
  80. 		res[i] = ((av % M * cut + bv) % M * cut + cv) % M;
  81. 	}
  82. 	return res;
  83. }
  84. template<int MOD, int RT> struct Mint {
  85.     static const int mod = MOD;
  86.     static constexpr Mint rt() { return RT; } // primitive root for FFT
  87.     int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
  88.     Mint():v(0) {}
  89.     Mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
  90.  
  91.     bool operator==(const Mint& o) const { return v == o.v; }
  92.     friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
  93.     friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
  94.  
  95.     Mint& operator+=(const Mint& o) { if ((v += o.v) >= MOD) v -= MOD; return *this; }
  96.     Mint& operator-=(const Mint& o) { if ((v -= o.v) < 0) v += MOD; return *this; }
  97.     Mint& operator*=(const Mint& o) { v = int((ll)v*o.v%MOD); return *this; }
  98.     Mint& operator/=(const Mint& o) { return (*this) *= inv(o); }
  99.     friend Mint pow(Mint a, ll p) {
  100.         Mint ans = 1; assert(p >= 0);
  101.         for (; p; p /= 2, a *= a) if (p&1) ans *= a; return ans; }
  102.     friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a,MOD-2); }
  103.  
  104.     Mint operator-() const { return Mint(-v); }
  105.     Mint& operator++() { return *this += 1; }
  106.     Mint& operator--() { return *this -= 1; }
  107.     friend Mint operator+(Mint a, const Mint& b) { return a += b; }
  108.     friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
  109.     friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
  110.     friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
  111.     friend ostream& operator<<(ostream &out, const Mint &m) {return out << m.v;}
  112.     friend istream& operator>>(istream &in, Mint &m) {long long x; in >> x; m = Mint(x); return in;}
  113. };
  114. const int MOD = 7340033; // change accordingly
  115. using mint = Mint<MOD,5>;
  116. vector<mint> fact(1, 1);
  117. vector<mint> inv_fact(1, 1);
  118.  
  119. mint choose(int n, int k) {
  120.   if (k < 0 || k > n) {
  121.     return 0;
  122.   }
  123.   while ((int) fact.size() < n + 1) {
  124.     fact.push_back(fact.back() * (int) fact.size());
  125.     inv_fact.push_back(1 / fact.back());
  126.   }
  127.   return fact[n] * inv_fact[k] * inv_fact[n - k];
  128. }
  129.  
  130. void solve(int tc = 0) {
  131.     int n; cin >> n;
  132.     vi cnt(4, 0);
  133.     rep(i, 0, n){
  134.         int x, y; cin >> x >> y;
  135.         if(x > 0 and y > 0) cnt[0]++;
  136.         if(x > 0 and y < 0) cnt[3]++;
  137.         if(x < 0 and y > 0) cnt[1]++;
  138.         if(x < 0 and y < 0) cnt[2]++;
  139.     }
  140.     int a = min(cnt[0], cnt[2]);
  141.     int b = min(cnt[1], cnt[3]);
  142.  
  143.     vl polya(a+1);
  144.     vl polyb(b+1);
  145.     for(int i = 0; i <= a; i++){
  146.         polya[i] = 1LL*int(choose(cnt[0], i))*1LL*int(choose(cnt[2], i));
  147.     }
  148.     for(int i = 0; i <= b; i++){
  149.         polyb[i] = 1LL*int(choose(cnt[1], i))*1LL*int(choose(cnt[3], i));
  150.     }
  151.     auto it = convMod<7340033>(polya, polyb);
  152.     dbg(it.size());
  153.  
  154.     cout << "Case " << tc+1 << ": \n";
  155.     while(it.size() <= n) it.pb(0);
  156.  
  157.     for(int i = 1; i <= n; i++){
  158.         if(i&1){
  159.             cout << 0;
  160.         }else{
  161.             cout << it[i/2];
  162.         }
  163.         cout << " \n"[i == n];
  164.     }
  165.  
  166. }
  167.  
  168. signed main() {
  169. ios_base::sync_with_stdio(false);
  170. cin.tie(NULL); cout.tie(NULL);
  171.  
  172. int tc = 1;
  173. cin >> tc;
  174. for(int t = 0; t < tc; t++) solve(t);
  175. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1:
https://ideone.com/SfDKU1
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!