fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MD (1000000007U)
  5. void *wmem;
  6. char memarr[96000000];
  7. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  8.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  9.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  10.   (*arr)=(T*)(*mem);
  11.   (*mem)=((*arr)+x);
  12. }
  13. struct Modint{
  14.   unsigned val;
  15.   Modint(){
  16.     val=0;
  17.   }
  18.   Modint(int a){
  19.     val = ord(a);
  20.   }
  21.   Modint(unsigned a){
  22.     val = ord(a);
  23.   }
  24.   Modint(long long a){
  25.     val = ord(a);
  26.   }
  27.   Modint(unsigned long long a){
  28.     val = ord(a);
  29.   }
  30.   inline unsigned ord(unsigned a){
  31.     return a%MD;
  32.   }
  33.   inline unsigned ord(int a){
  34.     a %= MD;
  35.     if(a < 0){
  36.       a += MD;
  37.     }
  38.     return a;
  39.   }
  40.   inline unsigned ord(unsigned long long a){
  41.     return a%MD;
  42.   }
  43.   inline unsigned ord(long long a){
  44.     a %= MD;
  45.     if(a < 0){
  46.       a += MD;
  47.     }
  48.     return a;
  49.   }
  50.   inline unsigned get(){
  51.     return val;
  52.   }
  53.   inline Modint &operator+=(Modint a){
  54.     val += a.val;
  55.     if(val >= MD){
  56.       val -= MD;
  57.     }
  58.     return *this;
  59.   }
  60.   inline Modint &operator-=(Modint a){
  61.     if(val < a.val){
  62.       val = val + MD - a.val;
  63.     }
  64.     else{
  65.       val -= a.val;
  66.     }
  67.     return *this;
  68.   }
  69.   inline Modint &operator*=(Modint a){
  70.     val = ((unsigned long long)val*a.val)%MD;
  71.     return *this;
  72.   }
  73.   inline Modint &operator/=(Modint a){
  74.     return *this *= a.inverse();
  75.   }
  76.   inline Modint operator+(Modint a){
  77.     return Modint(*this)+=a;
  78.   }
  79.   inline Modint operator-(Modint a){
  80.     return Modint(*this)-=a;
  81.   }
  82.   inline Modint operator*(Modint a){
  83.     return Modint(*this)*=a;
  84.   }
  85.   inline Modint operator/(Modint a){
  86.     return Modint(*this)/=a;
  87.   }
  88.   inline Modint operator+(int a){
  89.     return Modint(*this)+=Modint(a);
  90.   }
  91.   inline Modint operator-(int a){
  92.     return Modint(*this)-=Modint(a);
  93.   }
  94.   inline Modint operator*(int a){
  95.     return Modint(*this)*=Modint(a);
  96.   }
  97.   inline Modint operator/(int a){
  98.     return Modint(*this)/=Modint(a);
  99.   }
  100.   inline Modint operator+(long long a){
  101.     return Modint(*this)+=Modint(a);
  102.   }
  103.   inline Modint operator-(long long a){
  104.     return Modint(*this)-=Modint(a);
  105.   }
  106.   inline Modint operator*(long long a){
  107.     return Modint(*this)*=Modint(a);
  108.   }
  109.   inline Modint operator/(long long a){
  110.     return Modint(*this)/=Modint(a);
  111.   }
  112.   inline Modint operator-(void){
  113.     Modint res;
  114.     if(val){
  115.       res.val=MD-val;
  116.     }
  117.     else{
  118.       res.val=0;
  119.     }
  120.     return res;
  121.   }
  122.   inline operator bool(void){
  123.     return val!=0;
  124.   }
  125.   inline operator int(void){
  126.     return get();
  127.   }
  128.   inline operator long long(void){
  129.     return get();
  130.   }
  131.   inline Modint inverse(){
  132.     int a = val;
  133.     int b = MD;
  134.     int u = 1;
  135.     int v = 0;
  136.     int t;
  137.     Modint res;
  138.     while(b){
  139.       t = a / b;
  140.       a -= t * b;
  141.       swap(a, b);
  142.       u -= t * v;
  143.       swap(u, v);
  144.     }
  145.     if(u < 0){
  146.       u += MD;
  147.     }
  148.     res.val = u;
  149.     return res;
  150.   }
  151.   inline Modint pw(unsigned long long b){
  152.     Modint a(*this);
  153.     Modint res;
  154.     res.val = 1;
  155.     while(b){
  156.       if(b&1){
  157.         res *= a;
  158.       }
  159.       b >>= 1;
  160.       a *= a;
  161.     }
  162.     return res;
  163.   }
  164.   inline bool operator==(int a){
  165.     return ord(a)==val;
  166.   }
  167.   inline bool operator!=(int a){
  168.     return ord(a)!=val;
  169.   }
  170. }
  171. ;
  172. inline Modint operator+(int a, Modint b){
  173.   return Modint(a)+=b;
  174. }
  175. inline Modint operator-(int a, Modint b){
  176.   return Modint(a)-=b;
  177. }
  178. inline Modint operator*(int a, Modint b){
  179.   return Modint(a)*=b;
  180. }
  181. inline Modint operator/(int a, Modint b){
  182.   return Modint(a)/=b;
  183. }
  184. inline Modint operator+(long long a, Modint b){
  185.   return Modint(a)+=b;
  186. }
  187. inline Modint operator-(long long a, Modint b){
  188.   return Modint(a)-=b;
  189. }
  190. inline Modint operator*(long long a, Modint b){
  191.   return Modint(a)*=b;
  192. }
  193. inline Modint operator/(long long a, Modint b){
  194.   return Modint(a)/=b;
  195. }
  196. template<class S, class T> inline S chmax(S &a, T b){
  197.   if(a<b){
  198.     a=b;
  199.   }
  200.   return a;
  201. }
  202. template<class T> struct Comb{
  203.   int mem_fact;
  204.   T *factri;
  205.   T *ifactri;
  206.   Comb(){
  207.     mem_fact = 0;
  208.   }
  209.   inline void expand_fact(int k){
  210.     if(k <= mem_fact){
  211.       return;
  212.     }
  213.     chmax(k, 2* mem_fact);
  214.     if(mem_fact == 0){
  215.       int i;
  216.       factri = (T*)malloc(k * sizeof(T));
  217.       ifactri = (T*)malloc(k * sizeof(T));
  218.       factri[0] = 1;
  219.       for(i=(1);i<(k);i++){
  220.         factri[i] = i * factri[i-1];
  221.       }
  222.       ifactri[k-1] = 1 / factri[k-1];
  223.       for(i=(k-1)-1;i>=(0);i--){
  224.         ifactri[i] = (i+1) * ifactri[i+1];
  225.       }
  226.     }
  227.     else{
  228.       int i;
  229.       factri = (T*)realloc(factri, k * sizeof(T));
  230.       ifactri = (T*)realloc(ifactri, k * sizeof(T));
  231.       for(i=(mem_fact);i<(k);i++){
  232.         factri[i] = i * factri[i-1];
  233.       }
  234.       ifactri[k-1] = 1 / factri[k-1];
  235.       for(i=(k-1)-1;i>=(mem_fact);i--){
  236.         ifactri[i] = (i+1) * ifactri[i+1];
  237.       }
  238.     }
  239.     mem_fact = k;
  240.   }
  241.   inline T fac(int k){
  242.     if(mem_fact < k+1){
  243.       expand_fact(k+1);
  244.     }
  245.     return factri[k];
  246.   }
  247.   inline T ifac(int k){
  248.     if(mem_fact < k+1){
  249.       expand_fact(k+1);
  250.     }
  251.     return ifactri[k];
  252.   }
  253.   inline T C(int a, int b){
  254.     if(b < 0 || b > a){
  255.       return 0;
  256.     }
  257.     if(mem_fact < a+1){
  258.       expand_fact(a+1);
  259.     }
  260.     return factri[a] * ifactri[b] * ifactri[a-b];
  261.   }
  262.   inline T P(int a, int b){
  263.     if(b < 0 || b > a){
  264.       return 0;
  265.     }
  266.     if(mem_fact < a+1){
  267.       expand_fact(a+1);
  268.     }
  269.     return factri[a] * ifactri[a-b];
  270.   }
  271.   inline T H(int a, int b){
  272.     if(a==0 && b==0){
  273.       return 1;
  274.     }
  275.     if(a <= 0 || b < 0){
  276.       return 0;
  277.     }
  278.     if(mem_fact < a+b){
  279.       expand_fact(a+b);
  280.     }
  281.     return C(a+b-1, b);
  282.   }
  283.   inline T Multinomial(int sz, int a[]){
  284.     int i;
  285.     int s = 0;
  286.     T res;
  287.     for(i=(0);i<(sz);i++){
  288.       s += a[i];
  289.     }
  290.     if(mem_fact < s+1){
  291.       expand_fact(s+1);
  292.     }
  293.     res = factri[s];
  294.     for(i=(0);i<(sz);i++){
  295.       res *= ifactri[a[i]];
  296.     }
  297.     return 1;
  298.   }
  299.   inline T Multinomial(int a){
  300.     return 1;
  301.   }
  302.   inline T Multinomial(int a, int b){
  303.     if(mem_fact < a+b+1){
  304.       expand_fact(a+b+1);
  305.     }
  306.     return factri[a+b] * ifactri[a] * ifactri[b];
  307.   }
  308.   inline T Multinomial(int a, int b, int c){
  309.     if(mem_fact < a+b+c+1){
  310.       expand_fact(a+b+c+1);
  311.     }
  312.     return factri[a+b+c] * ifactri[a] * ifactri[b] * ifactri[c];
  313.   }
  314.   inline T Multinomial(int a, int b, int c, int d){
  315.     if(mem_fact < a+b+c+d+1){
  316.       expand_fact(a+b+c+d+1);
  317.     }
  318.     return factri[a+b+c+d] * ifactri[a] * ifactri[b] * ifactri[c] * ifactri[d];
  319.   }
  320.   inline T Catalan(int n){
  321.     if(n < 0){
  322.       return 0;
  323.     }
  324.     if(mem_fact < 2*n+1){
  325.       expand_fact(2*n+1);
  326.     }
  327.     return factri[2*n] * ifactri[n] * ifactri[n+1];
  328.   }
  329.   inline T C_s(long long a, long long b){
  330.     long long i;
  331.     T res;
  332.     if(b < 0 || b > a){
  333.       return 0;
  334.     }
  335.     if(b > a - b){
  336.       b = a - b;
  337.     }
  338.     res = 1;
  339.     for(i=(0);i<(b);i++){
  340.       res *= a - i;
  341.       res /= i + 1;
  342.     }
  343.     return res;
  344.   }
  345.   inline T P_s(long long a, long long b){
  346.     long long i;
  347.     T res;
  348.     if(b < 0 || b > a){
  349.       return 0;
  350.     }
  351.     res = 1;
  352.     for(i=(0);i<(b);i++){
  353.       res *= a - i;
  354.     }
  355.     return res;
  356.   }
  357.   inline T per_s(long long n, long long k){
  358.     T d;
  359.     int m;
  360.     if(n < 0 || k < 0){
  361.       return 0;
  362.     }
  363.     if(n == k  &&  k == 0){
  364.       return 1;
  365.     }
  366.     if(n == 0 || k == 0){
  367.       return 0;
  368.     }
  369.     if(k==1){
  370.       return 1;
  371.     }
  372.     if(k==2){
  373.       d = n / 2;
  374.       return d;
  375.     }
  376.     if(k==3){
  377.       d = (n-1) / 6;
  378.       m = (n-1) % 6;
  379.       if(m==0){
  380.         return 3 * d * d + d;
  381.       }
  382.       if(m==1){
  383.         return 3 * d * d + 2 * d;
  384.       }
  385.       if(m==2){
  386.         return 3 * d * d + 3 * d + 1;
  387.       }
  388.       if(m==3){
  389.         return 3 * d * d + 4 * d + 1;
  390.       }
  391.       if(m==4){
  392.         return 3 * d * d + 5 * d + 2;
  393.       }
  394.       if(m==5){
  395.         return 3 * d * d + 6 * d + 3;
  396.       }
  397.     }
  398.     assert(0 && "per_s should be k <= 3");
  399.     return -1;
  400.   }
  401. }
  402. ;
  403. #define main dummy_main
  404. int main(){
  405.   wmem = memarr;
  406.   return 0;
  407. }
  408. #undef main
  409. class Solution{
  410.   public:
  411.   int numberOfWays(int num_people){
  412.     Comb<Modint> c;
  413.     return c.Catalan(num_people/2);
  414.   }
  415. }
  416. ;
  417. // cLay varsion 20191123-1
  418.  
  419. // --- original code ---
  420. // #define main dummy_main
  421. // {}
  422. // #undef main
  423. // 
  424. // class Solution {
  425. // public:
  426. //   int numberOfWays(int num_people) {
  427. //     Comb<Modint> c;
  428. //     return c.Catalan(num_people/2);
  429. //   }
  430. // };
  431.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/3LzJtY
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!