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. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  14.   walloc1d(arr, x2-x1, mem);
  15.   (*arr) -= x1;
  16. }
  17. struct Modint{
  18.   unsigned val;
  19.   Modint(){
  20.     val=0;
  21.   }
  22.   Modint(int a){
  23.     val = ord(a);
  24.   }
  25.   Modint(unsigned a){
  26.     val = ord(a);
  27.   }
  28.   Modint(long long a){
  29.     val = ord(a);
  30.   }
  31.   Modint(unsigned long long a){
  32.     val = ord(a);
  33.   }
  34.   inline unsigned ord(unsigned a){
  35.     return a%MD;
  36.   }
  37.   inline unsigned ord(int a){
  38.     a %= (int)MD;
  39.     if(a < 0){
  40.       a += MD;
  41.     }
  42.     return a;
  43.   }
  44.   inline unsigned ord(unsigned long long a){
  45.     return a%MD;
  46.   }
  47.   inline unsigned ord(long long a){
  48.     a %= (int)MD;
  49.     if(a < 0){
  50.       a += MD;
  51.     }
  52.     return a;
  53.   }
  54.   inline unsigned get(){
  55.     return val;
  56.   }
  57.   inline Modint &operator+=(Modint a){
  58.     val += a.val;
  59.     if(val >= MD){
  60.       val -= MD;
  61.     }
  62.     return *this;
  63.   }
  64.   inline Modint &operator-=(Modint a){
  65.     if(val < a.val){
  66.       val = val + MD - a.val;
  67.     }
  68.     else{
  69.       val -= a.val;
  70.     }
  71.     return *this;
  72.   }
  73.   inline Modint &operator*=(Modint a){
  74.     val = ((unsigned long long)val*a.val)%MD;
  75.     return *this;
  76.   }
  77.   inline Modint &operator/=(Modint a){
  78.     return *this *= a.inverse();
  79.   }
  80.   inline Modint operator+(Modint a){
  81.     return Modint(*this)+=a;
  82.   }
  83.   inline Modint operator-(Modint a){
  84.     return Modint(*this)-=a;
  85.   }
  86.   inline Modint operator*(Modint a){
  87.     return Modint(*this)*=a;
  88.   }
  89.   inline Modint operator/(Modint a){
  90.     return Modint(*this)/=a;
  91.   }
  92.   inline Modint operator+(int a){
  93.     return Modint(*this)+=Modint(a);
  94.   }
  95.   inline Modint operator-(int a){
  96.     return Modint(*this)-=Modint(a);
  97.   }
  98.   inline Modint operator*(int a){
  99.     return Modint(*this)*=Modint(a);
  100.   }
  101.   inline Modint operator/(int a){
  102.     return Modint(*this)/=Modint(a);
  103.   }
  104.   inline Modint operator+(long long a){
  105.     return Modint(*this)+=Modint(a);
  106.   }
  107.   inline Modint operator-(long long a){
  108.     return Modint(*this)-=Modint(a);
  109.   }
  110.   inline Modint operator*(long long a){
  111.     return Modint(*this)*=Modint(a);
  112.   }
  113.   inline Modint operator/(long long a){
  114.     return Modint(*this)/=Modint(a);
  115.   }
  116.   inline Modint operator-(void){
  117.     Modint res;
  118.     if(val){
  119.       res.val=MD-val;
  120.     }
  121.     else{
  122.       res.val=0;
  123.     }
  124.     return res;
  125.   }
  126.   inline operator bool(void){
  127.     return val!=0;
  128.   }
  129.   inline operator int(void){
  130.     return get();
  131.   }
  132.   inline operator long long(void){
  133.     return get();
  134.   }
  135.   inline Modint inverse(){
  136.     int a = val;
  137.     int b = MD;
  138.     int u = 1;
  139.     int v = 0;
  140.     int t;
  141.     Modint res;
  142.     while(b){
  143.       t = a / b;
  144.       a -= t * b;
  145.       swap(a, b);
  146.       u -= t * v;
  147.       swap(u, v);
  148.     }
  149.     if(u < 0){
  150.       u += MD;
  151.     }
  152.     res.val = u;
  153.     return res;
  154.   }
  155.   inline Modint pw(unsigned long long b){
  156.     Modint a(*this);
  157.     Modint res;
  158.     res.val = 1;
  159.     while(b){
  160.       if(b&1){
  161.         res *= a;
  162.       }
  163.       b >>= 1;
  164.       a *= a;
  165.     }
  166.     return res;
  167.   }
  168.   inline bool operator==(int a){
  169.     return ord(a)==val;
  170.   }
  171.   inline bool operator!=(int a){
  172.     return ord(a)!=val;
  173.   }
  174. }
  175. ;
  176. inline Modint operator+(int a, Modint b){
  177.   return Modint(a)+=b;
  178. }
  179. inline Modint operator-(int a, Modint b){
  180.   return Modint(a)-=b;
  181. }
  182. inline Modint operator*(int a, Modint b){
  183.   return Modint(a)*=b;
  184. }
  185. inline Modint operator/(int a, Modint b){
  186.   return Modint(a)/=b;
  187. }
  188. inline Modint operator+(long long a, Modint b){
  189.   return Modint(a)+=b;
  190. }
  191. inline Modint operator-(long long a, Modint b){
  192.   return Modint(a)-=b;
  193. }
  194. inline Modint operator*(long long a, Modint b){
  195.   return Modint(a)*=b;
  196. }
  197. inline Modint operator/(long long a, Modint b){
  198.   return Modint(a)/=b;
  199. }
  200. template<class S, class T> inline S chmax(S &a, T b){
  201.   if(a<b){
  202.     a=b;
  203.   }
  204.   return a;
  205. }
  206. template<class T> struct Comb{
  207.   int mem_fact;
  208.   T*factri;
  209.   T*ifactri;
  210.   int mem_dfact;
  211.   T*dfactri;
  212.   int mem_pw2;
  213.   int mem_pw3;
  214.   int mem_pw10;
  215.   int mem_rep1;
  216.   T*pw2c;
  217.   T*pw3c;
  218.   T*pw10c;
  219.   T*rep1c;
  220.   int mem_ipw2;
  221.   int mem_ipw3;
  222.   int mem_ipw10;
  223.   T*ipw2c;
  224.   T*ipw3c;
  225.   T*ipw10c;
  226.   Comb(){
  227.     mem_fact = 0;
  228.     mem_dfact = 0;
  229.     mem_pw2 = mem_pw3 = mem_pw10 = mem_rep1 = 0;
  230.     mem_ipw2 = mem_ipw3 = mem_ipw10 = 0;
  231.   }
  232.   inline void expand_fact(int k){
  233.     int i;
  234.     if(k <= mem_fact){
  235.       return;
  236.     }
  237.     chmax(k, 2 * mem_fact);
  238.     if(mem_fact == 0){
  239.       factri = (T*)malloc(k * sizeof(T));
  240.       ifactri = (T*)malloc(k * sizeof(T));
  241.       factri[0] = 1;
  242.       for(i=(1);i<(k);i++){
  243.         factri[i] = i * factri[i-1];
  244.       }
  245.       ifactri[k-1] = 1 / factri[k-1];
  246.       for(i=(k-1)-1;i>=(0);i--){
  247.         ifactri[i] = (i+1) * ifactri[i+1];
  248.       }
  249.     }
  250.     else{
  251.       factri = (T*)realloc(factri, k * sizeof(T));
  252.       ifactri = (T*)realloc(ifactri, k * sizeof(T));
  253.       for(i=(mem_fact);i<(k);i++){
  254.         factri[i] = i * factri[i-1];
  255.       }
  256.       ifactri[k-1] = 1 / factri[k-1];
  257.       for(i=(k-1)-1;i>=(mem_fact);i--){
  258.         ifactri[i] = (i+1) * ifactri[i+1];
  259.       }
  260.     }
  261.     mem_fact = k;
  262.   }
  263.   inline T fac(int k){
  264.     if(mem_fact < k+1){
  265.       expand_fact(k+1);
  266.     }
  267.     return factri[k];
  268.   }
  269.   inline T ifac(int k){
  270.     if(mem_fact < k+1){
  271.       expand_fact(k+1);
  272.     }
  273.     return ifactri[k];
  274.   }
  275.   inline T C(int a, int b){
  276.     if(b < 0 || b > a){
  277.       return 0;
  278.     }
  279.     if(mem_fact < a+1){
  280.       expand_fact(a+1);
  281.     }
  282.     return factri[a] * ifactri[b] * ifactri[a-b];
  283.   }
  284.   inline T P(int a, int b){
  285.     if(b < 0 || b > a){
  286.       return 0;
  287.     }
  288.     if(mem_fact < a+1){
  289.       expand_fact(a+1);
  290.     }
  291.     return factri[a] * ifactri[a-b];
  292.   }
  293.   inline T H(int a, int b){
  294.     if(a==0 && b==0){
  295.       return 1;
  296.     }
  297.     if(a <= 0 || b < 0){
  298.       return 0;
  299.     }
  300.     if(mem_fact < a+b){
  301.       expand_fact(a+b);
  302.     }
  303.     return C(a+b-1, b);
  304.   }
  305.   inline T Multinomial(int sz, int a[]){
  306.     int i;
  307.     int s = 0;
  308.     T res;
  309.     for(i=(0);i<(sz);i++){
  310.       s += a[i];
  311.     }
  312.     if(mem_fact < s+1){
  313.       expand_fact(s+1);
  314.     }
  315.     res = factri[s];
  316.     for(i=(0);i<(sz);i++){
  317.       res *= ifactri[a[i]];
  318.     }
  319.     return 1;
  320.   }
  321.   inline T Multinomial(int a){
  322.     return 1;
  323.   }
  324.   inline T Multinomial(int a, int b){
  325.     if(mem_fact < a+b+1){
  326.       expand_fact(a+b+1);
  327.     }
  328.     return factri[a+b] * ifactri[a] * ifactri[b];
  329.   }
  330.   inline T Multinomial(int a, int b, int c){
  331.     if(mem_fact < a+b+c+1){
  332.       expand_fact(a+b+c+1);
  333.     }
  334.     return factri[a+b+c] * ifactri[a] * ifactri[b] * ifactri[c];
  335.   }
  336.   inline T Multinomial(int a, int b, int c, int d){
  337.     if(mem_fact < a+b+c+d+1){
  338.       expand_fact(a+b+c+d+1);
  339.     }
  340.     return factri[a+b+c+d] * ifactri[a] * ifactri[b] * ifactri[c] * ifactri[d];
  341.   }
  342.   inline T Catalan(int n){
  343.     if(n < 0){
  344.       return 0;
  345.     }
  346.     if(mem_fact < 2*n+1){
  347.       expand_fact(2*n+1);
  348.     }
  349.     return factri[2*n] * ifactri[n] * ifactri[n+1];
  350.   }
  351.   inline T C_s(long long a, long long b){
  352.     long long i;
  353.     T res;
  354.     if(b < 0 || b > a){
  355.       return 0;
  356.     }
  357.     if(b > a - b){
  358.       b = a - b;
  359.     }
  360.     res = 1;
  361.     for(i=(0);i<(b);i++){
  362.       res *= a - i;
  363.       res /= i + 1;
  364.     }
  365.     return res;
  366.   }
  367.   inline T P_s(long long a, long long b){
  368.     long long i;
  369.     T res;
  370.     if(b < 0 || b > a){
  371.       return 0;
  372.     }
  373.     res = 1;
  374.     for(i=(0);i<(b);i++){
  375.       res *= a - i;
  376.     }
  377.     return res;
  378.   }
  379.   inline T per_s(long long n, long long k){
  380.     T d;
  381.     int m;
  382.     if(n < 0 || k < 0){
  383.       return 0;
  384.     }
  385.     if(n == k  &&  k == 0){
  386.       return 1;
  387.     }
  388.     if(n == 0 || k == 0){
  389.       return 0;
  390.     }
  391.     if(k==1){
  392.       return 1;
  393.     }
  394.     if(k==2){
  395.       d = n / 2;
  396.       return d;
  397.     }
  398.     if(k==3){
  399.       d = (n-1) / 6;
  400.       m = (n-1) % 6;
  401.       if(m==0){
  402.         return 3 * d * d + d;
  403.       }
  404.       if(m==1){
  405.         return 3 * d * d + 2 * d;
  406.       }
  407.       if(m==2){
  408.         return 3 * d * d + 3 * d + 1;
  409.       }
  410.       if(m==3){
  411.         return 3 * d * d + 4 * d + 1;
  412.       }
  413.       if(m==4){
  414.         return 3 * d * d + 5 * d + 2;
  415.       }
  416.       if(m==5){
  417.         return 3 * d * d + 6 * d + 3;
  418.       }
  419.     }
  420.     assert(0 && "per_s should be k <= 3");
  421.     return -1;
  422.   }
  423.   inline void expand_dfact(int k){
  424.     int i;
  425.     if(k <= mem_dfact){
  426.       return;
  427.     }
  428.     chmax(k, 3);
  429.     chmax(k, 2 * mem_dfact);
  430.     if(mem_dfact==0){
  431.       dfactri = (T*)malloc(k * sizeof(T));
  432.       dfactri[0] = dfactri[1] = 1;
  433.       for(i=(2);i<(k);i++){
  434.         dfactri[i] = i * dfactri[i-2];
  435.       }
  436.     }
  437.     else{
  438.       dfactri = (T*)realloc(dfactri, k * sizeof(T));
  439.       for(i=(mem_dfact);i<(k);i++){
  440.         dfactri[i] = i * dfactri[i-2];
  441.       }
  442.     }
  443.     mem_dfact = k;
  444.   }
  445.   inline void expand_pw2(int k){
  446.     int i;
  447.     if(k <= mem_pw2){
  448.       return;
  449.     }
  450.     chmax(k, 2 * mem_pw2);
  451.     if(mem_pw2==0){
  452.       pw2c = (T*)malloc(k * sizeof(T));
  453.       pw2c[0] = 1;
  454.       for(i=(1);i<(k);i++){
  455.         pw2c[i] = 2 * pw2c[i-1];
  456.       }
  457.     }
  458.     else{
  459.       pw2c = (T*)realloc(pw2c, k * sizeof(T));
  460.       for(i=(mem_pw2);i<(k);i++){
  461.         pw2c[i] = 2 * pw2c[i-1];
  462.       }
  463.     }
  464.     mem_pw2 = k;
  465.   }
  466.   inline void expand_ipw2(int k){
  467.     int i;
  468.     if(k <= mem_ipw2){
  469.       return;
  470.     }
  471.     chmax(k, 2);
  472.     chmax(k, 2 * mem_ipw2);
  473.     if(mem_ipw2==0){
  474.       ipw2c = (T*)malloc(k * sizeof(T));
  475.       ipw2c[0] = 1;
  476.       ipw2c[1] = ipw2c[0] / 2;
  477.       for(i=(1);i<(k);i++){
  478.         ipw2c[i] = ipw2c[1] * ipw2c[i-1];
  479.       }
  480.     }
  481.     else{
  482.       ipw2c = (T*)realloc(ipw2c, k * sizeof(T));
  483.       for(i=(mem_ipw2);i<(k);i++){
  484.         ipw2c[i] = ipw2c[1] * ipw2c[i-1];
  485.       }
  486.     }
  487.     mem_ipw2 = k;
  488.   }
  489.   inline void expand_pw3(int k){
  490.     int i;
  491.     if(k <= mem_pw3){
  492.       return;
  493.     }
  494.     chmax(k, 2 * mem_pw3);
  495.     if(mem_pw3==0){
  496.       pw3c = (T*)malloc(k * sizeof(T));
  497.       pw3c[0] = 1;
  498.       for(i=(1);i<(k);i++){
  499.         pw3c[i] = 3 * pw3c[i-1];
  500.       }
  501.     }
  502.     else{
  503.       pw3c = (T*)realloc(pw3c, k * sizeof(T));
  504.       for(i=(mem_pw3);i<(k);i++){
  505.         pw3c[i] = 3 * pw3c[i-1];
  506.       }
  507.     }
  508.     mem_pw3 = k;
  509.   }
  510.   inline void expand_ipw3(int k){
  511.     int i;
  512.     if(k <= mem_ipw3){
  513.       return;
  514.     }
  515.     chmax(k, 2);
  516.     chmax(k, 2 * mem_ipw3);
  517.     if(mem_ipw3==0){
  518.       ipw3c = (T*)malloc(k * sizeof(T));
  519.       ipw3c[0] = 1;
  520.       ipw3c[1] = ipw3c[0] / 3;
  521.       for(i=(1);i<(k);i++){
  522.         ipw3c[i] = ipw3c[1] * ipw3c[i-1];
  523.       }
  524.     }
  525.     else{
  526.       ipw3c = (T*)realloc(ipw3c, k * sizeof(T));
  527.       for(i=(mem_ipw3);i<(k);i++){
  528.         ipw3c[i] = ipw3c[1] * ipw3c[i-1];
  529.       }
  530.     }
  531.     mem_ipw3 = k;
  532.   }
  533.   inline void expand_pw10(int k){
  534.     int i;
  535.     if(k <= mem_pw10){
  536.       return;
  537.     }
  538.     chmax(k, 2 * mem_pw10);
  539.     if(mem_pw10==0){
  540.       pw10c = (T*)malloc(k * sizeof(T));
  541.       pw10c[0] = 1;
  542.       for(i=(1);i<(k);i++){
  543.         pw10c[i] = 10 * pw10c[i-1];
  544.       }
  545.     }
  546.     else{
  547.       pw10c = (T*)realloc(pw10c, k * sizeof(T));
  548.       for(i=(mem_pw10);i<(k);i++){
  549.         pw10c[i] = 10 * pw10c[i-1];
  550.       }
  551.     }
  552.     mem_pw10 = k;
  553.   }
  554.   inline void expand_ipw10(int k){
  555.     int i;
  556.     if(k <= mem_ipw10){
  557.       return;
  558.     }
  559.     chmax(k, 2);
  560.     chmax(k, 2 * mem_ipw10);
  561.     if(mem_ipw10==0){
  562.       ipw10c = (T*)malloc(k * sizeof(T));
  563.       ipw10c[0] = 1;
  564.       ipw10c[1] = ipw10c[0] / 10;
  565.       for(i=(1);i<(k);i++){
  566.         ipw10c[i] = ipw10c[1] * ipw10c[i-1];
  567.       }
  568.     }
  569.     else{
  570.       ipw10c = (T*)realloc(ipw10c, k * sizeof(T));
  571.       for(i=(mem_ipw10);i<(k);i++){
  572.         ipw10c[i] = ipw10c[1] * ipw10c[i-1];
  573.       }
  574.     }
  575.     mem_ipw10 = k;
  576.   }
  577.   inline void expand_rep1(int k){
  578.     int i;
  579.     if(k <= mem_rep1){
  580.       return;
  581.     }
  582.     chmax(k, 2 * mem_rep1);
  583.     if(mem_rep1==0){
  584.       rep1c = (T*)malloc(k * sizeof(T));
  585.       rep1c[0] = 0;
  586.       for(i=(1);i<(k);i++){
  587.         rep1c[i] = 10 * rep1c[i-1] + 1;
  588.       }
  589.     }
  590.     else{
  591.       rep1c = (T*)realloc(rep1c, k * sizeof(T));
  592.       for(i=(mem_rep1);i<(k);i++){
  593.         rep1c[i] = 10 * rep1c[i-1] + 1;
  594.       }
  595.     }
  596.     mem_rep1 = k;
  597.   }
  598.   inline T dfac(int k){
  599.     if(k >= 0){
  600.       if(mem_dfact < k+1){
  601.         expand_dfact(k+1);
  602.       }
  603.       return dfactri[k];
  604.     }
  605.     if(k==-1){
  606.       return 1;
  607.     }
  608.     k = - k - 2;
  609.     if(k % 4 == 1){
  610.       return 1 / (-dfac(k));
  611.     }
  612.     return 1 / dfac(k);
  613.   }
  614.   inline T pw2(int k){
  615.     if(k >= 0){
  616.       if(mem_pw2 < k+1){
  617.         expand_pw2(k+1);
  618.       }
  619.       return pw2c[k];
  620.     }
  621.     else{
  622.       k = -k;
  623.       if(mem_ipw2 < k+1){
  624.         expand_ipw2(k+1);
  625.       }
  626.       return ipw2c[k];
  627.     }
  628.   }
  629.   inline T pw3(int k){
  630.     if(k >= 0){
  631.       if(mem_pw3 < k+1){
  632.         expand_pw3(k+1);
  633.       }
  634.       return pw3c[k];
  635.     }
  636.     else{
  637.       k = -k;
  638.       if(mem_ipw3 < k+1){
  639.         expand_ipw3(k+1);
  640.       }
  641.       return ipw3c[k];
  642.     }
  643.   }
  644.   inline T pw10(int k){
  645.     if(k >= 0){
  646.       if(mem_pw10 < k+1){
  647.         expand_pw10(k+1);
  648.       }
  649.       return pw10c[k];
  650.     }
  651.     else{
  652.       k = -k;
  653.       if(mem_ipw10 < k+1){
  654.         expand_ipw10(k+1);
  655.       }
  656.       return ipw10c[k];
  657.     }
  658.   }
  659.   inline T repunit(int k){
  660.     if(mem_rep1 < k+1){
  661.       expand_rep1(k+1);
  662.     }
  663.     return rep1c[k];
  664.   }
  665. }
  666. ;
  667. template<> inline Modint Comb<Modint>::C_s(long long a, long long b){
  668.   long long i;
  669.   Modint res;
  670.   Modint d;
  671.   if(b < 0 || b > a){
  672.     return 0;
  673.   }
  674.   if(b > a - b){
  675.     b = a - b;
  676.   }
  677.   res = d = 1;
  678.   for(i=(0);i<(b);i++){
  679.     res *= a - i;
  680.     d *= i + 1;
  681.   }
  682.   return res / d;
  683. }
  684. #define main dummy_main
  685. int main(){
  686.   wmem = memarr;
  687.   return 0;
  688. }
  689. #undef main
  690. Comb<Modint> c;
  691. class Solution{
  692.   public:
  693.   int concatenatedBinary(int n){
  694.     int i;
  695.     int d = 0;
  696.     Modint res = 0;
  697.     for(i=(1);i<(n+1);i++){
  698.       if(i == (1<<d)){
  699.         d++;
  700.       }
  701.       res = res * c.pw2(d) + i;
  702.     }
  703.     return res;
  704.   }
  705. }
  706. ;
  707. // cLay version 20201206-1
  708.  
  709. // --- original code ---
  710. // #define main dummy_main
  711. // {}
  712. // #undef main
  713. // 
  714. // Comb<Modint> c;
  715. // 
  716. // class Solution {
  717. // public:
  718. //   int concatenatedBinary(int n) {
  719. //     int d = 0;
  720. //     Modint res = 0;
  721. //     rep(i,1,n+1){
  722. //       if(i == (1<<d)) d++;
  723. //       res = res * c.pw2(d) + i;
  724. //     }
  725. //     return res;
  726. //   }
  727. // };
  728.  
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/V4eO7a
language:
C++ (gcc 8.3)
created:
3 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!