fork download 
  1. #include <vector> 
  2. #include <cmath> 
  3. using namespace std; 
  4.  
  5. static const unsigned MODVAL = 1000000007; 
  6. struct mint 
  7. { 
  8.   unsigned val; 
  9.   mint():val(0){} 
  10.   mint(int      x):val(x%MODVAL) {} 
  11.   mint(unsigned x):val(x%MODVAL) {} 
  12. }; 
  13. mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 
  14.  
  15. template<typename T> 
  16. struct DP3 
  17. { 
  18.   int N1, N2, N3; 
  19.   vector<T> data; 
  20.   DP3(int N1, int N2, int N3, const T& t = T()) 
  21.     : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<28)); } 
  22.   T& operator()(int i1, int i2, int i3) 
  23.     { return data[ ((i1*N2)+i2)*N3+i3 ]; } 
  24.   void swap(DP3& rhs) 
  25.     { data.swap(rhs.data); } 
  26. }; 
  27.  
  28. class AlienAndSetDiv1 { public: 
  29.   int getNumber(int N, int K) 
  30.   { 
  31.     const int MASK = (1<<K)-1; 
  32.     DP3<mint> dp(N+1, N+1, 1<<K); // |A|, |B|, last K 
  33.  
  34.     dp(0,0,0) = 1; 
  35.     for(int a_plus_b=0; a_plus_b<2*N; ++a_plus_b) 
  36.     for(int a=0; a<=N; ++a) { 
  37.       int b = a_plus_b - a; 
  38.       if(0<=b && b<=N) { 
  39.         for(int m=0; m<(1<<K); ++m) { 
  40.           int me = a+b+1; 
  41.           if(a<N) { 
  42.             int you = calc_Bs_elem(a, b, m); 
  43.             if(abs(you-me) >= K) 
  44.               dp(a+1, b, MASK&((m<<1)|0)) += dp(a,b,m); 
  45.           } 
  46.           if(b<N) { 
  47.             int you = calc_Bs_elem(b, a, m^MASK); 
  48.             if(abs(you-me) >= K) 
  49.               dp(a, b+1, MASK&((m<<1)|1)) += dp(a,b,m); 
  50.           } 
  51.         } 
  52.       } 
  53.     } 
  54.  
  55.     mint sum = 0; 
  56.     for(int m=0; m<(1<<K); ++m) 
  57.       sum += dp(N, N, m); 
  58.     return sum.val; 
  59.   } 
  60.  
  61.   int calc_Bs_elem(int a, int b, int m) 
  62.   { 
  63.     int next_idx = b-1; 
  64.     int v = a+b; 
  65.     for(int i=0; (1<<i)<=m; ++i) { 
  66.       if((1<<i)&m) { 
  67.         if(next_idx == a) 
  68.           return v; 
  69.         next_idx--; 
  70.       } 
  71.       --v; 
  72.     } 
  73.     return -99999; 
  74.   } 
  75. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In instantiation of ‘DP3<T>::DP3(int, int, int, const T&) [with T = mint]’:
prog.cpp:32:32:   required from here
prog.cpp:21:87: error: ‘assert’ was not declared in this scope
     : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<28)); } 
                                                                                       ^
stdout 
Standard output is empty
https://ideone.com/RvNwYm
language:
C++14 (gcc 8.3)
created:
11 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!