結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2021-10-11 06:42:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 11,620 bytes |
コンパイル時間 | 2,367 ms |
コンパイル使用メモリ | 187,084 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 03:44:05 |
合計ジャッジ時間 | 5,716 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;#define MD (1000000007U)template<class T> struct cLtraits_identity{using type = T;};template<class T> using cLtraits_try_make_signed =typename conditional<is_integral<T>::value,make_signed<T>,cLtraits_identity<T>>::type;template <class S, class T> struct cLtraits_common_type{using tS = typename cLtraits_try_make_signed<S>::type;using tT = typename cLtraits_try_make_signed<T>::type;using type = typename common_type<tS,tT>::type;};void*wmem;char memarr[96000000];template<class S, class T> inline auto min_L(S a, T b)-> typename cLtraits_common_type<S,T>::type{return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;}struct Modint{unsigned val;Modint(){val=0;}Modint(int a){val = ord(a);}Modint(unsigned a){val = ord(a);}Modint(long long a){val = ord(a);}Modint(unsigned long long a){val = ord(a);}inline unsigned ord(unsigned a){return a%MD;}inline unsigned ord(int a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned ord(unsigned long long a){return a%MD;}inline unsigned ord(long long a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned get(){return val;}inline Modint &operator++(){val++;if(val >= MD){val -= MD;}return *this;}inline Modint &operator--(){if(val == 0){val = MD - 1;}else{--val;}return *this;}inline Modint operator++(int a){Modint res(*this);val++;if(val >= MD){val -= MD;}return res;}inline Modint operator--(int a){Modint res(*this);if(val == 0){val = MD - 1;}else{--val;}return res;}inline Modint &operator+=(Modint a){val += a.val;if(val >= MD){val -= MD;}return *this;}inline Modint &operator-=(Modint a){if(val < a.val){val = val + MD - a.val;}else{val -= a.val;}return *this;}inline Modint &operator*=(Modint a){val = ((unsigned long long)val*a.val)%MD;return *this;}inline Modint &operator/=(Modint a){return *this *= a.inverse();}inline Modint operator+(Modint a){return Modint(*this)+=a;}inline Modint operator-(Modint a){return Modint(*this)-=a;}inline Modint operator*(Modint a){return Modint(*this)*=a;}inline Modint operator/(Modint a){return Modint(*this)/=a;}inline Modint operator+(int a){return Modint(*this)+=Modint(a);}inline Modint operator-(int a){return Modint(*this)-=Modint(a);}inline Modint operator*(int a){return Modint(*this)*=Modint(a);}inline Modint operator/(int a){return Modint(*this)/=Modint(a);}inline Modint operator+(long long a){return Modint(*this)+=Modint(a);}inline Modint operator-(long long a){return Modint(*this)-=Modint(a);}inline Modint operator*(long long a){return Modint(*this)*=Modint(a);}inline Modint operator/(long long a){return Modint(*this)/=Modint(a);}inline Modint operator-(void){Modint res;if(val){res.val=MD-val;}else{res.val=0;}return res;}inline operator bool(void){return val!=0;}inline operator int(void){return get();}inline operator long long(void){return get();}inline Modint inverse(){int a = val;int b = MD;int u = 1;int v = 0;int t;Modint res;while(b){t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}if(u < 0){u += MD;}res.val = u;return res;}inline Modint pw(unsigned long long b){Modint a(*this);Modint res;res.val = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}inline bool operator==(int a){return ord(a)==val;}inline bool operator!=(int a){return ord(a)!=val;}};inline Modint operator+(int a, Modint b){return Modint(a)+=b;}inline Modint operator-(int a, Modint b){return Modint(a)-=b;}inline Modint operator*(int a, Modint b){return Modint(a)*=b;}inline Modint operator/(int a, Modint b){return Modint(a)/=b;}inline Modint operator+(long long a, Modint b){return Modint(a)+=b;}inline Modint operator-(long long a, Modint b){return Modint(a)-=b;}inline Modint operator*(long long a, Modint b){return Modint(a)*=b;}inline Modint operator/(long long a, Modint b){return Modint(a)/=b;}inline int my_getchar(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline int rd_int(void){int x;rd(x);return x;}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar('-');}while(s--){my_putchar(f[s]+'0');}}inline void wt_L(Modint x){int i;i = (int)x;wt_L(i);}template<class T> struct Matrix{int r;int c;int mem;T*dat;Matrix(){r=c=mem = 0;}Matrix(const int rr, const int cc){if(rr == 0 || cc == 0){r = c = 0;}else{r = rr;c = cc;}mem = r * c;if(mem > 0){dat = new T[mem];}}Matrix(const Matrix<T> &a){int i;r = a.r;c = a.c;mem = r * c;dat = new T[mem];for(i=(0);i<(mem);i++){dat[i] = a.dat[i];}}~Matrix(){if(mem){delete [] dat;}}void changeSize(const int rr, const int cc){if(rr==0 || cc==0){r = c = 0;}else{r = rr;c = cc;}if(mem < r*c){if(mem){delete [] dat;}mem = r*c;dat = new T[mem];}}Matrix<T>& operator=(const Matrix<T> &a){int i;int j;r = a.r;c = a.c;j = r * c;changeSize(r,c);for(i=(0);i<(j);i++){dat[i] = a.dat[i];}return *this;}Matrix<T>& operator=(const int a){int i;int j;j = r * c;for(i=(0);i<(j);i++){dat[i] = 0;}j =min_L(r, c);for(i=(0);i<(j);i++){dat[i*c+i] = a;}return *this;}Matrix<T>& operator+=(const Matrix<T> &a){int i;int j;if(r==0 || r!=a.r || c!=a.c){changeSize(0,0);return *this;}j = r*c;for(i=(0);i<(j);i++){dat[i] += a.dat[i];}return *this;}Matrix<T> operator+(const Matrix<T> &a){return Matrix<T>(*this) += a;}Matrix<T>& operator-=(const Matrix<T> &a){int i;int j;if(r==0 || r!=a.r || c!=a.c){changeSize(0,0);return *this;}j = r*c;for(i=(0);i<(j);i++){dat[i] -= a.dat[i];}return *this;}Matrix<T> operator-(const Matrix<T> &a){return Matrix<T>(*this) -= a;}Matrix<T>& operator*=(const Matrix<T> &a){int i;int j;int k;int x;T*m;if(r==0 || c!=a.r){changeSize(0,0);return *this;}m = (T*)wmem;x = r * a.c;for(i=(0);i<(x);i++){m[i] = 0;}for(i=(0);i<(r);i++){for(k=(0);k<(c);k++){for(j=(0);j<(a.c);j++){m[i*a.c+j] += dat[i*c+k] * a.dat[k*a.c+j];}}}changeSize(r, a.c);for(i=(0);i<(x);i++){dat[i] = m[i];}return *this;}Matrix<T> operator*(const Matrix<T> &a){return Matrix<T>(*this) *= a;}Matrix<T>& operator*=(const int a){int i;int j;j = r * c;for(i=(0);i<(j);i++){dat[i] *= a;}return *this;}Matrix<T>& operator*=(const long long a){int i;int j;j = r * c;for(i=(0);i<(j);i++){dat[i] *= a;}return *this;}Matrix<T>& operator*=(const double a){int i;int j;j = r * c;for(i=(0);i<(j);i++){dat[i] *= a;}return *this;}inline T* operator[](const int a){return dat+a*c;}};template<class T> Matrix<T> operator*(const int a, const Matrix<T> &b){return Matrix<T>(b)*=a;}template<class T> Matrix<T> operator*(const Matrix<T> &b, const int a){return Matrix<T>(b)*=a;}template<class T> Matrix<T> operator*(const long long a, const Matrix<T> &b){return Matrix<T>(b)*=a;}template<class T> Matrix<T> operator*(const Matrix<T> &b, const long long a){return Matrix<T>(b)*=a;}template<class T> Matrix<T> operator*(const double a, const Matrix<T> &b){return Matrix<T>(b)*=a;}template<class T> Matrix<T> operator*(const Matrix<T> &b, const double a){return Matrix<T>(b)*=a;}template<class T, class S> inline Matrix<T> pow_L(Matrix<T> a, S b){int i;int j;Matrix<T> res;res.changeSize(a.r, a.c);res = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}template<class T, class S> inline T pow_L(T a, S b){T res = 1;res = 1;for(;;){if(b&1){res *= a;}b >>= 1;if(b==0){break;}a *= a;}return res;}inline double pow_L(double a, double b){return pow(a,b);}Matrix<Modint> ma;Matrix<Modint> mb;Matrix<Modint> mc;int main(){int i, rbGYC8dh;wmem = memarr;ma.changeSize(6,6);mb.changeSize(6,1);for(i=(0);i<(6);i++){ma[i][i%3] = Modint(1);if(i < 3){ma[i][i%3] /= 3;}}for(i=(0);i<(3);i++){int j;for(j=(0);j<(3);j++){if(i == j){continue;}ma[i][j+3] = Modint(1);ma[i][j+3] /= 3;}}mb[0][0] = Modint (1);mb[0][0] /= 3;mb[3][0] = Modint (1);int NN9wFlop = rd_int();for(rbGYC8dh=(0);rbGYC8dh<(NN9wFlop);rbGYC8dh++){int N;rd(N);mc = ((pow_L(ma,N)));mc = (mc) * mb;wt_L(mc[3][0]);wt_L('\n');}return 0;}// cLay version 20210405-1// --- original code ---// //no-unlocked// Matrix<Modint> ma;// Matrix<Modint> mb;// Matrix<Modint> mc;//// {// ma.changeSize(6,6);// mb.changeSize(6,1);// rep(i, 6){// ma[i][i%3] = Modint(1);// if(i < 3) ma[i][i%3] /= 3;// }// rep(i, 3){// rep(j, 3){// if(i == j) continue;// ma[i][j+3] = Modint(1);// ma[i][j+3] /= 3;// }// }// mb[0][0] = Modint (1);// mb[0][0] /= 3;// mb[3][0] = Modint (1);// REP(rd_int()){// int @N;// mc = (ma ** N);// mc = (mc) * mb;// wt(mc[3][0]);// }// }