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 S, class T> inline S min_L(S a,T b){
  8.   return a<=b?a:b;
  9. }
  10. struct Modint{
  11.   unsigned val;
  12.   Modint(){
  13.     val=0;
  14.   }
  15.   Modint(int a){
  16.     val = ord(a);
  17.   }
  18.   Modint(unsigned a){
  19.     val = ord(a);
  20.   }
  21.   Modint(long long a){
  22.     val = ord(a);
  23.   }
  24.   Modint(unsigned long long a){
  25.     val = ord(a);
  26.   }
  27.   inline unsigned ord(unsigned a){
  28.     return a%MD;
  29.   }
  30.   inline unsigned ord(int a){
  31.     a %= (int)MD;
  32.     if(a < 0){
  33.       a += MD;
  34.     }
  35.     return a;
  36.   }
  37.   inline unsigned ord(unsigned long long a){
  38.     return a%MD;
  39.   }
  40.   inline unsigned ord(long long a){
  41.     a %= (int)MD;
  42.     if(a < 0){
  43.       a += MD;
  44.     }
  45.     return a;
  46.   }
  47.   inline unsigned get(){
  48.     return val;
  49.   }
  50.   inline Modint &operator+=(Modint a){
  51.     val += a.val;
  52.     if(val >= MD){
  53.       val -= MD;
  54.     }
  55.     return *this;
  56.   }
  57.   inline Modint &operator-=(Modint a){
  58.     if(val < a.val){
  59.       val = val + MD - a.val;
  60.     }
  61.     else{
  62.       val -= a.val;
  63.     }
  64.     return *this;
  65.   }
  66.   inline Modint &operator*=(Modint a){
  67.     val = ((unsigned long long)val*a.val)%MD;
  68.     return *this;
  69.   }
  70.   inline Modint &operator/=(Modint a){
  71.     return *this *= a.inverse();
  72.   }
  73.   inline Modint operator+(Modint a){
  74.     return Modint(*this)+=a;
  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+(int a){
  86.     return Modint(*this)+=Modint(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+(long long 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-(void){
  110.     Modint res;
  111.     if(val){
  112.       res.val=MD-val;
  113.     }
  114.     else{
  115.       res.val=0;
  116.     }
  117.     return res;
  118.   }
  119.   inline operator bool(void){
  120.     return val!=0;
  121.   }
  122.   inline operator int(void){
  123.     return get();
  124.   }
  125.   inline operator long long(void){
  126.     return get();
  127.   }
  128.   inline Modint inverse(){
  129.     int a = val;
  130.     int b = MD;
  131.     int u = 1;
  132.     int v = 0;
  133.     int t;
  134.     Modint res;
  135.     while(b){
  136.       t = a / b;
  137.       a -= t * b;
  138.       swap(a, b);
  139.       u -= t * v;
  140.       swap(u, v);
  141.     }
  142.     if(u < 0){
  143.       u += MD;
  144.     }
  145.     res.val = u;
  146.     return res;
  147.   }
  148.   inline Modint pw(unsigned long long b){
  149.     Modint a(*this);
  150.     Modint res;
  151.     res.val = 1;
  152.     while(b){
  153.       if(b&1){
  154.         res *= a;
  155.       }
  156.       b >>= 1;
  157.       a *= a;
  158.     }
  159.     return res;
  160.   }
  161.   inline bool operator==(int a){
  162.     return ord(a)==val;
  163.   }
  164.   inline bool operator!=(int a){
  165.     return ord(a)!=val;
  166.   }
  167. }
  168. ;
  169. inline Modint operator+(int a, Modint b){
  170.   return Modint(a)+=b;
  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+(long long 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 int my_getchar_unlocked(){
  194.   static char buf[1048576];
  195.   static int s = 1048576;
  196.   static int e = 1048576;
  197.   if(s == e && e == 1048576){
  198.     e = fread_unlocked(buf, 1, 1048576, stdin);
  199.     s = 0;
  200.   }
  201.   if(s == e){
  202.     return EOF;
  203.   }
  204.   return buf[s++];
  205. }
  206. inline void rd(int &x){
  207.   int k;
  208.   int m=0;
  209.   x=0;
  210.   for(;;){
  211.     k = my_getchar_unlocked();
  212.     if(k=='-'){
  213.       m=1;
  214.       break;
  215.     }
  216.     if('0'<=k&&k<='9'){
  217.       x=k-'0';
  218.       break;
  219.     }
  220.   }
  221.   for(;;){
  222.     k = my_getchar_unlocked();
  223.     if(k<'0'||k>'9'){
  224.       break;
  225.     }
  226.     x=x*10+k-'0';
  227.   }
  228.   if(m){
  229.     x=-x;
  230.   }
  231. }
  232. struct MY_WRITER{
  233.   char buf[1048576];
  234.   int s;
  235.   int e;
  236.   MY_WRITER(){
  237.     s = 0;
  238.     e = 1048576;
  239.   }
  240.   ~MY_WRITER(){
  241.     if(s){
  242.       fwrite_unlocked(buf, 1, s, stdout);
  243.     }
  244.   }
  245. }
  246. ;
  247. MY_WRITER MY_WRITER_VAR;
  248. void my_putchar_unlocked(int a){
  249.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  250.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  251.     MY_WRITER_VAR.s = 0;
  252.   }
  253.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  254. }
  255. inline void wt_L(char a){
  256.   my_putchar_unlocked(a);
  257. }
  258. inline void wt_L(int x){
  259.   int s=0;
  260.   int m=0;
  261.   char f[10];
  262.   if(x<0){
  263.     m=1;
  264.     x=-x;
  265.   }
  266.   while(x){
  267.     f[s++]=x%10;
  268.     x/=10;
  269.   }
  270.   if(!s){
  271.     f[s++]=0;
  272.   }
  273.   if(m){
  274.     my_putchar_unlocked('-');
  275.   }
  276.   while(s--){
  277.     my_putchar_unlocked(f[s]+'0');
  278.   }
  279. }
  280. inline void wt_L(unsigned x){
  281.   int s=0;
  282.   char f[10];
  283.   while(x){
  284.     f[s++]=x%10;
  285.     x/=10;
  286.   }
  287.   if(!s){
  288.     f[s++]=0;
  289.   }
  290.   while(s--){
  291.     my_putchar_unlocked(f[s]+'0');
  292.   }
  293. }
  294. inline void wt_L(long long x){
  295.   int s=0;
  296.   int m=0;
  297.   char f[20];
  298.   if(x<0){
  299.     m=1;
  300.     x=-x;
  301.   }
  302.   while(x){
  303.     f[s++]=x%10;
  304.     x/=10;
  305.   }
  306.   if(!s){
  307.     f[s++]=0;
  308.   }
  309.   if(m){
  310.     my_putchar_unlocked('-');
  311.   }
  312.   while(s--){
  313.     my_putchar_unlocked(f[s]+'0');
  314.   }
  315. }
  316. inline void wt_L(unsigned long long x){
  317.   int s=0;
  318.   char f[21];
  319.   while(x){
  320.     f[s++]=x%10;
  321.     x/=10;
  322.   }
  323.   if(!s){
  324.     f[s++]=0;
  325.   }
  326.   while(s--){
  327.     my_putchar_unlocked(f[s]+'0');
  328.   }
  329. }
  330. inline void wt_L(Modint x){
  331.   int i;
  332.   i = (int)x;
  333.   wt_L(i);
  334. }
  335. int WRITER_DOUBLE_DIGIT = 15;
  336. inline int writerDigit_double(){
  337.   return WRITER_DOUBLE_DIGIT;
  338. }
  339. inline void writerDigit_double(int d){
  340.   WRITER_DOUBLE_DIGIT = d;
  341. }
  342. inline void wt_L(double x){
  343.   const int d = WRITER_DOUBLE_DIGIT;
  344.   int k;
  345.   int r;
  346.   double v;
  347.   if(x!=x || (x==x+1 && x==2*x)){
  348.     my_putchar_unlocked('E');
  349.     my_putchar_unlocked('r');
  350.     my_putchar_unlocked('r');
  351.     return;
  352.   }
  353.   if(x < 0){
  354.     my_putchar_unlocked('-');
  355.     x = -x;
  356.   }
  357.   x += 0.5 * pow(0.1, d);
  358.   r = 0;
  359.   v = 1;
  360.   while(x >= 10*v){
  361.     v *= 10;
  362.     r++;
  363.   }
  364.   while(r >= 0){
  365.     r--;
  366.     k = floor(x / v);
  367.     if(k >= 10){
  368.       k = 9;
  369.     }
  370.     if(k <= -1){
  371.       k = 0;
  372.     }
  373.     x -= k * v;
  374.     v *= 0.1;
  375.     my_putchar_unlocked(k + '0');
  376.   }
  377.   if(d > 0){
  378.     my_putchar_unlocked('.');
  379.     v = 1;
  380.     for(r=(0);r<(d);r++){
  381.       v *= 0.1;
  382.       k = floor(x / v);
  383.       if(k >= 10){
  384.         k = 9;
  385.       }
  386.       if(k <= -1){
  387.         k = 0;
  388.       }
  389.       x -= k * v;
  390.       my_putchar_unlocked(k + '0');
  391.     }
  392.   }
  393. }
  394. inline void wt_L(const char c[]){
  395.   int i=0;
  396.   for(i=0;c[i]!='\0';i++){
  397.     my_putchar_unlocked(c[i]);
  398.   }
  399. }
  400. inline void wt_L(string &x){
  401.   int i=0;
  402.   for(i=0;x[i]!='\0';i++){
  403.     my_putchar_unlocked(x[i]);
  404.   }
  405. }
  406. template<class T> struct Matrix{
  407.   int r;
  408.   int c;
  409.   int mem;
  410.   T*dat;
  411.   Matrix(){
  412.     r=c=mem = 0;
  413.   }
  414.   Matrix(const int rr, const int cc){
  415.     if(rr == 0 || cc == 0){
  416.       r = c = 0;
  417.     }
  418.     else{
  419.       r = rr;
  420.       c = cc;
  421.     }
  422.     mem = r * c;
  423.     if(mem > 0){
  424.       dat = new T[mem];
  425.     }
  426.   }
  427.   Matrix(const Matrix<T> &a){
  428.     int i;
  429.     r = a.r;
  430.     c = a.c;
  431.     mem = r * c;
  432.     dat = new T[mem];
  433.     for(i=(0);i<(mem);i++){
  434.       dat[i] = a.dat[i];
  435.     }
  436.   }
  437.   ~Matrix(){
  438.     if(mem){
  439.       delete [] dat;
  440.     }
  441.   }
  442.   void changeSize(const int rr, const int cc){
  443.     if(rr==0 || cc==0){
  444.       r = c = 0;
  445.     }
  446.     else{
  447.       r = rr;
  448.       c = cc;
  449.     }
  450.     if(mem < r*c){
  451.       if(mem){
  452.         delete [] dat;
  453.       }
  454.       mem = r*c;
  455.       dat = new T[mem];
  456.     }
  457.   }
  458.   Matrix<T>& operator=(const Matrix<T> &a){
  459.     int i;
  460.     int j;
  461.     r = a.r;
  462.     c = a.c;
  463.     j = r * c;
  464.     changeSize(r,c);
  465.     for(i=(0);i<(j);i++){
  466.       dat[i] = a.dat[i];
  467.     }
  468.     return *this;
  469.   }
  470.   Matrix<T>& operator=(const int a){
  471.     int i;
  472.     int j;
  473.     j = r * c;
  474.     for(i=(0);i<(j);i++){
  475.       dat[i] = 0;
  476.     }
  477.     j =min_L(r, c);
  478.     for(i=(0);i<(j);i++){
  479.       dat[i*c+i] = a;
  480.     }
  481.     return *this;
  482.   }
  483.   Matrix<T>& operator+=(const Matrix<T> &a){
  484.     int i;
  485.     int j;
  486.     if(r==0 || r!=a.r || c!=a.c){
  487.       changeSize(0,0);
  488.       return *this;
  489.     }
  490.     j = r*c;
  491.     for(i=(0);i<(j);i++){
  492.       dat[i] += a.dat[i];
  493.     }
  494.     return *this;
  495.   }
  496.   Matrix<T> operator+(const Matrix<T> &a){
  497.     return Matrix<T>(*this) += a;
  498.   }
  499.   Matrix<T>& operator-=(const Matrix<T> &a){
  500.     int i;
  501.     int j;
  502.     if(r==0 || r!=a.r || c!=a.c){
  503.       changeSize(0,0);
  504.       return *this;
  505.     }
  506.     j = r*c;
  507.     for(i=(0);i<(j);i++){
  508.       dat[i] -= a.dat[i];
  509.     }
  510.     return *this;
  511.   }
  512.   Matrix<T> operator-(const Matrix<T> &a){
  513.     return Matrix<T>(*this) -= a;
  514.   }
  515.   Matrix<T>& operator*=(const Matrix<T> &a){
  516.     int i;
  517.     int j;
  518.     int k;
  519.     int x;
  520.     T*m;
  521.     if(r==0 || c!=a.r){
  522.       changeSize(0,0);
  523.       return *this;
  524.     }
  525.     m = (T*)wmem;
  526.     x = r * a.c;
  527.     for(i=(0);i<(x);i++){
  528.       m[i] = 0;
  529.     }
  530.     for(i=(0);i<(r);i++){
  531.       for(k=(0);k<(c);k++){
  532.         for(j=(0);j<(a.c);j++){
  533.           m[i*a.c+j] += dat[i*c+k] * a.dat[k*a.c+j];
  534.         }
  535.       }
  536.     }
  537.     changeSize(r, a.c);
  538.     for(i=(0);i<(x);i++){
  539.       dat[i] = m[i];
  540.     }
  541.     return *this;
  542.   }
  543.   Matrix<T> operator*(const Matrix<T> &a){
  544.     return Matrix<T>(*this) *= a;
  545.   }
  546.   Matrix<T>& operator*=(const int a){
  547.     int i;
  548.     int j;
  549.     j = r * c;
  550.     for(i=(0);i<(j);i++){
  551.       dat[i] *= a;
  552.     }
  553.     return *this;
  554.   }
  555.   Matrix<T>& operator*=(const long long a){
  556.     int i;
  557.     int j;
  558.     j = r * c;
  559.     for(i=(0);i<(j);i++){
  560.       dat[i] *= a;
  561.     }
  562.     return *this;
  563.   }
  564.   Matrix<T>& operator*=(const double a){
  565.     int i;
  566.     int j;
  567.     j = r * c;
  568.     for(i=(0);i<(j);i++){
  569.       dat[i] *= a;
  570.     }
  571.     return *this;
  572.   }
  573.   inline T* operator[](const int a){
  574.     return dat+a*c;
  575.   }
  576. }
  577. ;
  578. template<class T> Matrix<T> operator*(const int a, const Matrix<T> &b){
  579.   return Matrix<T>(b)*=a;
  580. }
  581. template<class T> Matrix<T> operator*(const Matrix<T> &b, const int a){
  582.   return Matrix<T>(b)*=a;
  583. }
  584. template<class T> Matrix<T> operator*(const long long a, const Matrix<T> &b){
  585.   return Matrix<T>(b)*=a;
  586. }
  587. template<class T> Matrix<T> operator*(const Matrix<T> &b, const long long a){
  588.   return Matrix<T>(b)*=a;
  589. }
  590. template<class T> Matrix<T> operator*(const double a, const Matrix<T> &b){
  591.   return Matrix<T>(b)*=a;
  592. }
  593. template<class T> Matrix<T> operator*(const Matrix<T> &b, const double a){
  594.   return Matrix<T>(b)*=a;
  595. }
  596. template<class T, class S> inline Matrix<T> pow_L(Matrix<T> a, S b){
  597.   int i;
  598.   int j;
  599.   Matrix<T> res;
  600.   res.changeSize(a.r, a.c);
  601.   res = 1;
  602.   while(b){
  603.     if(b&1){
  604.       res *= a;
  605.     }
  606.     b >>= 1;
  607.     a *= a;
  608.   }
  609.   return res;
  610. }
  611. template<class T, class S> inline T pow_L(T a, S b){
  612.   T res = 1;
  613.   res = 1;
  614.   for(;;){
  615.     if(b&1){
  616.       res *= a;
  617.     }
  618.     b >>= 1;
  619.     if(b==0){
  620.       break;
  621.     }
  622.     a *= a;
  623.   }
  624.   return res;
  625. }
  626. inline double pow_L(double a, double b){
  627.   return pow(a,b);
  628. }
  629. int main(){
  630.   wmem = memarr;
  631.   int N;
  632.   rd(N);
  633.   int M;
  634.   rd(M);
  635.   Matrix<Modint> mt(2,2);
  636.   mt[0][0] = M-1;
  637.   mt[0][1] = 1;
  638.   mt[1][0] = M-1;
  639.   mt[1][1] = 0;
  640.   (mt = pow_L(mt,N));
  641.   wt_L(mt[0][0] + mt[0][1] -(pow_L(Modint(M-1),N)));
  642.   wt_L('\n');
  643.   return 0;
  644. }
  645. // cLay version 20201123-1
  646.  
  647. // --- original code ---
  648. // {
  649. //   int @N, @M;
  650. //   Matrix<Modint> mt(2,2);
  651. //   mt[0][0] = M-1;
  652. //   mt[0][1] = 1;
  653. //   mt[1][0] = M-1;
  654. //   mt[1][1] = 0;
  655. //   mt **= N;
  656. //   wt(mt[0][0] + mt[0][1] - Modint(M-1)**N);
  657. // }
  658.  
Time limit exceeded #stdin #stdout 5s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/v4Urax
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!